Podzbiory

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11266
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3143 razy
Pomógł: 747 razy

Podzbiory

Post autor: mol_ksiazkowy »

Wzynaczyc ilosc tych podzbiorow zbioru X= {1,....,2n} ktore"
1) nie zawieraja trzech kolejnych liczb
2) zawieraja dwie liczby rozniace sie o n
3) zawieraja wiecej liczb parzystych
niz nieparzystych
jovante
Użytkownik
Użytkownik
Posty: 204
Rejestracja: 23 cze 2007, o 14:32
Płeć: Mężczyzna
Lokalizacja: Siedlce
Pomógł: 56 razy

Podzbiory

Post autor: jovante »

1) \(\displaystyle{ \sum_{m=0}^{n} \sum_{k=0}^{m} {m \choose k} {2n-m-k+1 \choose m}}\) przy czym \(\displaystyle{ {x \choose y} =0}\) dla \(\displaystyle{ y>x}\)

Najłatwiej zrozumieć ten wzór zwracając uwagę, że zadanie sprowadza się do policzenia ile jest ciągów o konfiguracjach _XOXO...OXOX_, gdzie X to jedna lub dwie 1 (oznacza występujące w podzbiorze liczby), O to co najmniej jedna 1 (oznacza nie występujące w wybranym podzbiorze liczby), _ to zero lub więcej 1 (o znaczeniu jak przy O). Drugi człon we wzorze bierze się ze wzoru na kombinacje z powtórzeniami.

2) \(\displaystyle{ \sum_{i=1}^{n} (-1)^{i+1} {n \choose i} 2^{2(n-i)}}\)

To idzie wprost ze wzoru włączeń i wyłączeń.

3) \(\displaystyle{ \frac{2^{2n}- \sum_{i=0}^{n} {n \choose i}^2}{2}}\)

Tutaj z kolei od wszystkich podzbiorów odejmuję te, które mają jednakową liczbę elementów parzystych i nieparzystych i otrzymany wynik dzielę przez dwa (bo wśród pozostałych podzbiorów jest tyle samo takich, które zawierają więcej liczb parzystych od nieparzystych i takich, które zawierają więcej liczb nieparzystych od parzystych).
ODPOWIEDZ