7 przyjaciół, zapraszanie na kolację

lidka95 · Post autor: **lidka95** » 8 mar 2015, o 16:10

Pewien człowiek ma 7 przyjaciół. Zbadać na ile sposobów może zapraszać po 3 z nich na kolację przez 7 kolejnych dni tak, aby każdy z nich został zaproszony co najmniej raz.

Czy ktoś mógłby pomóc mi z tym zadaniem?

Medea 2 · Post autor: **Medea 2** » 8 mar 2015, o 17:58

Chyba przyda się wzór włączeń i wyłączeń. Wszystkich możliwości jest:

\(\displaystyle{ {7 \choose 3}^7,}\)

bo z siedmiu wybieramy trzech przez siedem dni. Od tego odejmij te wybory, gdzie wybierane było tylko sześć, a nie siedem osób (łącznie), dodaj te, gdzie zaproszone zostało pięć osób, i tak dalej.

lidka95 · Post autor: **lidka95** » 8 mar 2015, o 21:26

A czy można tak?

\(\displaystyle{ A _{i}}\) - i osób nie dostało zaproszenia

\(\displaystyle{ \left| A _{i}\right|= {7 \choose i} {7 - i \choose 3} ^{7}}\), gdzie pierwszy składnik to wybranie osób nie do zaproszenia, a drugi - rozkład zaproszonych na kolejne dni.

Kartezjusz · Post autor: **Kartezjusz** » 8 mar 2015, o 21:38

Koncepcja dobra, ale w zbiorze włączeń i wyłączeń są części wspólne. Tu jak myślisz, jaka będą ich liczebność?

lidka95 · Post autor: **lidka95** » 8 mar 2015, o 21:41

Właśnie z tym mam problem, dlatego próbowałam inaczej.

arek1357 · Post autor: **arek1357** » 8 mar 2015, o 22:46

Suriekcje:

\(\displaystyle{ S( {7 \choose 3},7 )}\)

szachimat · Post autor: **szachimat** » 9 mar 2015, o 00:02

Nie wiem, czy moje rozumowanie będzie dobre, ale najwyżej ktoś je skoryguje.
Ponieważ każda z siedmiu osób A, B, C, D, E, F, G musi się pojawić na kolacji któregoś dnia, to zaproszenia na kolejne dni tygodnia mogą być rozdzielone na \(\displaystyle{ 7!}\) sposobów.

Gdyby gospodarz zapraszał tylko jedną osobę na jeden wieczór, wśród tych układów żadna z osób nie zostałaby pominięta.
Przykładowo jeden z naszych układów dla kolejnych dni tygodnia jest następujący:
PPP WWW SSS CCC PPP SSS NNN
A_ _ F_ _ G_ _ E_ _ D_ _ C_ _ B_ _(nie wiem jak mi wyjdzie ten zapis po wysłaniu).
Przeczytalibyśmy go w sposób następujący: osoba A dostała zaproszenie na poniedziałek, osoba F na wtorek, G na środę itd.

A zatem biorąc pod uwagę ten układ musimy już teraz w dowolny sposób wybrać dwie osoby z sześciu na poniedziałek (bo już bez A), dwie z sześciu na wtorek (bo już bez F) itd.

Ale w tych układach coś się dubluje, a zatem przez coś trzeba będzie jeszcze dzielić. Może komuś uda się pociągnąć dalej moją koncepcję, ewentualnie ją skorygować.

Medea 2 · Post autor: **Medea 2** » 9 mar 2015, o 06:41

arek1357 pisze:Suriekcje:

\(\displaystyle{ S( {7 \choose 3},7 )}\)

Mógłbyś wyjaśnić to dokładniej? Chodzi o surjekcje ze zbioru trójek na zbiór osób? Myślałam, że myślimy w inną stronę: każdy dzień tygodnia dostaje trójkę.

arek1357 · Post autor: **arek1357** » 9 mar 2015, o 13:45

Suriekcje zbioru trójek na zbiór dni!

szachimat · Post autor: **szachimat** » 9 mar 2015, o 14:29

Czy jest ktoś, kto ma wynik i może go podać?

arek1357 · Post autor: **arek1357** » 10 mar 2015, o 13:39

A nie będzie tak:

\(\displaystyle{ {7 \choose 3}^7- {7 \choose 1} {6 \choose 3}^7+ {7 \choose 2} {5 \choose 3}^7- {7 \choose 3} {4 \choose 3}^7+ {7 \choose 4} {3 \choose 3}^7=55588723470}\)

Korzystając z zasady włączeń i wyłączeń.

Medea 2 · Post autor: **Medea 2** » 10 mar 2015, o 15:04

No chyba jednak nie :/ Gdybyśmy zamienili u nas \(\displaystyle{ (7,3)}\) na \(\displaystyle{ (5,2)}\) w oczywisty sposób, to Twój wzór daje \(\displaystyle{ 61120}\), a poprawna odpowiedź to \(\displaystyle{ 63540}\). Wzór włączeń i wyłączeń nie urywa się za pierwszym wyrazem.

arek1357 · Post autor: **arek1357** » 10 mar 2015, o 20:52

Coś mi się twój wynik nie podoba przeanalizowałem to i powinno wyjść znacznie więcej zauważ że:
ilość wszystkich możliwości to:

\(\displaystyle{ {7 \choose 3}^7=64 339 296 875}\)

Więc jeśli każdy jest przynajmniej raz to wynik będzie mniejszy ale nie aż o tyle

szachimat · Post autor: **szachimat** » 10 mar 2015, o 20:58

A może ktoś potrafi napisać program na komputer, który poda wynik. Bo zadanie jest bardzo logiczne, ale rozwiązanie nie jest takie banalne, a ciekawi mnie do jakiego wyniku musimy dojść.

arek1357 · Post autor: **arek1357** » 11 mar 2015, o 08:27

Sprawdzałem ten mój wzór powyższy dla kilku możliwości.
np:

czworo ludzi, trzy dni i w każdym dniu zapraszane są dwie osoby problem ten sam rozwiązanie:

\(\displaystyle{ {4 \choose 2}^3-4 {3 \choose 2}^3 + {4 \choose 2} {2 \choose 2}^3=114}\)

Liczyłem na piechotę i się zgadza wynik!

Podobnie:

czterech ludzi, trzy dni, w każdym dniu zapraszanych jest trzy osoby łatwo na piechotę wyliczyć
możliwości 60

\(\displaystyle{ {4 \choose 3}^3-4 {3 \choose 3}^3=60}\)

Pięć ludzi, trzy dni, w każdym dniu zapraszanych jest trzy osoby też działa!