Liczba wszystkich podzbiorów zbioru skończonego

Można obliczyć, ile jest wszystkich podzbiorów pewnych zbiorów skończonych.

  • pewien zbiór dwuelementowy ma 22=4 podzbiory,

  • pewien zbiór czteroelementowy ma 24=16 podzbiorów,

  • pewien zbiór pięcioelementowy ma 25=32 podzbiory,

  • pewien podzbiór dziewięcioelementowy ma 29=512 podzbiorów.

Ustalając liczbę podzbiorów zauważaliśmy, że w stosunku do każdego elementu zbioru możemy na dwa sposoby podjąć decyzję o jego wyborze do tworzonego podzbioru.

Przykład 1

Rozpatrzmy teraz zbiór A=a1,a2,...,an, który ma n elementów. Dowolny podzbiór zbioru A tworzymy, podejmując decyzję, czy każdy z kolejnych elementów zbioru A: a1,a2,...,an należy do tego podzbioru, czy nie należy. Można to zrobić na 22...2n czynników=2n sposobów.
Zatem liczba wszystkich podzbiorów zbioru A, który ma n elementów, jest równa 2n.

Liczba kombinacji

W przykładach prezentowanych w tym rozdziale często spotykaliśmy się z koniecznością obliczenia, na ile sposobów możemy z ustalonego zbioru wybrać podzbiór o konkretnej liczbie elementów.

Przykład 2

Rozpatrzmy zbiór A=a1,a2,...,an, który ma n elementów. Wtedy, jak to już pokazywaliśmy w rozwiązaniach przykładów tego rozdziału:

  • jest jeden podzbiór zbioru A, do którego nie wybierzemy żadnego elementu ze zbioru A (tym podzbiorem jest zbiór pusty),

  • jest jeden podzbiór zbioru A, do którego wybierzemy każdy element zbioru A (tym podzbiorem jest cały zbiór A),

  • jest n wszystkich podzbiorów jednoelementowych zbioru A,

  • jest nn-12wszystkich podzbiorów dwuelementowych zbioru A.

Rozumując podobnie jak w rozwiązaniu metodą dopełniania podzbiorów do całego zbioru i zasadą równoliczności, stwierdzimy też, że

  • jest n wszystkich podzbiorów (n-1)-elementowych zbioru A,

  • jest nn-12 wszystkich podzbiorów (n-2)-elementowych zbioru A.

liczba k–elementowych podzbiorów zbioru n–elementowego
Definicja: liczba k–elementowych podzbiorów zbioru n–elementowego

Rozpatrzmy zbiór A=a1,a2,...,an, który ma (n1) elementów.
Symbolem nk oznaczamy liczbę jego wszystkich podzbiorów k–elementowych (k0kn) .
Zapis symboliczny nk odczytujemy „n po k”, stąd np.:

  • 52 czytamy „pięć po dwa”,

  • 71 czytamy „siedem po jeden”,

  • 60 czytamy „sześć po zero”.

Stosując to oznaczenie, stwierdzimy, że:

n0=nn=1
n1=nn-1=n
n2=nn-2=nn-12,

gdy n2
W szczególności:

52=542=10,53=10,
71=7,76=7,
 60=66=1

Rozszerza się też (z czego my nie będziemy korzystać) stosowanie tego symbolu na:

  • podzbiór pusty zbioru pustego, przyjmując 00=1,

  • przypadek, gdy k>n, wtedy przyjmujemy nk=0.

iyyZQTCUNb_d5e363

Kombinacje

k‑elementowa kombinacja zbioru n‑elementowego
Definicja: k‑elementowa kombinacja zbioru n‑elementowego

Każdy k-elementowy podzbiór zbioru n-elementowego (0k n) nazywa się zwyczajowo k-elementową kombinacją zbioru n-elementowego.

Pokażemy, że liczba wszystkich kelementowych podzbiorów, które można wybrać ze zbioru A=a1,a2,...,an liczącego n elementów, jest równa n!k!n-k!. Przypomnijmy, że przez nk umówiliśmy się oznaczać liczbę wszystkich możliwych kelementowych podzbiorów zbioru A.

Dla dowodu zauważmy, że liczba wszystkich możliwych kelementowych ciągów utworzonych z różnych elementów zbioru A jest z jednej strony równa

