Matematyka dyskretna – dr Marcin Raniszewski, dr inż. Witold Staszewski

Matematyka Dyskretna – ćw. 4

Kombinatoryka

Kombinacja bez powtórzeń i z powtórzeniami, zadania różne

Kombinacja bez powtórzeń:

Niech dany będzie zbiór

złożony z n różnych elementów. 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ć. Symbol:

.

Liczba wszystkich k-elementowych kombinacji bez powtórzeń ze zbioru

wyraża się wzorem:

Zachodzi:



, gdyż



(zbiór pusty)



(cały zbiór)



Kombinacja z powtórzeniami:

Niech dany będzie zbiór

złożony z n różnych elementów. 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ć. Symbol:

.

Liczba wszystkich k-elementowych kombinacji z powtórzeniami ze zbioru

wyraża się wzorem:

Zad. 1. Ile zostanie rozegranych meczów w turnieju szachowym dziesięciu zawodników gdzie
każdy grał z każdym dokładnie jeden raz?

Zad. 2. Ile zespołów liczy liga jeżeli w sezonie letnim rozegrano 120 meczów (każdy grał z
każdym dokładnie jeden raz)?

Zad. 3. Ile jest możliwych skreśleń sześciu liczb w Lotto?

Zad. 4. Na ile sposobów można pomalować czterema kolorami sześć nierozróżnialnych
przedmiotów?

symbol Newtona

Matematyka dyskretna – dr Marcin Raniszewski, dr inż. Witold Staszewski

Zad. 5. Ile jest rezultatów rzutu:

(a) trzema nierozróżnialnymi kostkami?
(b) trzema rozróżnialnymi kostkami?

Zad. 6. Pewna grupa studencka składa się z 10 mężczyzn i 6 kobiet. Na ile sposobów można
ich wpisać na numerowaną listę tak aby:

(a) lista zwierała tylko siedem osób?
(b) lista zawierała trzech mężczyzn i cztery kobiety?
(c) lista zawierała cztery kobiety lub siedmiu mężczyzn?
(d) lista zawierała dwóch mężczyzn i cztery kobiety lub trzech mężczyzn i trzy kobiety?

Zad. 7. Ile jest rezultatów rzutu:

(a) pięcioma nierozróżnialnymi monetami?
(b) pięcioma rozróżnialnymi monetami?

Zad. 8. Znajdź liczbę układów kart w pokerze następujących rodzajów:

(a) poker (strit w kolorze)
(b) kareta (cztery karty o tej samej wartości)
(c) kolor (pięć kart w tym samym kolorze, ale nie poker)
(d) trójka (dokładnie trzy karty o tej samej wartości, reszta kart o innych wartościach)
(e) para (dokładnie dwie karty o tej samej wartości, reszta kart o innych wartościach)

Czy liczy się

kolejność?

Nie

Kombinacje

Czy są

powtórzenia?

Nie

Kombinacje

bez powtórzeń

Tak

Kombinacje

z powtórzeniami

Tak

Wariacje

Czy są

powtórzenia?

Nie

Wariacje

bez powtórzeń

Tak

Wariacje

z powtórzeniami