1Cztery własności
- Definicję, trójkąt Pascala i wzór dwumianowy znasz z klasy II. Tu liczy się znaczenie: (n po k) to liczba k-elementowych podzbiorów zbioru n-elementowego (0 ≤ k ≤ n).
- (n po 0) = (n po n) = 1: jest jeden pusty podzbiór i jeden cały.
- Symetria: (n po k) = (n po n − k). Wybranie k elementów to to samo, co wskazanie n − k odrzuconych.
- Reguła Pascala: (n po k) + (n po k + 1) = (n + 1 po k + 1).
- Suma: (n po 0) + (n po 1) + … + (n po n) = 2ⁿ.
2Dowód zliczający krok po kroku
- Dowód sumy, krok 1: każdy z n elementów jest w podzbiorze albo go nie ma (2 możliwości), więc wszystkich podzbiorów jest 2 · 2 · … · 2 = 2ⁿ.
- Krok 2: liczymy te same podzbiory według liczby elementów k: k-elementowych jest (n po k), dla k = 0, 1, …, n.
- Krok 3: to ten sam zbiór, więc (n po 0) + (n po 1) + … + (n po n) = 2ⁿ.
- Dowód Pascala: wybieramy k + 1 osób z n + 1, wśród których jest wyróżniona osoba x. Albo x jest w wyborze (dobierasz k z n), albo nie ma jej (wybierasz k + 1 z n).
- Sprawdzenie liczbowe: 10 + 10 = 20 = (6 po 3).
W dowodzie reguły Pascala wyróżniasz jedną osobę x, bo
Podział na rozłączne przypadki pozwala dodać ich liczności.
To jedno z 8 pytań quizu. Rozwiąż cały quiz →
3Zastosowania
- Wybór 3 z 7 to wybór 4 odrzuconych: (7 po 3) = (7 po 4) = 35.
- Ile podzbiorów 6-elementowego zbioru ma parzystą liczbę elementów? 1 + 15 + 15 + 1 = 32 = 2⁵. To połowa z 2⁶ = 64 podzbiorów.
Dowód zliczający: ten sam zbiór liczysz dwa razy na różne sposoby i porównujesz wyniki.
Dowodzenie równości tylko sprawdzeniem dla kilku liczb. Przykład nie jest dowodem, dowodem jest rozumowanie dla dowolnych n i k.
✎Ściąga: Własności symbolu Newtona i dowód zliczający
Najważniejsze w pigułce – przeczytaj tuż przed kartkówką lub sprawdzianem.
- Dowód zliczający: ten sam zbiór liczysz dwa razy na różne sposoby i porównujesz wyniki.
- Symetria: (n po k) = (n po n − k). Wybranie k elementów to to samo, co wskazanie n − k odrzuconych.
- Reguła Pascala: (n po k) + (n po k + 1) = (n + 1 po k + 1).
- Suma: (n po 0) + (n po 1) + … + (n po n) = 2ⁿ.
- Dowód sumy, krok 1: każdy z n elementów jest w podzbiorze albo go nie ma (2 możliwości), więc wszystkich podzbiorów jest 2 · 2 · … · 2 = 2ⁿ.
- Krok 2: liczymy te same podzbiory według liczby elementów k: k-elementowych jest (n po k), dla k = 0, 1, …, n.
- Krok 3: to ten sam zbiór, więc (n po 0) + (n po 1) + … + (n po n) = 2ⁿ.
?Quiz: powtórz przed kartkówką
8 pytań w stylu kartkówki i sprawdzianu. Odpowiedz w myślach, potem sprawdź odpowiedź. Rozwiąż quiz z wynikiem – każda odpowiedź ma wyjaśnienie.
Ile podzbiorów ma zbiór 5-elementowy?
- A120
- B25
- C10
- D32
Sprawdź odpowiedź
Odpowiedź D: 32 – Każdy z 5 elementów jest albo nie jest wybrany: 2⁵ = 32.
Równość (n po k) = (n po n − k) wynika z tego, że
- Awybranie k elementów to wskazanie n − k odrzuconych
- Bn jest zawsze parzyste
- Cn! = k!
- Dzbiór ma n − k elementów
Sprawdź odpowiedź
Odpowiedź A: wybranie k elementów to wskazanie n − k odrzuconych – Każdemu podzbiorowi k-elementowemu odpowiada jego dopełnienie z n − k elementami.
Ile wynosi (7 po 4)?
- A70
- B35
- C21
- D28
Sprawdź odpowiedź
Odpowiedź B: 35 – (7 po 4) = (7 po 3) = 35.
Reguła Pascala mówi, że (6 po 2) + (6 po 3) równa się
- A(12 po 5)
- B(7 po 3)
- C(7 po 2)
- D(6 po 5)
Sprawdź odpowiedź
Odpowiedź B: (7 po 3) – (n po k) + (n po k + 1) = (n + 1 po k + 1): tu n = 6, k = 2.
Ile wynosi (6 po 2) + (6 po 3)?
- A36
- B35
- C20
- D30
Sprawdź odpowiedź
Odpowiedź B: 35 – 15 + 20 = 35 = (7 po 3).
Suma (4 po 0) + (4 po 1) + (4 po 2) + (4 po 3) + (4 po 4) wynosi
- A16
- B24
- C8
- D15
Sprawdź odpowiedź
Odpowiedź A: 16 – Suma po wszystkich k to 2⁴ = 16 (1 + 4 + 6 + 4 + 1).
W dowodzie reguły Pascala wyróżniasz jedną osobę x, bo
- Awybór albo ją zawiera, albo nie – to dwa rozłączne przypadki
- Bosoba x musi być wybrana
- Cdzięki temu liczba osób maleje o 2
- Dx ma największy numer
Sprawdź odpowiedź
Odpowiedź A: wybór albo ją zawiera, albo nie – to dwa rozłączne przypadki – Podział na rozłączne przypadki pozwala dodać ich liczności.
Ile podzbiorów zbioru 6-elementowego ma parzystą liczbę elementów?
- A20
- B32
- C64
- D31
Sprawdź odpowiedź
Odpowiedź B: 32 – 1 + 15 + 15 + 1 = 32, czyli połowa z 2⁶ = 64.
Cały dział „Kombinatoryka”: ściąga i próbny sprawdzian →
Kartkówka albo sprawdzian już blisko?
Rozwiąż quiz z wynikiem i powtórz materiał na fiszkach. Każda odpowiedź ma wyjaśnienie, a postęp zapisuje się bez zakładania konta.