We say a permutation $\sigma$ of a set $S = \{1,2,\dots,n\}$ has a property $A$ if for every $1\le k < n$, $$\sigma(\{1,\dots,k\})\not=\{1,\dots,k\}$$ Let $c_n$ be the number of such permutations, prove that the following equation holds


Not sure how to aproach this, tried it for small numbers and i've got that $c_1=1,c_2=1,c_3=3,c_4=13$. Also not sure if i can somehow prove it combinatorialy with $i$ being lenght of a prefix of a permutation that satisfies property $A$.

For example for $S = \{1,2,3\}$ $$ \sigma= \left( \begin{matrix} 1&2&3\\2&3&1 \end{matrix} \right) $$ works and $$\sigma_2= \left( \begin{matrix} 1&2&3\\2&1&3 \end{matrix} \right)$$ doesn't since $\sigma_2(\{1,2\})=\{1,2\}$

  • 2
    $\begingroup$ I think it's meant as a mapping of sets there -- the image of $\{1,\dots,k\}$ is not itself. $\endgroup$ – cwindolf Nov 20 '19 at 21:25
  • $\begingroup$ @Paul No, it requires that $\sigma$ applied to any proper initial segment of $n$ permutes at least one element of the initial segment away from the initial segment. $\endgroup$ – Robert Shore Nov 20 '19 at 21:26
  • 2
    $\begingroup$ I believe this is A003319 in oeis. $\endgroup$ – lulu Nov 20 '19 at 21:34

Call a permutation that has the property you mentioned "good".
You can show that there is a bijection between the set of all of the permutations on $[n]$ and the set $$\{(k,f,g) |k\in [n], f \text{ is a good permutation on } [k] \text{ and } g \text{ is a permutation on } \{k+1,...,n\}\}$$
By looking at the first $k$ such that $f[k]=[k]$ for some permutation. this proves the relation.

| cite | improve this answer | |
  • $\begingroup$ i am sorry is $[n]$ a set with $n$ elements? $\endgroup$ – Nasal Nov 20 '19 at 21:39
  • $\begingroup$ Yes, $[n] := \{1,...,n\}$ $\endgroup$ – Asaf Rosemarin Nov 20 '19 at 21:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.