0

After I learned the Error permutation problems, I start to think the more complicated situations. Choose $n$ different numbers from number $1$ to $m$ ($m≥n$) to make a permutation,what's the sums of permutations that all i-th $(0<i≤n)$ position numbers is not number $i$? For example,when $n=2$ and $m=3$,there are only three situations.

$$2 1$$ $$2 3$$ $$3 1$$ I want a function like Γ(n + 1, -1)/e when $n=m$.

Thomas Andrews
  • 177,126

1 Answers1

1

Inclusion-exclusion is your friend.

Let $A$ be the set of permutationss of $n$ elements from $1,\dots,m.$ Let $A_i$ be the set of such permutations with $i$th element $i.$

Then you get:$$\left|A\setminus (A_1\cup A_n)\right|=\frac{m!}{(m-n)!}-\sum_{k=1}^{n}(-1)^{k-1}\binom nk \frac{(m-k)!}{(m-n)!}$$

When $n=m$ this gives the usual derangements term:

$$\binom{n}k\frac{(m-k)!}{(m-n)!}=\frac{m!}{k!}$$

When $n=m-1,$

$$\binom{n}k\frac{(m-k)!}{(m-n)!}=\frac{(m-k)(m-1)!}{k!}$$

When $n=2,m=3$ you get:

$$6-4+1=3.$$

Thomas Andrews
  • 177,126
  • Thank you sir,but can it be simplified with $n,m$ and gamma function?Sorry for my additional requirement because it is hard to make a program to calculate now.@Thomas Andrews – shenyuantao Jun 11 '21 at 13:36