Zasada włączania i wyłączania.

[ugabuga333]

Z przyjęcia, na którym było \(\displaystyle{ 10}\) par małżeńskich jego uczestnicy wychodzą parami ( kobieta z mężczyzną ). Ile jest możliwości, że żaden mężczyzna nie wychodzi ze swoją żoną ?

[sieniaf]

Rozpatrzmy #1 mężczyznę, może on wybrać 1 z 9 na 10 partnerek, #2 mężczyzna również nie może wybrać swojej żony, jednak on dobiera sobie partnerkę już z puli 9 partnerek, dlatego wybiera 1 z 8 na 9 partnerek, analogicznie dobiera sobie partnerkę mężczyzna 3,4,5,6,7,8. #9 mężczyzna wybiera z puli 2 partnerek, gdzie 1 z nich to jego żona, więc tak naprawdę może dokonać, tylko 1 wyboru, ostatni mężczyzna wychodzi z ostatnią partnerką, więc też może wybrać, tylko w 1 sposób. Zatem ilość wszystkich par, w której żaden mężczyzna nie wychodzi z żoną wyraża się liczbą:
\(\displaystyle{ C_{9}^{1}C_{8}^{1}C_{7}^{1}C_{6}^{1}C_{5}^{1}C_{4}^{1}C_{3}^{1}C_{2}^{1}=9!}\)

[norwimaj]

sieniaf, tytuł wątku nie jest przypadkowy. Skąd wiesz że drugi mężczyzna ma do wyboru \(\displaystyle{ 9}\) partnerek? Tak jest tylko wtedy gdy pierwszy wybierze żonę drugiego. W przeciwnym wypadku drugi ma już tylko \(\displaystyle{ 8}\) partnerek do wyboru. Jeśli chcesz dalej brnąć w rozpatrywanie przypadków, to życzę wytrwałości.

[ugabuga333]

Umie ktoś to zrobić z zasady włączania i wyłączania ? ;/

[sieniaf]

sieniaf, tytuł wątku nie jest przypadkowy. Skąd wiesz że drugi mężczyzna ma do wyboru \(\displaystyle{ 9}\) partnerek? Tak jest tylko wtedy gdy pierwszy wybierze żonę drugiego.

#2 mężczyzna ma do wyboru 8 partnerek, #1 mężczyzna może wybrać dowolną żonę prócz swojej, nie tylko żonę #2.

W przeciwnym wypadku drugi ma już tylko \(\displaystyle{ 8}\) partnerek do wyboru

mógłbyś to uzasadnić?

Jeśli chcesz dalej brnąć w rozpatrywanie przypadków, to życzę wytrwałości

Wystarczy rozpatrzyć 2-3 przypadki, żeby zauważyć zależność.

[Tatar]

To nie jest zasada włączania i wyłączania, tylko prostacka reguła mnożenia. Na pocieszenie wstawiam wam deltę. \(\displaystyle{ \Delta}\)

[norwimaj]

Wystarczy rozpatrzyć 2-3 przypadki, żeby zauważyć zależność.

To znajdź tę zależność.

Umie ktoś to zrobić z zasady włączania i wyłączania ? ;/

Niech \(\displaystyle{ A_i}\) (dla \(\displaystyle{ i=1,2,\ldots10}\)) będzie zbiorem tych przyporządkowań, w których \(\displaystyle{ i}\)-ty mężczyzna wychodzi z \(\displaystyle{ i}\)-tą kobietą. Chcemy policzyć

\(\displaystyle{ \left|X\setminus \bigcup_{i=1}^{10} A_i\right|}\),

gdzie \(\displaystyle{ X}\) to zbiór wszystkich przyporządkowań.


Dalej już chyba wiadomo co robić?

-- 16 kwi 2012, o 23:47 --

Tatar dziękuję, piękna delta.

[sieniaf]

To znajdź tę zależność.

Przedstawiłem ją w moim pierwszym poście, pewnie się mylę, ale nie wiem gdzie w moim rozumowaniu jest błąd, byłbym wdzięczny, gdyby ktoś mi go wskazał.

[Tatar]

Prosze bardzo sieniaf

[norwimaj]

Pierwszy mężczyzna może wybrać jedną z dziewięciu kobiet - z tym się zgadzam.

