MathDB
2012 BMT Team 9

Source:

January 5, 2022
permutationcombinatorics

Problem Statement

A permutation of a set is a bijection from the set to itself. For example, if σ\sigma is the permutation 17↦31 7\mapsto 3, 2↦12 \mapsto 1, and 3↦23 \mapsto 2, and we apply it to the ordered triplet (1,2,3)(1, 2, 3), we get the reordered triplet (3,1,2)(3, 1, 2). Let σ\sigma be a permutation of the set {1,...,n}\{1, ... , n\}. Let θk(m)={m+1for  m<k1for  m=kmfor  m>k\theta_k(m) = \begin{cases} m + 1 & \text{for} \,\, m < k\\ 1 & \text{for} \,\, m = k\\ m & \text{for} \,\, m > k\end{cases} Call a finite sequence {ai}i=1j\{a_i\}^{j}_{i=1} a disentanglement of σ\sigma if θaj∘...∘θaj∘σ\theta_{a_j} \circ ...\circ \theta_{a_j} \circ \sigma is the identity permutation. For example, when σ=(3,2,1)\sigma = (3, 2, 1), then {2,3}\{2, 3\} is a disentaglement of σ\sigma. Let f(σ)f(\sigma) denote the minimum number kk such that there is a disentanglement of σ\sigma of length kk. Let g(n)g(n) be the expected value for f(σ)f(\sigma) if σ\sigma is a random permutation of {1,...,n}\{1, ... , n\}. What is g(6)g(6)?
Back to ProblemsView on AoPS