mateforum.ro

Gasiti numarul permutarilor de ordinul \( n \) care nu au puncte fixe.

Problema tipica de numarare.
Sa numaram toate permutarile care au cel putin un punct fix. Notand \( A_i \) multimea permutarilor pentru care \( i \) e punct fix, ne intereseaza \( |A_1\cup A_2\cup\dots\cup A_n|=\sum_i|A_i|-\sum_{i<j}|A_i\cap A_j|-\sum_{i<j<k}|A_i\cap A_j \cap A_k|+\dots=C_n^1(n-1)!-C_n^2(n-2)!+\dots \) (am folosit PIE).
Scazand acest numar din numarul total de permutari \( n! \) gasim in final
\( \sum_{k=0}^{n}(-1)^k C_n^k(n-k)! \)
permutari fara puncte fixe.

Daca mai si simplifici factorialul de la numitorii combinarilor obtii
\( \sum_{k=0}^n \frac{n!}{k!}(-1)^k \).