nn-1n-2...n-k+1k czynników=n!n-k!

a z drugiej strony – jest równa

kk-1k-2...1k czynnikównk

ponieważ w każdym z k–elementowych podzbiorów zbioru A możemy ustalić kolejność elementów na

k!=kk-1k-2...1k czynników

sposobów.
Otrzymujemy więc równość

n!n-k!=k!nk

stąd

nk=n!k!n-k!

Na podstawie spostrzeżenia poczynionego powyżej mamy twierdzenie.

liczba k‑elementowych kombinacji zbioru n‑elementowego
Twierdzenie: liczba k‑elementowych kombinacji zbioru n‑elementowego

Liczba nk wszystkich k-elementowych kombinacji zbioru n-elementowego jest równa

n!k!n-k!=nn-1n-2...n-k+1kk-1k-2...1.
Przykład 3

Pokażemy kilka zastosowań twierdzenia o liczbie kombinacji.

  1. Do turnieju koszykówki, rozgrywanego systemem „każdy z każdym” (bez rewanżów), zgłosiło się 12 drużyn.
    Liczba wszystkich meczów do rozegrania w tym turnieju jest zatem równa 122, czyli 12112=66.

  2. Z pudełka, w którym znajduje się 20 kul ponumerowanych od 1 do 20 mamy wylosować 3 kule.
    Każdy wynik takiego losowania to trzyelementowy podzbiór zbioru dwudziestoelementowego, zatem liczba sposobów, na które można to zrobić, jest równa 203. Ta liczba jest więc równa20!3!17!=201918321=1140.

  3. Na okręgu zaznaczono 11 różnych punktów. Obliczamy, ile jest wszystkich czworokątów wypukłych, których wierzchołkami są punkty wybrane spośród tych zaznaczonych.
    Ponieważ wybierając dowolne cztery z tych jedenastu punktów na dokładnie jeden sposób, połączymy je tak, aby otrzymać kolejne boki czworokąta wypukłego, więc szukana liczba wszystkich czworokątów to 114, co jest równe11!4!7!=1110984321=330.

  4. Spośród uczniów 37-osobowej klasy należy wybrać 5-osobową delegację.
    Można to zrobić na 375 sposobów, co jest równe 37!5!32!=373635343354321=435897 (to prawie pół miliona sposobów).

  5. W pewnej grze losowej należy wybrać 6 liczb ze zbioru {1, 2, 3, ..., 49}. Liczba sposobów, na które można tego dokonać jest równa 496, czyli 49!6!43!=494847464544654321=13983816 (to liczba bliska 14 milionom).

  6. W rozdaniu brydżowym gracz otrzymuje 13 kart wybranych losowo z talii 52 kart. Liczba wszystkich układów kart możliwych do otrzymania przez brydżystę jest więc równa 5213, czyli 52!13!39!=5251504948474645444342414013121110987654321=635013559600 (to ponad 635 miliardów układów).

Przykład 4

Rozpatrzmy równanie

x1+x2+x3+x4+x5+x6=10

gdzie każda z liczb x1,x2,x3,x4,x5,x6 jest całkowita i nieujemna.
Wykażemy, że jest 3003 wszystkich rozwiązań tego równania.

Skorzystamy z pomysłu przedstawionego w Uwadze do podpunktu a) przykładu 13.
Rozpatrzmy pomocniczo wszystkie wyniki piętnastokrotnego rzutu monetą, w których wypadło dokładnie 10 orłów. Oznaczmy przez:
x1 – liczbę orłów uzyskanych w kolejnych rzutach do momentu, w którym wyrzucono pierwszą reszkę,
x2 – liczbę orłów uzyskanych w kolejnych rzutach od momentu, w którym wyrzucono pierwszą reszkę, do momentu, w którym wyrzucono drugą reszkę,
x3 – liczbę orłów uzyskanych w kolejnych rzutach od momentu, w którym wyrzucono drugą reszkę, do momentu, w którym wyrzucono trzecią reszkę,
x4 – liczbę orłów uzyskanych w kolejnych rzutach od momentu, w którym wyrzucono trzecią reszkę, do momentu, w którym wyrzucono czwartą reszkę,
x5 – liczbę orłów uzyskanych w kolejnych rzutach od momentu, w którym wyrzucono czwartą reszkę, do momentu, w którym wyrzucono piątą reszkę,
x6 – liczbę orłów uzyskanych w kolejnych rzutach od momentu, w którym wyrzucono piątą reszkę.
Wtedy

  • każdemu wynikowi takiego rzutu monetą odpowiada dokładnie jeden ciąg x1,x2,x3,x4,x5,x6,

  • każdemu ciągowi x1,x2,x3,x4,x5,x6 odpowiada jeden wynik piętnastokrotnego rzutu monetą, w którym wypadło dokładnie 10 orłów.

