Ilość różnych kombinacji k jednakowych ciągów?

[TomASS]

Witam

Mam ciąg składający się z kolejnych liczb naturalnych - np. P={0,1,2,3} o długości |P|

Mam drugi ciąg ( D ), który składa się TYLKO z liczb z pierwszego ciągu i o długości wielokrotności (k) |P| i każda liczba występu w nim dokładnie |P| razy

Czyli poprawny ciąg D o długości k*|P| dla k=3 długość 12 wygląda np.

D1 = {0,1,2,3,0,1,2,3,0,1,2,3}
D2 = {0,0,0,1,1,1,2,2,2,3,3,3}
D3 = {3,0,2,3,1,2,0,0,2,1,1,3}

Pytanie:

Ile różnych kombinacji jest możliwych w zależności od wartości parametru k i długości ciągu |P|?

[lina2002]

Jak masz ciąg \(\displaystyle{ k \cdot \left|P \right|}\), to należałboy chyba najpierw wybrac miejsce dla \(\displaystyle{ 0}\), a zer masz \(\displaystyle{ \left|P \right|}\). Tak więc wybierasz miejsca na \(\displaystyle{ {k \left|P \right| \choose \left| P\right| }}\) sposobów, potem dla jedynek na \(\displaystyle{ {(k-1) \left|P \right| \choose \left|P \right| }}\) sposobów itd. Następnie z reguły mnożenia liczba sposobów jest równa:

\(\displaystyle{ {k \left|P \right| \choose \left| P\right| }{(k-1) \left|P \right| \choose \left|P \right| }... {2 \left|P \right| \choose \left|P \right| } { \left|P \right| \choose \left|P \right| }}\)
Teraz spróbuj to rozpisać i zobaczysz jak się ładnie liczniki i mianowniki skracają .

[TomASS]

Dzięki,

Też tak kombinowałem ale wyjdzie sporo powtarzanych ciągów. Jakby (teoretycznie) numerować liczby i np.

P1 = {0.1 , 1.1 , 2.1, 3.1} oraz P2 = {0.2, 1.2, 2.2, 3.2}

to ciąg D1 = {0.1 , 1.1 , 2.1, 3.1, 0.2, 1.2, 2.2, 3.2} = D2 = {0.2, 1.2, 2.2, 3.2, 0.1 , 1.1 , 2.1, 3.1}

czyli obydwa ciągi będą wyglądały 0,1,2,3,0,1,2,3 :/

tych dublowanych oczywiście nie powinniśmy zliczać - jak to ująć?

[lina2002]

Przeciez wcale Ci się ciągi nie powtórzą, bo w kombinacjach nie bierzesz pod uwagę kolejności. Np. kiedy wybieram miejsca dla zer, to wybieram \(\displaystyle{ \left|P \right|}\) miejsc nie biorąc pod uwagę kolejności ich wybierania. Gdybyś najpierw wybierał miejsce dla pierwszego zera na \(\displaystyle{ k \left|P \right|}\), dla drugiego na \(\displaystyle{ k\left|P \right|-1}\) sposobów, to wtedy byłby problem, o którym piszesz, ale wtedy wyszedłby swoją drogą wynik \(\displaystyle{ (k \left|P \right|)!}\) (wariacja bez powtórzeń) i trzeba by to było dzielić, zeby się kolejności pozbyć. Łatwiej jest tak jak napisałam.

[TomASS]

Ok, dzięki, rzeczywiście masz rację.

Wyszło mi coś takiego:
\(\displaystyle{ \frac{ \left( k |P|\right)! }{|P|! k}}\)

dobrze wyszło?

[lina2002]

Wyszło Ci dobrze. Przecież to wcale nie jest 1...
\(\displaystyle{ \frac{k \left|P \right| \cdot (k \left|P \right|-1) \cdot ... \cdot 2 \cdot 1 }{ k \cdot \left|P \right| \cdot \left|P-1 \right| \cdot ... \cdot 2 \cdot 1 }}\)
Możnaby ewentualnie skrócić przez \(\displaystyle{ k \left|P \right|}\), ale jakbyś chciał to skrócić do jedynki, to doprawdy nie wiem .

[TomASS]

Dzięki, czyli dla k=4 i |P|=5
daje to nam :
\(\displaystyle{ \frac{20!}{5! \cdot 4} \approx 5 \cdot 10^{15}}\)
tak?

[lina2002]

Tak, dokładnie \(\displaystyle{ 5068545850368000}\), można w pamięci policzyć .