Ile jest permutacji z jedynką w cyklu długości k

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Heniek1991
Użytkownik
Użytkownik
Posty: 111
Rejestracja: 14 paź 2010, o 16:58
Płeć: Mężczyzna
Lokalizacja: Lublin / Warszawa
Podziękował: 1 raz
Pomógł: 1 raz

Ile jest permutacji z jedynką w cyklu długości k

Post autor: Heniek1991 »

Zadanie: \(\displaystyle{ n \ge k > 0}\). Ile jest n-permutacji, w których jedynka należy do cyklu długości k.

Czy dobrze rozumuje?
Wybieramy z n-1 elementów k-1 na \(\displaystyle{ {n-1 \choose k-1}}\) sposobów. Rozważmy zapis cyklowy. Teraz wybrane k-1 elementów z jedynką ustawiamy na \(\displaystyle{ k!}\) sposobów w ciąg. Zamykamy go w jeden cykl. Ale mamy permutacje różniące się tylko przesunięciem. Zatem dzielimy przez k. Pozostałe n-k elementów ustawiamy w dowolny sposób w permutacje, czyli \(\displaystyle{ (n-k)!}\).

Podsumowując: \(\displaystyle{ {n-1 \choose k-1} \cdot (k-1)! \cdot (n-k)! = \frac{(n-1)! \cdot (k-1)! \cdot (n-k)!}{(n-k)! \cdot (k-1)!} = (n-1)!}\)
Jeśli się mylę, to w którym miejscu?
Ostatnio zmieniony 14 sie 2011, o 00:12 przez Lbubsazob, łącznie zmieniany 1 raz.
Powód: Symbol mnożenia to \cdot.
ODPOWIEDZ