[Kombinatoryka] Pozamieniane listy

[przemon]

Ktoś napisał sześć listów do sześciu osób i zaadresował do nich sześć kopert. Iloma sposobami można listy tak włożyć do kopert, żeby żaden list nie trafił do właściwej koperty?

[Skrydka]

Policz ile jest możliwych kombinacji listów z kopertami i odejmij jedną - prawidłową i masz wynik.

[ordyh]

Policz ile jest możliwych kombinacji listów z kopertami i odejmij jedną - prawidłową i masz wynik.

a co z np. takim przypadkiem, że 4 listy trafią dobrze, a 2 źle?

[Afish]

\(\displaystyle{ 5 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}\)? Bierzemy pierwszy list i wkładamy go do dowolnej niewłaściwej koperty. Następnie bierzemy list, który miał iść do tej koperty, do której włożyliśmy pierwszy list i wkładamy go do dowolnej niewłaściwej koperty. Postępowanie kontynuujemy, aż skończą się listy.

PS Mówiąc "niewłaściwa koperta" mam na myśli kopertę zaadresowaną do innej osoby, niż adresat dnaego listu.

[Qń]

\(\displaystyle{ 5 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}\)? Bierzemy pierwszy list i wkładamy go do dowolnej niewłaściwej koperty. Następnie bierzemy list, który miał iść do tej koperty, do której włożyliśmy pierwszy list i wkładamy go do dowolnej niewłaściwej koperty. Postępowanie kontynuujemy, aż skończą się listy.

Jeśli pierwszy list trafi do drugiej koperty, a drugi do pierwszej, to na kolejny mamy tylko trzy możliwości, a nie cztery.

Odnośnie prawidłowego rozwiązania, wskazówka: zasada włączeń i wyłączeń. Ewentualnie bardziej szczegółowa wskazówka: wygooglać "liczba nieporządków".

Q.

[przemon]

Prawidłowa odpowiedź (aby zmniejszyć liczbę postów z błędnymi wynikami):

Ukryta treść:    

265 sposobów

Prosiłbym o jak najbardziej elementarne rozwiązanie problemu, gdyż propozycja użytkownika Qń wygląda mi na dość skomplikowaną (nie wiem czy w rzeczywistości jest).

[Qń]

propozycja użytkownika Qń wygląda mi na dość skomplikowaną

Masz do wyboru: albo użyjesz zasady włączeń i wyłączeń, albo wypiszesz wszystkie możliwości i policzysz je ręcznie.

A prawidłowa odpowiedź to jak się zdaje \(\displaystyle{ 264}\).

Q.

[przemon]

Odpowiedź przepisałem z książki, ale rozwiązanie w niej zawarte wydaje się sensowne i nie znalazłem błędu. Ciekawią mnie inne rozwiązania, czy mogłbyś zaprezentować swoje, jak doszedłeś do wyniku \(\displaystyle{ 264}\).

[Qń]

Zaprezentuj rozwiązanie z książki, to będzie można ocenić czy w rozumowaniu nie ma błędu.

A do wyniku \(\displaystyle{ 264}\) doszedłem tak jak napisałem: używając zasady włączeń i wyłączeń.

Q.

[Fingon]

\(\displaystyle{ a_n}\) - rozwiązanie dla n kopert
\(\displaystyle{ \begin{cases} a_1 = 0 \\ a_2 = 1 \\ a_n = (n-1)\cdot(a_{n-1} + a_{n-2}) \end{cases}}\)

\(\displaystyle{ a_6 = 265}\)

Skąd wziął się wzór? Załóżmy, że mamy jedno z rozwiązań zadania dla danego n, a koperty oraz skrzynki są ponumerowane od 1 do n. Zamieńmy miejscami kopertę n, oraz kopertę znajdującą się w skrzynce n, a następnie usuńmy skrzynkę o numerze n. W ten sposób otrzymaliśmy jakiś układ n-1 kopert w n-1 skrzynkach, z którego można stworzyć rozwiązanie dla n kopert, odwracając cały opisany proces. Teraz przyjrzyjmy się rodzajom układów, jakie możemy w ten sposób uzyskać. Są dwie opcje. Pierwsza opcja: żadna z n-1 kopert nie jest w skrzynce o numerze jej odpowiadającej, takich układów jest \(\displaystyle{ a_{n-1}}\), wtedy możemy stworzyć rozwiązanie dla n kopert przez dołożenie nowej skrzynki z kopertą i zamianę miejscami dołożonej koperty z dowolną inną, w ten sposób zyskujemy \(\displaystyle{ (n-1)\cdot a_{n-1}}\) rozwiązań. Druga opcja: dokładnie jedna koperta jest na swoim miejscu, rozwiązanie dla n kopert tworzymy przez dołączenie nowej skrzynki z kopertą i zamianę miejscami kopert, które znajdują się w skrzynkach o numerach im odpowiadających, więc każdy taki układ daje nam jedno rozwiązanie, a takich układów jest \(\displaystyle{ (n-1)\cdot a_{n-2}}\). Po zsumowaniu rozwiązań otrzymujemy podany na początku wzór.

[przemon]

W książce jest dokładnie to samo rozwiązanie.

[Qń]

Rzeczywiście, \(\displaystyle{ 265}\), nie doliczyłem ostatniego składnika, powinno być:

\(\displaystyle{ 6! \cdot \left(\frac{1}{0!}-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}+\frac{1}{6!}\right)}\)

Q.

[Althorion]

Nawiasem mówiąc, jeżeli kogoś to interesuje, to funkcję taką, że \(\displaystyle{ f(n) = a_n}\) w tym przykładzie nazywa się podsilnią i zapisuje \(\displaystyle{ f(n) = \, !n}\).

Równanie rekurencyjne już nam Fingon podał, więc ja dam tylko wzór jawny:
\(\displaystyle{ !n = n! \sum_{i=0}^{n} \frac{(-1)^i}{i!}}\)