Ile jest takich permutacji, że...

[matinf]

Witam,
Mamy zbiór \(\displaystyle{ \{1,2,...,n\}}\)
Ile jest permutacji, takich że nie istnieje w niej cykl długości \(\displaystyle{ k}\).

No to ja chciałbym od wszystkich permutacji odjąć takie które właśnie mają cykl długości \(\displaystyle{ k}\).

Ile jest permutacji takich, które mają cykl długości \(\displaystyle{ k}\) ?

No więc mi się wydaje, że musimy zagwarantować, żeby taki cykl był choć jeden, a z resztą niech się dzieje co się chce.

Tych permutacji jest:
\(\displaystyle{ \binom{n}{k} \cdot \frac{k!}{k} \cdot (n-k)! = \frac{n!}{k}}\)


Ok ?

[arek1357]

Cykli o długości \(\displaystyle{ k}\) jest \(\displaystyle{ (k-1)!}\) tyle ile permutacji koralików na naszyjniku

[matinf]

Ale co u mnie jest źle ? W którym miejscu ?

[norwimaj]

Jeśli permutacja ma \(\displaystyle{ m}\) cykli długości \(\displaystyle{ k}\), to niechcący liczysz ją \(\displaystyle{ m}\) razy.

[matinf]

Ok, chcę się upewnić czy ja właściwie zrozumiałem Twoją uwagę.


Np, rozważmy taką sytuację. Sytuacja permutacji o 5 cyklach długości 2.

No więc istnieje jakaś taka permutacja, która zawiera 2 cykle długości 2. Te same cykle zawiera inna permutacja + inny jakiś 2-cykl. I już teraz policzyłem o raz za dużo (ta permutacja została policzona).
Czyli widać, że to nie jest dobre podejście.


I teraz wydaje mi się, że ja po prostu zliczam ilość permutacji (wszystkich) o tej własności, że każda z nich ma co najmniej jeden cykl tej długości.


Ok czy znowu źle ?

[norwimaj]

Chyba źle. Nie jestem pewien, czy dobrze zrozumiałem to, co napisałeś. Na wszelki wypadek rozwinę swoją myśl.

Ile jest permutacji zbioru \(\displaystyle{ \{1,2,3,4\}}\), w których istnieje cykl długości \(\displaystyle{ 2}\)? Takich, które mają tylko jeden cykl długości \(\displaystyle{ 2}\), jest \(\displaystyle{ \binom42=6}\). Pozostałe możemy wszystkie wypisać: \(\displaystyle{ (1,2)(3,4)}\), \(\displaystyle{ (1,3)(2,4)}\), \(\displaystyle{ (1,4)(2,3)}\). Wszystkich razem jest \(\displaystyle{ 9}\).

Twoją metodą wychodzi \(\displaystyle{ 12}\), bo masz \(\displaystyle{ 6}\) permutacji z jednym cyklem długości \(\displaystyle{ 2}\), oraz permutacje z dwoma cyklami: \(\displaystyle{ (1,2)(3,4)}\), \(\displaystyle{ (1,3)(2,4)}\), \(\displaystyle{ (1,4)(2,3)}\), \(\displaystyle{ (2,3)(1,4)}\), \(\displaystyle{ (2,4)(1,3)}\), \(\displaystyle{ (3,4)(1,2)}\). Jak widzisz, niektóre permutacje policzyłeś dwa razy.

[matinf]

Tak wiec, powinienem podzielić wszystko przez (ilość cykli długości 2 )silnia.


Tak, jak w takim razie ten wzór znaleźć ?
Bo nie mogę tak podzielić jak powiedziałem, bo nie wiem ile w której będzie cykli.

[norwimaj]

Tak wiec, powinienem podzielić wszystko przez (ilość cykli długości 2 )silnia.

Dlaczego silnia?

Tak, jak w takim razie ten wzór znaleźć ?

Nie wiem. Znane jest rozwiązanie w przypadku \(\displaystyle{ k=1}\), ale w ogólności nie potrafię pomóc.

[arek1357]

