Zasada włączeń i wyłączeń - 365 dni, 80 sukienek

[Elas]

Mój pierwszy post na forum, więc się przywitam - cześć
Mam problem z tym zadaniem. Ma ono zostać rozwiązane zasadą włączeń i wyłączeń, ale nie jestem w stanie wymyślić, jak można je pod nią przystosować.

Pewna pani ma 80 sukienek. Każdego dnia w roku (365 dni) ubiera jedną z nich. Na ile sposobów może ubierać się przez rok, zakładając, że musi ubrać każdą sukienkę co najmniej raz.

Z góry dziękuje za wszelką pomoc

[MatXXX]

Cześć!
Musisz zastosować zasadę włączeń i wyłączeń w zależności od ilości sukienek, których dama NIE założyła. Czyli zbiory \(\displaystyle{ A_i}\) to takie ustawienia, że nie w żaden z dni nie jest zakładana \(\displaystyle{ i}\)-ta sukienka, a \(\displaystyle{ S_i}\), czyli części wspólne zbiorów, ustalasz wybierając \(\displaystyle{ i}\) sukienek, które nie zostały założone oraz zliczając możliwości dopasowania \(\displaystyle{ 80-i}\) sukienek do \(\displaystyle{ 365}\) dni. W ogólności jest to problem zliczania suriekcji (w tym wypadku ze zbioru \(\displaystyle{ 365}\) elementowego na \(\displaystyle{ 80}\) elementowy)

[Elas]

Mógłbyś to jakoś szerzej rozwinąć? Na chwilę obecną dalej nie jestem w stanie zrozumieć o co chodzi.

[MatXXX]

Masz dwa zbiory, jeden z nich to zbiór dni w roku, a drugi to zbiór sukienek. Będziemy przyporządkowywać każdemu z dni jedną sukienkę, czyli zrobimy funkcję ze zbioru dni do zbioru sukienek. Każda sukienka ma być użyta co najmniej raz, czyli funkcje, których szukamy, muszą być suriekcjami (czyli funkcjami "na"). Do zliczania suriekcji można użyć zasady włączeń i wyłączeń tak jak tutaj (dwa ostatnie posty to poprawne odpowiedzi).

[Majeskas]

W takich sytuacjach liczy się "od tyłu". Od wszystkich możliwości ubrania się odejmiemy te "złe". Co to znaczy "złe"? Skoro dobre to takie, w których każda sukienka wystąpi co najmniej raz, złe to takie, w których pewna sukienka nie wystąpi w ogóle. Ale nie wiadomo która. To może być którakolwiek z tych 80. Oznaczmy

\(\displaystyle{ A_i}\) - zbiór tych wszystkich możliwości ubrania się, w których \(\displaystyle{ i}\)-ta sukienka nie wystąpi.

W takim razie szukamy mocy zbioru \(\displaystyle{ A_1\cup A_2\cup\ldots\cup A_{80}}\). Zbiory występujące w tej sumie nie są parami rozłączne, np. \(\displaystyle{ A_{13}\cap A_{43}}\) oznacza zbiór tych ubiorów, w których nie wystąpią suknie o numerach 13 i 43. Dlatego potrzebujemy teraz zasady włączeń i wyłączeń, która pozwala właśnie obliczać moc sumy zbiorów, które nie są parami rozłączne.

Spróbuj po tych wskazówkach, a w razie kłopotów pytaj dalej.

[Elas]

Ok, zrozumiałem czemu musi być zasada włączeń i wyłączeń, oraz, że najlepiej to zrobić jako suriekcje. Ten podrzucony temat mi sporo pomógł, dzięki

Doszedłem do momentu następującego:
Wszystkich możliwości założenia sukienek jest \(\displaystyle{ 80^{365}}\)
Problem jest taki, że trzeba wyłączyć te sytuacje, w których funkcja suriekcją nie jest.
Doszedłem do czegoś takiego: \(\displaystyle{ \sum_{i=0}^{365} (-1)^{i} {365 \choose i}(365-i) ^{80}}\)
Nie wiem jednak, czy jest to prawidłowe (znalazłem wzór na suriekcje i wrzuciłem liczby do niego :d), a już tym bardziej nie mam pojęcia, jak to wyliczyć, poza żmudnym liczeniem (w teorii mógłbym napisać do tego program, coby mi pozwoliło wzór zapamiętać... ale to później ).

[Majeskas]

Błąd polega na tym, że wstawiłeś te liczby odwrotnie. Gorsza sprawa, że to pokazuje, że nie wiesz, skąd się wziął ten wzór. Byłoby znacznie pożyteczniej, gdybyś spróbował rozwiązać to zadanie od podstaw, stosując tylko wzór włączeń i wyłączeń i wskazówki, które Ci podałem. Właśnie dlatego nie rzuciłem Ci wzoru na liczbę suriekcji. Ja nie widzę sensu w uczeniu się matematyki w taki sposób, że "wezmę jakiś wzór, bo ktoś mówił, że jest dobry, i może zadziała". Można rozwiązać to zadanie, nie znając słowa "suriekcja". Wystarczy tylko trochę pomyśleć.

Jeśli chodzi o sam rezultat, który już obaj znamy, to lepiej się tego nie da zapisać i właśnie taki wynik jest oczekiwany. Można sobie napisać program, który to obliczy (albo choćby skorzystać z Wolframa Alphy), ale to już inna rzecz.

[Elas]

\(\displaystyle{ \sum_{i=0}^{80} (-1)^{i} {80 \choose i}(80-i) ^{365}}\)

Cóż, nie mogę Ci przyznać racji.
Z tego co rozumiem - iteracji będzie 80, ponieważ mamy 80 sytuacji, w których któraś sukienka nie zostanie wybrana.

Tym samym wynik całościowy to: \(\displaystyle{ 80^{365} - \sum_{i=0}^{80} (-1)^{i} {80 \choose i}(80-i) ^{365}}\)

[Majeskas]

Nie wiem, w której kwestii nie możesz mi przyznać racji, ale nie jest mi to niezbędne do szczęścia. Nie wiem też, co dla Ciebie znaczy słowo "iteracja", bo chyba co innego niż dla mnie, dlatego nie jestem w stanie zweryfikować tego, co rozumiesz.

Wynik całościowy to: \(\displaystyle{ \sum_{i=0}^{80}(-1)^i{80\choose i}(80-i)^{365}}\)

Chcemy obliczyć liczbę suriekcji ze zbioru \(\displaystyle{ 365}\)-elementowego w zbiór \(\displaystyle{ 80}\)-elementowy, dlatego - zgodnie ze wzorem - jest właśnie tak. Podejście, które Ci proponowałem, polegało na odjęciu od liczby wszystkich funkcji liczbę tych funkcji, które nie są suriekcjami. Tak więc skrzyżowałeś sposób rozumowania, który próbowałem podsunąć, z gotowym wzorem na to, co trzeba.