Otóż próbuję ożywić ten dział ciekawym zadaniem z cykli permutacyjnych , otóż wyznaczyć ciąg: \(\displaystyle{ a(n,k)}\)
gdzie \(\displaystyle{ n}\) długość permutacji ale każda permutacja o długości \(\displaystyle{ n }\) zawiera różną ilość cykli o różnych długościach.
Nas interesuje, żeby wyliczyć ile jest tych permutacji, które zawierają takie cykle, których suma długości wynosi \(\displaystyle{ k: n \ge k \ge 1}\)
\(\displaystyle{ a(2,1)=1}\)
Podam przykład:
\(\displaystyle{ n=3, k=2}\)
wiadomo, że permutacji wszystkich jest \(\displaystyle{ 6}\), ale odpowiadające warunkom zadania są typu:
\(\displaystyle{ (..)(.) - 3}\)
\(\displaystyle{ (.)(.)(.) - 1}\)
Oczywiście nie pasuje:
\(\displaystyle{ (...) - }\) bo tu nie ma cyklów, żeby sumowały się do dwóch, awięc odpowiedź:
\(\displaystyle{ a(3,2)=4}\)
oczywiście: \(\displaystyle{ a(3,1)=a(3,2)=4}\)
Teraz:
\(\displaystyle{ n=4, k=2}\)
Odpowiadające permutacje o cyklach:
\(\displaystyle{ (..)(..) - 3}\)
\(\displaystyle{ (..)(.)(.) - 6}\)
\(\displaystyle{ (.)(.)(.)(.) - 1}\)
więc:
\(\displaystyle{ a(4,2)=10}\)
jeszcze jedno:
\(\displaystyle{ n=4, k=3}\)
\(\displaystyle{ (...)(.) - 8}\)
\(\displaystyle{ (..)(.)(.) - 6}\)
\(\displaystyle{ (.)(.)(.)(.) - 1}\)
\(\displaystyle{ a(4,3)=18}\)
\(\displaystyle{ a(4,4)=24}\)
\(\displaystyle{ a(4,1)=8+1+6=15}\)
itd...
\(\displaystyle{ a(n,n)=n!}\)
Permutacje
-
arek1357
- Użytkownik
- Posty: 5747
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 526 razy
Re: Permutacje
Doszedłem jeszcze do tego, że:
\(\displaystyle{ a(n,1)=n!- \sum_{i=0}^{n} (-1)^i \frac{1}{i!} }\)
Czyli ze wszystkich permutacje wyrzucamy tylko nieporządki
Następna rzecz jaką odkryłem to to, że:
\(\displaystyle{ a(n,k)=a(n,n-k)}\)
czyli wystarczy liczyć \(\displaystyle{ k}\) dla:
\(\displaystyle{ k=1,2,3,..., \left[ \frac{n}{2} \right] }\)
Dla:
\(\displaystyle{ k \in \left\langle 2,3,4,..., \left[\frac{n}{2} \right]\right\rangle }\)
trudno napisać jakiś spektakularny wzór, ale da się je wyliczyć bardzo łatwo ze wzoru na ilość permutacji:
(*) \(\displaystyle{ \frac{n!}{1^{a_{1}} \cdot 2^{a_{2}} \cdot 3^{a_{3}} \cdot ... \cdot n^{a_{n}} \cdot a_{1}! \cdot a_{2}! \cdot ... \cdot a_{n}! } }\)
Oczywiście długości cykli w tej permutacji mają rozkład partycjonalny \(\displaystyle{ p(n)}\)
I teraz, żeby zliczyć: \(\displaystyle{ a(n,k)}\) możemy liczyć ze wzoru (*) ale tylko te rozkłady brać w których zachodzi:
\(\displaystyle{ P(k,s) \subset p(n), s=1, 2, 3,...,k}\) dla pewnego \(\displaystyle{ s}\).
Np dla \(\displaystyle{ k=3 }\), wybieramy z \(\displaystyle{ p(n)}\) te rozkłady w których zawierają się partycje liczby \(\displaystyle{ 3}\)
Czyli muszą być cykle tego typu:
\(\displaystyle{ (...)}\) ,
\(\displaystyle{ (..)(.)}\) ,
\(\displaystyle{ (.)(.)(.)}\).
Jeżeli ,żadnego z tych rozkładów nie będzie to ten rozkład \(\displaystyle{ p(n)}\) odrzucamy
Czyli:
\(\displaystyle{ a(n,k)= \sum_{P(k,s) \subset p(n)}^{}\frac{n!}{1^{a_{1}} \cdot 2^{a_{2}} \cdot 3^{a_{3}} \cdot ... \cdot n^{a_{n}} \cdot a_{1}! \cdot a_{2}! \cdot ... \cdot a_{n}! } }\)
\(\displaystyle{ a(n,1)=n!- \sum_{i=0}^{n} (-1)^i \frac{1}{i!} }\)
Czyli ze wszystkich permutacje wyrzucamy tylko nieporządki
Następna rzecz jaką odkryłem to to, że:
\(\displaystyle{ a(n,k)=a(n,n-k)}\)
czyli wystarczy liczyć \(\displaystyle{ k}\) dla:
\(\displaystyle{ k=1,2,3,..., \left[ \frac{n}{2} \right] }\)
Dla:
\(\displaystyle{ k \in \left\langle 2,3,4,..., \left[\frac{n}{2} \right]\right\rangle }\)
trudno napisać jakiś spektakularny wzór, ale da się je wyliczyć bardzo łatwo ze wzoru na ilość permutacji:
(*) \(\displaystyle{ \frac{n!}{1^{a_{1}} \cdot 2^{a_{2}} \cdot 3^{a_{3}} \cdot ... \cdot n^{a_{n}} \cdot a_{1}! \cdot a_{2}! \cdot ... \cdot a_{n}! } }\)
Oczywiście długości cykli w tej permutacji mają rozkład partycjonalny \(\displaystyle{ p(n)}\)
I teraz, żeby zliczyć: \(\displaystyle{ a(n,k)}\) możemy liczyć ze wzoru (*) ale tylko te rozkłady brać w których zachodzi:
\(\displaystyle{ P(k,s) \subset p(n), s=1, 2, 3,...,k}\) dla pewnego \(\displaystyle{ s}\).
Np dla \(\displaystyle{ k=3 }\), wybieramy z \(\displaystyle{ p(n)}\) te rozkłady w których zawierają się partycje liczby \(\displaystyle{ 3}\)
Czyli muszą być cykle tego typu:
\(\displaystyle{ (...)}\) ,
\(\displaystyle{ (..)(.)}\) ,
\(\displaystyle{ (.)(.)(.)}\).
Jeżeli ,żadnego z tych rozkładów nie będzie to ten rozkład \(\displaystyle{ p(n)}\) odrzucamy
Czyli:
\(\displaystyle{ a(n,k)= \sum_{P(k,s) \subset p(n)}^{}\frac{n!}{1^{a_{1}} \cdot 2^{a_{2}} \cdot 3^{a_{3}} \cdot ... \cdot n^{a_{n}} \cdot a_{1}! \cdot a_{2}! \cdot ... \cdot a_{n}! } }\)