Ponieważ jest 1510=15!10!5!=151413121154321=3003 wszystkich wyników piętnastokrotnego rzutu monetą, w których wypadło dokładnie 10 orłów, więc również tyle jest rozwiązań równania x1+x2+x3+x4+x5+x6=10 w nieujemnych liczbach całkowitych.
Rozumując podobnie, można też wykazać, że równanie x1+x2+x3+...+xn=k, gdzie k jest dodatnią liczbą całkowitą, a każda z liczb x1,x2,x3,...,xn jest całkowita i nieujemna, ma dokładnie n+k-1k rozwiązań.

iyyZQTCUNb_d5e542

Współczynniki dwumianowe, wzór dwumianowy Newtona

Przykład 5

Wykażemy, że dla dowolnej liczby rzeczywistej x:
x+14=x4+4x3+6x2+4x+1

  • sposób I (algebraiczny)
    Zapisujemy równość
    x+14=x+1x+1x+1x+1.
    Po wymnożeniu wyrażeń zapisanych w nawiasach po prawej stronie tej równości i pogrupowaniu wyrazów podobnych otrzymamy wyrażenie (wielomian zmiennej x), w którym wystąpią jednomiany zmiennej x.
    Czynność taką można wykonać, korzystając ze wzoru na sześcian sumy:
    x+14=x+1x+1x+1x+1=x+13x+1=x3+3x2+3x+1x+1==x3+3x2+3x+1x+x3+3x2+3x+11= x4+3x3+3x2+x+x3+3x2+3x+1=x4+4x3+6x2+4x+1lub ze wzoru skróconego mnożenia na kwadrat sumy:
    x+14=x+122=x2+2x+12=x2+2x+12=x22+2x22x+1+2x+12==x4+4x3+2x2+4x2+4x+1=x4+4x3+6x2+4x+1.

  • sposób II (kombinatoryczny)
    Zauważmy, że mnożąc wyrażenia wybierane z każdego z kolejnych nawiasów iloczynu
    x+1x+1x+1x+1, dostaniemy za każdym razem mnożenie czterech czynników. Wynikiem każdego takiego mnożenia jest wyrażenie xk, gdzie k jest równe 4, 3, 2, 1 lub 0. Wykonajmy więc wszystkie możliwe mnożenia wyrażeń wybieranych z kolejnych nawiasów – możemy to zrobić na 24=16 sposobów.
    Rozróżniamy pięć przypadków:

  1. ze wszystkich nawiasów wybraliśmy można to zrobić na jeden sposób, a w wyniku otrzymamy x4, co można też zapisać jako 44x410,

  2. z dokładnie trzech nawiasów wybraliśmy wtedy z dokładnie jednego nawiasu wybraliśmy 1, a więc można to zrobić na 4 sposoby. Zatem łącznie otrzymamy 4x3, co można też zapisać jako 43x311,

  3. z dokładnie dwóch nawiasów wybraliśmy x – można to zrobić na 432=6 sposobów. Łącznie otrzymamy więc 6x2, co można też zapisać jako 42x212,

  4. z dokładnie jednego nawiasu wybraliśmy można to zrobić na 4 sposoby. Łącznie otrzymamy więc 4x, co można też zapisać jako 41x113,

  5. z żadnego z nawiasów nie wybraliśmy można to zrobić na 1 sposób. Wtedy z każdego z nawiasów musimy wybrać jedynkę, więc w wyniku mnożenia otrzymamy 1, co można też zapisać jako 40x014.
    Ostatecznie stwierdzamy, że
    x+14=x4+4x3+6x2+4x+1.Otrzymaną tożsamość możemy też zapisać w postaci
    x+14=44x410+43x311+42x212+41x113+40x014