Drugi mężczyzna może wybrać każdą z wyjątkiem swojej żony i kobiety wybranej przez pierwszego. Żona drugiego oraz kobieta wybrana przez pierwszego to może być ta sama osoba albo mogą to być dwie różne osoby. Dlatego drugi ma do wyboru albo dziewięć, albo osiem kobiet. W związku z tym nie można zastosować reguły mnożenia.

[sieniaf]

Pierwszy mężczyzna może wybrać jedną z dziewięciu kobiet - z tym się zgadzam.

Drugi mężczyzna może wybrać każdą z wyjątkiem swojej żony i kobiety wybranej przez pierwszego. Żona drugiego oraz kobieta wybrana przez pierwszego to może być ta sama osoba albo mogą to być dwie różne osoby. Dlatego drugi ma do wyboru albo dziewięć, albo osiem kobiet. W związku z tym nie można zastosować reguły mnożenia.

Dzięki.

[mat_61]

Proponuję taki sposób doboru par (nie widzę błędu w poniższym rozumowaniu ale myślę, że ktoś to jeszcze zweryfikuje):

Zaczyna mąż z pierwszej pary \(\displaystyle{ M_{1}}\) i wybiera dowolną spośród pań z wyjątkiem swojej żony \(\displaystyle{ K_{1}}\), czyli ma \(\displaystyle{ 9}\) możliwości wyboru. Powiedzmy, że wybiera panią \(\displaystyle{ K_{i}}\)

Następnie mąż \(\displaystyle{ M_{i}}\) czyli pani wybranej przez \(\displaystyle{ M_{1}}\) wybiera dowolną spośród pozostałych pań, czyli ma \(\displaystyle{ 8}\) możliwości. Powiedzmy, że wybiera panią \(\displaystyle{ K_{j}}\)

Następnie mąż \(\displaystyle{ M_{j}}\) czyli pani wybranej przez \(\displaystyle{ M_{i}}\) wybiera dowolną spośród pozostałych pań, czyli ma \(\displaystyle{ 7}\) możliwości. Powiedzmy, że wybiera panią \(\displaystyle{ K_{k}}\)

itd.

Wszystkich możliwych do utworzenia par takich, że mąż nie jest w parze ze swoją żoną jest więc \(\displaystyle{ 9!}\)

[norwimaj]

mat_61, jeśli \(\displaystyle{ M_i}\) wybierze \(\displaystyle{ K_1}\), to w Twoim rozumowaniu następnie prawo wyboru ma \(\displaystyle{ M_1}\), a przecież on już wybierał.


Dokończę sposób z regułą włączeń i wyłączeń, żeby był napisany poprawny wynik. To ułatwi weryfikację kolejnych sposobów rozwiązania.

\(\displaystyle{ \left|X\setminus \bigcup_{i=1}^{10} A_i\right|=\\\\=
\left|X\right|- \left|\bigcup_{i=1}^{10} A_i\right| =
\left|X\right|- \sum_{1\le i \le 10} \left|A_i\right| + \sum_{1\le i_1<i_2 \le 10} \left|A_{i_1}\cap A_{i_2}\right| +\\\\- \sum_{1\le i_1<i_2<i_3 \le 10} \left|A_{i_1}\cap A_{i_2}\cap A_{i_3}\right| +
\ldots + \left|A_1\cap A_2\cap \ldots \cap A_{10}\right|=\\\\
=\left|X\right|- 10\left|A_1\right| +\binom{10}2 \left|A_1\cap A_2\right| - \binom{10}3 \left|A_1\cap A_2\cap A_3\right| +
\ldots + \left|A_1\cap A_2\cap \ldots \cap A_{10}\right|=\\\\
=10!- 10\cdot 9! +\binom{10}2 \cdot 8! - \binom{10}3 \cdot 7! +
\ldots + 0! =
10!\cdot \left(\frac1{0!}-\frac1{1!}+\frac1{2!}-\frac1{3!}+\ldots+\frac1{10!}\right) =\\\\= \left\lceil \frac{10!}e \right\rceil = 1334961}\)

[mat_61]

Nie wiem jak mogłem tego nie zauważyć ale rzeczywiście moja propozycja jest do ... niczego.

[fon_nojman]

Mam pytanie do przedostatniej równości

\(\displaystyle{ \ldots= 10!\cdot \left(\frac1{0!}-\frac1{1!}+\frac1{2!}-\frac1{3!}+\ldots+\frac1{10!}\right) = \left\lceil \frac{10!}e \right\rceil =\ldots}\)

jak ją uzasadnić?