Egzamin z kombinatoryki

[anka0501]

Witam ! Mam tu do rozwiazania 5 zad z egzaminu. Kompletnie nie rozumiem tego przedmiotu, nie wiem jak sie do tego zabrac. Gdyby ktos raczyl je rozwiazac i dodatkowo wytlumaczyl jak do tego doszedl, bylabym wdzieczna.
1. Udowodnic KOMBINATORYCZNIE rownosc dla \(\displaystyle{ n \ge 3}\)
\(\displaystyle{ \sum_{k=1}^{n} ( 2 ^{n-k} -1 = 2^{n} -(n+1)}\)

2. Ania lubi kolor pik, Bartek karo, a Czesław i Danusia lubią zarówno kier jak i trefl. Ile jest mozliwych rozwiazan w brydzu dla tych 4 osob, aby co najmniej jedna z tych osob otrzymala karty jednego koloru i to koloru, ktory lubi.

3. Znaleźć liczbe rozwiazan w liczbach calkowitych nieujemnych rownania :
\(\displaystyle{ x _{1} +...+ x_{4} =30}\)
takich ze:
a) dla kazdego \(\displaystyle{ i=1...4 \ \ x_{i} >i}\)
b) dla kazdego \(\displaystyle{ i=1...4 \ \ x_{i} <2i}\)

4. Sposrod 9 osob gdzie i-ta osoba ma i lat (\(\displaystyle{ i \in \{1,2...10\}}\)) wybieramy grupe co najmniej 3 osob. Udowodnij, ze istnieje co najmniej 20 takich grup, w ktorych suma wieku osob jest taka sama.

5. Wyznaczyc jawny wzor na n-ty wyraz ciagu \(\displaystyle{ \left( a_{n} \right)}\) wyznaczonego przez nastepujace warunki rekurencyjne
\(\displaystyle{ a_{0} =0 \\
a_{1} =4 \\
a_{n} =3 a_{n-2} -2 a_{n-1}}\)

[miodzio1988]

Gotowca nie będzie . Przykro mi.
Od najłatwiejszego zaczniemy. Jak się gra w Brydża wiesz? Po ile kart dostaje każdy zawodnik?

[anka0501]

Nigdy nie gralam ...13 ?

[miodzio1988]

Zasady brydża -> Google.

Nie uważasz, że to powinna być pierwsza rzecz, którą sprawdzasz widząc takie zadania? Sprawdź i dopiero nam powiedz.

[anka0501]

Sprawdziłam z tali 52 kart kazdy z 4 graczy uzyskuje 13 kart

[miodzio1988]

aby co najmniej jedna z tych osob otrzymala karty jednego koloru i to koloru, ktory lubi.

To najpierw napisz nam na ile sposób dowolnie możemy rozdać te karty?

[anka0501]

Nawiazujac do mojego pierwszego postu, kombinatoryka jest moja pieta Achillesowa. Prosze sie nie smiac jak przeczytasz glupote.

Jesli mamy 4 osoby i 1 z nich dostanie 13 kart tego samego koloru, czyli mamy:
\(\displaystyle{ x_1+13+x_2+\,\cdots\,+x_4=52\\ x_1+\,\cdots\,+x_4=39\\ \\ \frac{39+4-1}{4-1}}\)
zatem mamy 42 po 3-- 4 sie 2011, o 20:50 --zle napisalane powinien byc nawias zamist kreski ulamkowej

[miodzio1988]

Najpierw masz napisać ogólnie ile takich sposobów jest. Wszystkich

[anka0501]

Ma byc 52 po 13

[miodzio1988]

Brawo.

aby co najmniej jedna z tych osob otrzymala karty jednego koloru i to koloru, ktory lubi.

No dobra. To teraz będziemy się bawić w sumowanie przypadków.

Ania lubi kolor pik

No to jak można rozdać te kwarty tak, żeby Ania otrzymała same piki, a reszta ( póki co) dowolnie.

[anka0501]

Ania ma 13 po 13 , bartek 39 po 13, czesiek 26 po 13 i danka 13 po 13
zatem bedzie 39 po 13 razy 26 po 13

[miodzio1988]

I tak sumujesz te przypadki pamiętając o tym, że możesz niektóre kombinacje dodawać kilka razy. Pomyśl które. I tyle. Jakie są jeszcze problemy?

[anka0501]

Zatem bedzie :ania pik \(\displaystyle{ {39 \choose 13}\cdot {26 \choose 13}}\)
bartek karo -//-
czesiek kier -//-
czesiek trefl-//-
danka kier -//-
danka trefl -//-
I teraz rozumie sie, ze od \(\displaystyle{ {52 \choose 13}}\) mam odjac te wszystkie zsumowane przypadki, czy tez w tych przypadkach mam uwzglednic , ze 2, 4 osoby dostaly wszystkie karty koloru, ktory lubia ?
Jesli tak to byloby
\(\displaystyle{ 6 \cdot {39 \choose 13} \cdot {26 \choose 13}+ 11\cdot {26 \choose 13}+2}\)
i od \(\displaystyle{ {52 \choose 13}}\)odejmujemy ta sume-- 9 sie 2011, o 16:40 --Dobrze czy zle ? No i przydałoby sie zajac zad 1

[strzyga]

czy mógłby ktoś sprawdzić to rozwiązanie?

[Kryftof]

A może tak?
Ania dostaje karty koloru pik a reszta dowolnie
\(\displaystyle{ |A|={39\choose 13}{26\choose 13}}\)
Bartek dostaje karty koloru karo a reszta dowolnie
\(\displaystyle{ |B|={39\choose 13}{26\choose 13}}\)
Czeslaw i Danusia dostaja karty koloru tylko trefl i tylko kier kier a reszta dowolnie
\(\displaystyle{ |C|=4{39\choose 13}{26\choose 13}}\)
Ania dostaje pik, a Bartek karo reszta dowolnie
\(\displaystyle{ |A \cap B|={26\choose 13}}\)
Ania Czesław i Danusia dostają kolory
\(\displaystyle{ |A \cap C|=5{26\choose 13}}\)
Bartek Czesław i Danusia dostają kolory
\(\displaystyle{ |B \cap C|=5{26\choose 13}}\)
Wszyscy dostają kolory jakie lubią
\(\displaystyle{ |A \cap B \cap C|=4}\)
I teraz z zasady włączeń i wyłączeń mamy
\(\displaystyle{ |A \cup B \cup C|=6{39\choose 13}{26\choose 13}-11{26\choose 13}+4}\)

Taa juz wiem gdzie miałem bład na egzaminie ja poprostu policzyłem przypadki gdzie Czesław i Danusia mają w talii kier albo trefl a mogą mieć karty jednego koloru