Ja bym proponował dzielić zbiór na podzbiory rozłączne o długości \(\displaystyle{ k}\) a potem zliczać ilość cykli w każdym takim podziale

Tak mniej więcej:

\(\displaystyle{ \{1,2,3,4,5,6\}}\)

Dzielimy zbiór na dwa podzbiory o mocy \(\displaystyle{ k=3}\)

\(\displaystyle{ \{1,2,3\}\{4,5,6\}}\)

takich podziałów jest:

\(\displaystyle{ {6\choose 3}=20}\)

W każdym podziale jest po dwa cykle o długości trzy zliczamy teraz cykle:

\(\displaystyle{ 2!*3!+2!*3!-2!*2!}\) - odejmujemy część wspólną

teraz mnożymy ten wynik przez ilość podziałów czyli \(\displaystyle{ 20}\)

i mamy ilość cykli o długości trzy w tym podzbiorze
Dla ogólnego warunku możemy stosować wzór wyłączeń (Sylwestra)

[norwimaj]

Dzielimy zbiór na dwa podzbiory o mocy \(\displaystyle{ k=3}\)

\(\displaystyle{ \{1,2,3\}\{4,5,6\}}\)

Co zrobić w przypadku, gdy \(\displaystyle{ k\not|n}\) ?

takich podziałów jest:

\(\displaystyle{ {6\choose 3}=20}\)

Nieprawda. Jest ich dwa razy mniej.

W każdym podziale jest po dwa cykle o długości trzy

Wyrażasz się niejasno. W każdym podziale są dwa zbiory o mocy trzy.

zliczamy teraz cykle:

\(\displaystyle{ 2!*3!+2!*3!-2!*2!}\) - odejmujemy część wspólną

Na podstawie tego jeszcze nie załapałem, jak zamierzasz to robić w ogólnym przypadku. Czy mógłbyś rozpisać jeszcze przypadek \(\displaystyle{ n=6,k=2}\) ?

[arek1357]

ok
dla \(\displaystyle{ n=6,k=2}\)

mamy podziały:

\(\displaystyle{ \{1,2\} \{3,4\}\{5,6\}}\)

Takich podziałów jest:

(*) \(\displaystyle{ \frac{{6 \choose 2} \cdot {4 \choose 2}}{3!}}\)

Na każdy podział przypada po \(\displaystyle{ 1}\) cykl

łącznie w każdym podziale jest po jednym cyklu tak czy inaczej

czyli zliczamy tylko podziały których jest (*)

jeśli \(\displaystyle{ k}\) nie dzieli \(\displaystyle{ n}\)

też dzielimy zbiór wyjściowy na podzbiory \(\displaystyle{ k}\) elementowe
i zostaje jeszcze reszta, zbiór o mocy mniejszej niż \(\displaystyle{ k}\), który nie ma wpływu na ilość cykli o długości \(\displaystyle{ k}\)


sorki masz racje z tymi podziałami jest ich mniej

[norwimaj]

Czyli jaki wynik jest w tym przypadku?

[arek1357]

wychodzi \(\displaystyle{ 15}\)

w przypadku \(\displaystyle{ k=2}\) każdy podzbiór o długości dwa można traktować jak cykl.


Tyle ile jest podziałów na cykle dwuelementowe.
np weźmy przypadek \(\displaystyle{ n=4,k=3}\)

Biorę takie podziały:

\(\displaystyle{ (a,b,c)\{d\}}\) na każdy taki podział mamy dwa cykle!

I moja koncepcja sprowadza się do tego żeby najpierw podzielić na podzbiory o długości \(\displaystyle{ k}\)

a potem zliczać ile w takim podzbiorze występuje cykli o długości też \(\displaystyle{ k}\)

[matinf]

A czy ktoś mi powie jak to rozwiązać ? Bo ja zaproponowałem niepoprawne rozwiązanie, choć nie będące totalnie beznadziejne.

[norwimaj]

wychodzi \(\displaystyle{ 15}\)

Jak to się ma do prawidłowego wyniku, obliczonego jakimiś prostymi metodami?