Matematyka Dyskretna  ćw. 5
Kombinatoryka 1
Zasada włączeń i wyłączeń, prawo mnożenia,
wariacje i kombinacje
Zasada włączeń i wyłączeń dla dwóch skończonych zbiorów:
Zasada włączeń i wyłączeń dla trzech skończonych zbiorów:
Prawo mnożenia (dla zbiorów skończonych):
Zad. 1. Ile jest liczb trzycyfrowych podzielnych przez 8 lub 12?
Zad. 2. Ile jest liczb czterocyfrowych podzielnych przez 3 lub 11 lub 12?
Zad. 3. Niech: , ,
. Oblicz liczbę elementów zbioru .
Niech dany będzie zbiór złożony z n elementów.
k-elementową ( ) wariacją bez powtórzeń ze zbioru nazywamy każdy k-elementowy ciąg
utworzony z elementów zbioru taki, że elementy w tym ciągu nie mogą się powtarzać.
Liczba wszystkich k-elementowych wariacji bez powtórzeń ze zbioru wyraża się wzorem:
Jeśli to wariację bez powtórzeń nazywamy permutacją zbioru . Czyli: .
Liczba wszystkich permutacji zbioru wyraża się wzorem:
k-elementową wariacją z powtórzeniami ze zbioru nazywamy każdy k-elementowy ciąg utworzony
z elementów zbioru taki, że elementy w tym ciągu mogą się powtarzać.
Liczba wszystkich k-elementowych wariacji z powtórzeniami ze zbioru wyraża się wzorem:
Matematyka dyskretna  dr Marcin Raniszewski, dr inż. Witold Staszewski
k-elementową ( ) kombinacją bez powtórzeń ze zbioru nazywamy każdy k-elementowy podzbiór
utworzony z elementów zbioru . Skoro podzbiór, to elementy nie mogą się powtarzać.
Liczba wszystkich k-elementowych kombinacji bez powtórzeń ze zbioru wyraża się wzorem:
k-elementową kombinacją z powtórzeniami ze zbioru nazywamy każdy k-elementowy wielozbiór
utworzony z elementów zbioru . Skoro wielozbiór, to elementy mogą się powtarzać.
Liczba wszystkich k-elementowych kombinacji z powtórzeniami ze zbioru wyraża się wzorem:
Czy liczy się
kolejność?
Nie Tak
Kombinacje Wariacje
Czy są Czy są
powtórzenia? powtórzenia?
Nie Tak Nie Tak
Kombinacje Kombinacje Wariacje Wariacje
bez powtórzeń z powtórzeniami bez powtórzeń z powtórzeniami
Zad. 4. Na ile sposobów można sześć z dziesięciu osób wpisać na numerowaną listę? Na ile
sposobów można ich wszystkich wpisać na numerowaną listę?
Zad. 5. Ile zostanie rozegranych meczów w turnieju szachowym dziesięciu zawodników gdzie
każdy grał z każdym dokładnie jeden raz?
Zad. 6. Ile symboli można zakodować w alfabecie używając co najwyżej 6
znaków tego alfabetu?
Zad. 7. Na ile sposobów można pomalować czterema kolorami sześć nierozróżnialnych
przedmiotów?
Zad. 8. Ile jest dziewięciocyfrowych numerów rozpoczynających się od  609 zawierających
dokładnie raz sekwencję  609 ?
Zad. 9. Ile jest pięciocyfrowych liczb parzystych, które mają dokładnie dwie cyfry parzyste?
Zad. 10. Ile jest sześciocyfrowych liczb nieparzystych o różnych cyfrach, które mają
dokładnie trzy cyfry parzyste?
Matematyka dyskretna  dr Marcin Raniszewski, dr inż. Witold Staszewski