Permutacje liczb

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
herfoo
Użytkownik
Użytkownik
Posty: 103
Rejestracja: 10 paź 2006, o 21:36
Płeć: Mężczyzna
Lokalizacja: Iłża

Permutacje liczb

Post autor: herfoo » 1 gru 2013, o 21:28

Ile jest permutacji liczb \(1, 2, 3, 4, 5, 6, 7, 8\) w których nie występują \(12, 34, 45, 78\) jako pociągi kolejnych wyrazów?

Wszystkie permutacje:

\(8!\)

Określam zdarzenie polegające na występowaniu podciągów w ciągu

\(A_{1}\) występowanie podciągu 12

\(A_{2}\) występowanie podciągu 34

\(A_{3}\) występowanie podciągu 56

\(A_{4}\) występowanie podciągu 78

\(|A_{1}|=|A_{2}|=|A_{3}|=|A_{4}|=7!\)

\(|A_{1} \cap A_{2}|=...|A_{3} \cap A_{4}| = {4 \choose 2} 6!\)

\(|A_{1} \cap A_{2} \cap A_{3}|=...|A_{2} \cap A_{3} \cap A_{4}| = {4 \choose 3} 5!\)

\(|A_{1} \cap A_{2} \cap A_{3} \cap A_{4}|={4 \choose 4} 4!\)

Wzór ogólny:

\(\sum_{k=1}^{n}(-1)^{k+1} {n \choose k} (2n-k)!\)

Końcowy wynik:

\(8!-\sum_{k=1}^{4}(-1)^{k+1} {4 \choose k} (8-k)!\)

Czy rozwiązanie zadania jest poprawne?

norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E

Permutacje liczb

Post autor: norwimaj » 1 gru 2013, o 21:44

herfoo pisze: \(|A_{1}|=|A_{2}|=|A_{3}|=|A_{4}|=7!\)
Do tego miejsca jest dobrze.
herfoo pisze:\(|A_{1} \cap A_{2}|=...|A_{3} \cap A_{4}| = {4 \choose 2} 6!\)
To już jest źle.

herfoo
Użytkownik
Użytkownik
Posty: 103
Rejestracja: 10 paź 2006, o 21:36
Płeć: Mężczyzna
Lokalizacja: Iłża

Permutacje liczb

Post autor: herfoo » 1 gru 2013, o 21:58

Więc może wytłumacze mój tok rozumowania:

\({n \choose k}\) - jest liczbą wszystkich możliwych przecięć dwóch zbiorów. Skoro mamy 4 zbiory i mamy z nich wybrać 2 to wynik będzie kombinacją \({4 \choose 2}\) Jest to zdarzenie takie, że np 12 i 34 występują jednocześnie. Zatem jeżeli one występują jednocześnie czyli możemy całość ustawić na \(6!\)

Analogicznie w pozostałych przypadkach.

Możesz wytłumaczyć bliżej co jest tutaj złego w tym toku rozumowania?

norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E

Permutacje liczb

Post autor: norwimaj » 1 gru 2013, o 22:07

Jeśli masz policzyć na przykład \(|A_{1} \cap A_{2}|\), to jakie zbiory tam musisz jeszcze wybierać?

herfoo
Użytkownik
Użytkownik
Posty: 103
Rejestracja: 10 paź 2006, o 21:36
Płeć: Mężczyzna
Lokalizacja: Iłża

Permutacje liczb

Post autor: herfoo » 1 gru 2013, o 22:18

no to są te zbiory w któych występuje 12, 34 jednoczesnie plus reszta w dowolnej kolejnosci wiec pojedyńcze przeciecie bedzie wynosiło \(6!\) natomiast suma tych przecięć będzie wynosiła \({4 \choose 2} \cdot 6!\)

norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E

Permutacje liczb

Post autor: norwimaj » 1 gru 2013, o 22:35

Czyli po zamianie tego:
herfoo pisze: \(|A_{1} \cap A_{2}|=...|A_{3} \cap A_{4}| = {4 \choose 2} 6!\)

\(|A_{1} \cap A_{2} \cap A_{3}|=...|A_{2} \cap A_{3} \cap A_{4}| = {4 \choose 3} 5!\)
na to:
\(|A_{1} \cap A_{2}|+\ldots+|A_{3} \cap A_{4}| = {4 \choose 2} 6!\)

\(|A_{1} \cap A_{2} \cap A_{3}|+\ldots+|A_{2} \cap A_{3} \cap A_{4}| = {4 \choose 3} 5!\)
rozwiązanie będzie dobre.

ODPOWIEDZ