Przykład 6

Wykażemy, że dla dowolnej liczby rzeczywistej x:
x+15=x5+5x4+10x3+10x2+5x+1

  • sposób I (algebraiczny)
    x+15=x+14x+1=x4+4x3+6x2+4x+1x+1  =x5+4x4+6x3+4x2+x+x4+4x3+6x2+4x+1= x5+5x4+10x3+10x2+5x+1

  • sposób II (kombinatoryczny)
    Zauważmy, że mnożąc wyrażenia wybierane z każdego z kolejnych nawiasów iloczynu
    x+1x+1x+1x+1x+1
    dostaniemy za każdym razem do pomnożenia pięć czynników, przy czym każdy z nich to x albo 1. Zatem wynikiem każdego takiego mnożenia jest wyrażenie xk, gdzie k jest równe 5, 4, 3, 2, 1 lub 0. Wykonajmy więc wszystkie możliwe mnożenia wyrażeń wybieranych z kolejnych nawiasów – możemy to zrobić na 25=32 sposoby.
    Rozróżniamy sześć przypadków:

  1. ze wszystkich nawiasów wybraliśmy można to zrobić na jeden sposób, a w wyniku otrzymamy x5, co można też zapisać jako 55x510,

  2. z dokładnie czterech nawiasów wybraliśmy wtedy z dokładnie jednego nawiasu wybraliśmy 1, a więc można to zrobić na 5 sposobów. Zatem łącznie otrzymamy 5x4, co można też zapisać jako 54x411,

  3. z dokładnie trzech nawiasów wybraliśmy można to zrobić na 53=54332=10 sposobów. Łącznie otrzymamy więc 10x3, co można też zapisać jako 53x312,

  4. z dokładnie dwóch nawiasów wybraliśmy można to zrobić na 542=10 sposobów. Łącznie otrzymamy więc 10x2, co można też zapisać jako 52x312,

  5. z dokładnie jednego nawiasu wybraliśmy można to zrobić na 5 sposobów. Łącznie otrzymamy więc 5x, co można też zapisać jako 51x114,

  6. z żadnego z nawiasów nie wybraliśmy x – można to zrobić na 1 sposób. Wtedy z każdego z nawiasów musimy wybrać jedynkę, więc w wyniku mnożenia otrzymamy 1, co można też zapisać jako 50x015.
    Ostatecznie stwierdzamy, że
    x+15=x5+5x4+10x3+10x2+5x+1.
    Otrzymaną tożsamość możemy też zapisać w postaci
    x+15=55x510+54x411+53x312+52x213+51x114+50x015.

Przykład 7

Wykażemy, że dla dowolnej liczby rzeczywistej x:

x+17=x7+7x6+21x5+35x4+35x3+21x2+7x+1
  • sposób I
    Najpierw pokazujemy, że
    x+16=x+15x+1=x5+5x4+10x3+10x2+5x+1x+1=x6+6x5+15x4+20x3+15x2+6x+1.
    Stąd
    x+17=x+16x+1=x6+6x5+15x4+20x3+15x2+6x+1x+1=

=x7+7x6+21x5+35x4+35x3+21x2+7x+1.

  • sposób II
    Korzystając z pomysłów przedstawionych w sposobie II rozwiązania poprzednich podpunktów, pokazujemy, że
    x+17=

=77x710+76x611+75x512+74x413+73x314+72x215+71x116+70x017.
Ponieważ 77=70=1, 76=71=7, 75=72=762=21, 74=73=765321=35, więc otrzymujemy
x+17=x7+7x6+21x5+35x4+35x3+21x2+7x+1.
Rozumując podobnie jak w sposobie II rozwiązań przedstawionych w powyższym przykładzie, można pokazać, że dla dowolnej dodatniej liczby całkowitej n oraz dowolnych liczb całkowitych a oraz b prawdziwa jest równość
a+bn=n0an+n1an-1b+n2an-2b2+...+nn-1a1bn-1+nnbn.
Wzór ten jest nazywany wzorem dwumianowym Newtona.
W szczególności dla a=b=1 otrzymujemy
2n=n0+n1+n2+...+nn-1+nn.
Otrzymana równość uzasadnia znany nam już fakt, że liczba wszystkich podzbiorów zbioru n–elementowego jest równa 2n.