Jakie jest prawdopodobieństwo

[max123321]

Jakie jest prawdopodobieństwo, że w losowo wybranej permutacji zbioru \(\displaystyle{ \left\{ 1,2,...,n\right\}}\) liczba \(\displaystyle{ 1}\) znajdzie się w cyklu \(\displaystyle{ k}\)-elementowym \(\displaystyle{ \left( 1 \le k \le n\right)}\).

Jak to zrobić?

[Premislav]

Na \(\displaystyle{ {n-1\choose k-1}}\) sposobów dobierasz pozostałe elementy, które będą w tym cyklu, co \(\displaystyle{ 1}\). Jak masz te elementy, to z \(\displaystyle{ k}\) elementów powstanie \(\displaystyle{ (k-1)!}\) cykli długości \(\displaystyle{ k}\) (to już Ci z grubsza pokazywałem przy okazji innego zadania). Pozostałe elementy permutujesz na \(\displaystyle{ (n-k)!}\) sposobów (dzięki temu, że do tego cyklu długości \(\displaystyle{ k}\) ma należeć konkretny element, niczego w ten sposób nie policzysz wielokrotnie). Następnie dzielisz to przez liczbę wszystkich permutacji zbioru \(\displaystyle{ n}\)-elementowego, czyli \(\displaystyle{ n!}\).
Otrzymujemy w ten sposób prawdopodobieństwo
\(\displaystyle{ \frac{{n-1\choose k-1}(k-1)!(n-k)!}{n!}=\frac{1}{n}}\)
Taki wynik podpowiada, że jest też sprytniejsze podejście do tego zadania, ale ja sprytny nie jestem.

[max123321]

Czyli jak rozumiem najpierw dobierasz elementy, które będą w cyklu z jedynką, a potem je permutujesz z tym, że dla dowolnej permutacji zrobionej w ten sposób "przesunięcie" w prawo o jedno lub więcej miejsc wszystkich elementów z zawinięciem ostatnich na pierwsze da ten sam cykl. Czyli jak normalnie \(\displaystyle{ k}\) elementów by można było spermutować na \(\displaystyle{ k!}\) sposobów tak każdy cykl zostanie policzony \(\displaystyle{ k}\) razy zatem \(\displaystyle{ k!}\) trzeba podzielić przez \(\displaystyle{ k}\) czyli \(\displaystyle{ (k-1)!}\) tak? No, a potem pozostałe elementy permutujemy dowolnie. O to chodzi?

[Premislav]

Tak.

[a4karo]

Fatalnie sformułowane zadanie, bo rozkład na cykle nie jest jednoznaczny.

[Premislav]

No należy dopisać, że chodzi o cykle rozłączne.