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
Podzbiory
-
- Użytkownik
- Posty: 204
- Rejestracja: 23 cze 2007, o 14:32
- Płeć: Mężczyzna
- Lokalizacja: Siedlce
- Pomógł: 56 razy
Podzbiory
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).
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).