Are $n!=\sum_{k=0}^{n}kD_{n,k}$ and $n!=\sum_{k=0}^{n}\left(k-1\right)^{2}D_{n,k}$ true?

221 Views Asked by At

It's known that :

$$n!=\sum_{k=0}^{n}\binom{n}{k}D_{n-k}\tag{I}$$

Where $D_{n-k}$ is the number of derangements on a set $[n-k]$.

On the other hands from the number of partial derangements we know that:

$$D_{n,k}=\binom{n}{k}D_{n-k,0}$$

Where $D_{n,k}$ is the number of ways to select $k$ elements from $[n]$ to be fixed and let the others to be deranged (AKA Rencontres numbers).

Clearly $D_{n,0}=D_n$, from here $(\text{I})$ can be rewritten as:

$$n!=\sum_{k=0}^{n}D_{n,k}$$

I know another definitions for $n!$ which are as follows:

$$n!=\sum_{k=0}^{n}kD_{n,k}\tag{1}$$ $$n!=\sum_{k=0}^{n}\left(k-1\right)^{2}D_{n,k}\tag{2}$$

However I'm not sure if the one is right,so can someone check the validity of the two definitions and if they're true then prove them combinatorially?(I think the first one is not true)

1

There are 1 best solutions below

2
On

It seems to me that the first one is true. The expression $$\sum_{k=1}^nk\binom{n}{k}D_{n-k}$$ means that one picks one of the fixed points of the permutation and color it knowing, apriori, that it is a fixed point.

It is equivalent to picking an element from the $n$ available before forming the permutation in $n$ ways and then picking the other $k-1$ fixed points to form a permutation with $k$ fixed points in $$\sum_{k=0}^{n-1}\binom{n-1}{k-1}D_{n-1-k}=(n-1)!$$ ways by the proposition that you have there (Check comment below). This two process are equivalent, and so the result is true.

Edit: The second one is also true for $n>0.$ Notice that $(k-1)^2=k^2-2k+1.$ Distribute the sum over $k^2$ and $-2k+1$ separately and use the result above to see that the $-2k+1$ gives a $-(n!)$ and so you have to check that $$\sum_{k=0}^nk^2D_{n,k}=2(n!).$$ For this result use the same approach as above by noticing that $k^2$ means choosing $2$ fixed points to color, they can be repeated. Check that $a^2=2\cdot \binom{a}{2}+\binom{a}{1}$ for every $a$ and use it to conclude the result.


Another way to see this results is by thinking probabilistically. Consider the random variable $X$ that tells you the number of fixed points in a permutation $\sigma .$ Notice that $$\mathbb{E}[X]=\frac{1}{n!}\sum_{k=0}^nkD_{n,k},$$ because the probability of getting $k$ fixed points is given by $P(X=k)=\frac{D){n,k}}{n!}.$ Notice also that $X=\sum_{i=1}^n\mathbb{1}_{\sigma (i)=i},$ where $\mathbb{1}_{\sigma (i)=i}$ is 1 if $i$ is a fixed point and $0$ if not. Is easy to check that $$\mathbb{E}[\mathbb{1}_A]=P(A).$$ Check that $P(\mathbb{1}_{\sigma(i)=1})=\frac{1}{n}$ and use linearity of expectation to get your result.

It is worth noticing that this sums corresponds to the moments of this random variable.