# Number of permutations with a given property

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

$$\sum_{i=1}^nc_i(n-i)!=n!$$

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\}$$

• I think it's meant as a mapping of sets there -- the image of $\{1,\dots,k\}$ is not itself. – cwindolf Nov 20 '19 at 21:25
• @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. – Robert Shore Nov 20 '19 at 21:26
• I believe this is A003319 in oeis. – lulu Nov 20 '19 at 21:34

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.
• i am sorry is $[n]$ a set with $n$ elements? – Nasal Nov 20 '19 at 21:39
• Yes, $[n] := \{1,...,n\}$ – Asaf Rosemarin Nov 20 '19 at 21:40