Permutacje liczb

[herfoo]

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

Wszystkie permutacje:

\(\displaystyle{ 8!}\)

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

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

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

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

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

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

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

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

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

Wzór ogólny:

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

Końcowy wynik:

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

Czy rozwiązanie zadania jest poprawne?

[norwimaj]

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

Do tego miejsca jest dobrze.

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

To już jest źle.

[herfoo]

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

\(\displaystyle{ {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ą \(\displaystyle{ {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 \(\displaystyle{ 6!}\)

Analogicznie w pozostałych przypadkach.

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

[norwimaj]

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

[herfoo]

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 \(\displaystyle{ 6!}\) natomiast suma tych przecięć będzie wynosiła \(\displaystyle{ {4 \choose 2} \cdot 6!}\)

[norwimaj]

Czyli po zamianie tego:

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

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

na to:

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

\(\displaystyle{ |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.