dr inż. Magdalena Topczewska Ćwiczenia nr 1
Kombinatoryka
Definicja 1. Permutacje bez powtórzeń - zbiór sk ladajacy sie z n elementów uporzadkowanych i różnych.
,
,
,
Pn = V n = n!
n
Dwie permutacje tego samego zbioru różnia sie tylko kolejnościa wystepowania elementów.
,
,
,
,
Definicja 2. Permutacje z powtórzeniami - zbiór sk ladajacy sie z n elementów uporzadkowanych, wśród
,
,
,
których pewne elementy powtarzaja sie odpowiednio n
,
,
1, n2, ..., nk razy.
n
n!
P 1,n2,...,nk =
n
n1!n2!...nk!
Definicja 3. Kombinacje bez powtórzeń - z n elementów po k nazywamy zbiór sk ladajacy sie z k różnych
,
,
elementów wybranych spośród n różnych elementów, przy czym obojetne jest w jakim porzadku elementy tego
,
,
zbioru sa rozmieszczone.
,
n
n!
Ck =
=
n
k
k!(n − k)!
Definicja 4. Kombinacje z powtórzeniami - z n elementów po k nazywamy zbiór sk ladajacy sie z k
,
,
elementów różnych lub nieróżniacych sie miedzy soba, wybranych spośród n różnych elementów, przy czym
,
,
,
,
obojetne jest w jakim porzadku elementy tego zbioru sa rozmieszczone.
,
,
,
k
n + k − 1
n + k − 1
(n + k − 1)!
C
=
=
=
n
k
n − 1
k!(n − 1)!
Definicja 5. Wariacja bez powtórzeń - z n elementów po k nazywamy uporzadkowany zbiór sk ladajacy sie
,
,
,
,
z k różnych elementów, wybranych spośród n różnych elementów.
n!
V k =
n
(n − k)!
Definicja 6. Wariacja z powtórzeniami - z n elementów po k nazywamy uporzadkowany zbiór sk ladajacy
,
,
,
sie z k elementów różnych lub nieróżniacych sie miedzy soba, wybranych spośród n różnych elementów.
,
,
,
,
,
k
V
= nk
n
Zadania
Zad 1.
20 studentów ma odbyć praktyke pracujac na każdym z sześciu różnych stanowisk oraz na każdej z dwóch zmian.
,
,
Ile dni bedzie trwa la praktyka?
,
Zad 2.
Ile można utworzyć znaków sk ladajacych sie z figury geometrycznej (okregu, kwadratu, trójkata) oraz cyfry?
,
,
,
,
Zad 3.
Czterech studentów i cztery studentki udaja sie na wycieczke w szyku zwanym gesiego. Iloma sposobami można
,
,
,
,
ich ustawić, tak, aby żadne dwie osoby jednakowej p lci nie sz ly obok siebie.
Zad 4.
Ile jest liczb trzycyfrowych?
Zad 5.
Iloma sposobami można w wyrazie logarytm tak przestawić litery, by miejsca drugie, czwarte i szóste by ly zajete
,
przez spó lg loski?
Zad 6.
Pieciu studentów zdaje egzamin. Iloma sposobami moga być im wystawione oceny?
,
,
Zad 7.
Ile nastapi powitań, jeśli jednocześnie spotka sie pieciu znajomych?
,
,
,
Zad 8.
Ile istnieje trójkatów, których d lugości boków przybieraja jedna z wartości: 5,6,7,8,9?
,
,
,
1
Na ile sposobów można miedzy 3 osoby podzielić 3n różnych przedmiotów, tak, aby każda otrzyma la n przed-
,
miotów?
Zad 10.
Ile jest permutacji liczb 1, 2, ..., n, w których a) 1, 2 nie sasiaduja ze soba
,
,
,
b) 1, 2, 3 nie tworza kolejnych wyrazów?
,
Zad 11.
Na przystanku autobusu wsiada grupa pasażerów sk ladajaca sie z sześciu kobiet i czterech meżczyzn. Ile ist-
,
,
,
nieje wszystkich możliwych sposobów wejścia pasażerów do autobusu, jeżeli pierwsze wsiadaja kobiety, wszyscy
,
wsiadaja tylko jednymi drzwiami i wsiadanie odbywa sie pojedynczo?
,
,
Zad 12.
W mieście L przebudowano centrale telefoniczna czterocyfrowa wprowadzajac numery pieciocyfrowe. O ile osób
,
,
,
,
,
może sie zwiekszyć liczba abonentów (po laczeń z zerem na poczatku nie uwzglednia sie)?
,
,
,
,
,
,
Zad 13.
Winda zatrzymuje sie na 8 pietrach. Na ile sposobów moga opuścić winde 3 osoby?
,
,
,
,
Zad 14.
Rzucamy trzema kostkami do gry. W ilu przypadkach otrzymamy na tych kostkach różne liczby oczek?
Zad 15.
W ciagu roku klient ma sp lacić 6 równych rat miesiecznych. Iloma sposobami może to uczynić?
,
,
Zad 16.
Ile p laszczyzn można poprowadzić przez n punktów, z których żadne cztery nie leża w jednej p laszczyźnie?
,
Zad 17.
Ile różnych warazów (majacych sens lub nie) można otrzymać przestawiajac litery w wyrazie ”kartka”?
,
,
Zad 18.
Winda zatrzymuje sie na 11 pietrach. Na ile sposobów moga opuścić winde 4 osoby wysiadajace na różnych
,
,
,
,
,
pietrach?
,
Zad 19.
Ile liczb czterocyfrowych można utworzyć z cyfr liczby 135135?
Zad 20.
W przedziale wagonu kolejowego ustawione sa naprzeciw siebie dwie lawki majace po pieć numerowanych miejsc
,
,
,
od 1 do 5. Do przedzia lu wchodzi 10 osób. Na ile sposobów moga usiaść, jeśli 3 osoby chca jechać zgodnie
,
,
,
z kierunkiem jazdy, zaś 4 siedzac ty lem do kierunku jazdy?
,
Zad 21.
Sześć kul bia lych, sześć czarnych i sześć zielonych numerujemy i uk ladamy obok siebie w szereg, tak by każde trzy nastepujace po sobie kule by ly różnego koloru (np. bia la, zielona, czarna). Na ile sposobów możemy to
,
,
zrobić, jeżeli kolejność barw jest ustalona?
Zad 22.
W przedziale wagonu kolejowego ustawione sa naprzeciw siebie dwie lawki majace po cztery ponumerowane
,
,
miejsca od 1 do 4. Wszystkie miejsca w przedziale zosta ly zajete. Na ile różnych sposobów moga usiaść
,
,
,
pasażerowie, jeśli wiadomo, że moga zmienić miejsca tylko na lawce, na której siedza, nie moga jednak zmieniać
,
,
,
lawek.
Zad 23.
Malarz ma pomalować trzy pokoje majac do dyspozycji 5 różnych farb. Na ile sposobów może malarz poma-
,
lować pokoje, przy za lożeniu, że każdy pokój ma być pomalowany jednym.
Zad 24.
Ile jest liczb trzycyfrowych o różnych cyfrach wiekszych od 352?
,
Zad 25.
Ile jest różnych rozmieszczeń n ponumerowanych kul w n ponumerowanych komórkach, w których a) wszystkie komórki sa zajete,
,
,
b) co najmniej jedna komórka jest pusta, c) dok ladnie jedna komórka jest pusta?
Zad 26.
Na ile różnych sposobów brydżysta może otrzymać uk lad kart: a) pieć pików, cztery kiery, trzy kara, jeden trefl,
,
b) uk lad: 5–4–3–1, kolory nie sa ustalone,
,
c) uk lad: 4–4–3–2, kolory nie sa ustalone.
,
2