LISTA ZADAC
NR 5 Z MATEMATYKI DYSKRETNEJ
Kombinatoryka (do samodzielnego rozwiÄ…zania)
1. Ile liczb naturalnych ze zbioru S = {1, 2,3,...,1000} dzieli siÄ™ przez 3 lub 5?
2. W pewnej grupie składającej się ze 150 osób 45 regularnie pływa, 40 jez
dzi na rowerze, a 50
uprawia jogging. Wiemy ponadto, że są 32 osoby, które uprawiają jogging, ale nie jeżdżą na
rowerze, 27 takich, które uprawiają jogging i pływają i 10 uprawiających wszystkie trzy
dyscypliny.
a) Ile osób uprawia jogging, ale nie pływa i nie jez
dzi na rowerze?
b) Jeśli wiemy dodatkowo, że 21 osób jez
dzi na rowerze i pływa, to ile nie uprawia żadnej z
wymienionych dyscyplin?
3. Na ile sposobów można ustawić 10 osób w rząd?
4. Ile liczb pięciocyfrowych można utworzyć z cyfr: 1, 2, 3, 4, 5, w taki sposób, aby żadna z cyfr
w liczbie nie powtarzała się?
5. Ile jest liczb pięciocyfrowych, w których żadna cyfra nie powtarza się?
6. Do turnieju szachowego rozgrywanego systemem  każdy z każdym zgłoszono n
zawodników. Ile partii zostanie rozegranych w turnieju?
7. W trójwymiarowej przestrzeni danych jest n punktów, z których żadne cztery nie leżą na
jednej płaszczyz
nie. Ile prostych i ile płaszczyzn wyznaczają te punkty?
8. Pewna grupa studencka składa się z 12 mężczyzn i 16 kobiet. Ile da się z nich utworzyć
komisji, składających się z:
a) siedmiu osób?
b) trzech mężczyzn i czterech kobiet?
c) siedmiu kobiet lub siedmiu mężczyzn?
9. Niech S = {a,b,c, d} i T = {1, 2,3,4,5,6,7} .
a) Ile jest funkcji różnowartościowych z T do S?
b) Ile jest funkcji różnowartościowych z S do T?
c) Ile jest funkcji z S do T?
10. Niech P = {1, 2,3, 4,5,6,7,8,9}i Q = {A, B,C, D, E}.
a) Ile jest czteroelementowych podzbiorów zbioru P?
b) Ile jest permutacji zbioru Q?
c) Ile jest numerów rejestracyjnych składających się z trzech liter ze zbioru Q i następujących po
nich dwóch cyfr ze zbioru P? Zakładamy, że zarówno litery, jak i cyfry mogą się powtarzać.
11. Z tali 52 kart losujemy karty ze zwracaniem.
a) Na ile osób sposobów można wylosować kolejno dziesięć kart, tak aby dziesiąta z nich nie
wystąpiła wcześniej?
b) Na ile osób sposobów można wylosować kolejno dziesięć kart, tak aby dziesiąta z nich
wystąpiła wcześniej?
12. Niech " = {a,b,c, d,e} będzie alfabetem i "k będzie zbiorem słów o długości k
utworzonych ze znaków alfabetu " . Ile elementów mają zbiory?
a) "k , dla dowolnego k " N ?
b) { s " "3 : żadna litera nie występuje w s więcej niż raz}?
c) { s " "4 : litera c występuje w s dokładnie raz}?
d) { s " "4 : litera c występuje w s co najmniej raz}?
13. Na ile sposobów można ustawić litery a, b, c, d, e, f w takiej kolejności, aby
a) litery a i b sąsiadowały ze sobą?
b) litery a i b nie sąsiadowały ze sobą?
c) litery a i b sąsiadowały ze sobą, a litery a i c nie?
14. Udowodnić tożsamości kombinatoryczne:
n n
ëÅ‚ öÅ‚ ëÅ‚ öÅ‚
a) ìÅ‚ ÷Å‚ = ìÅ‚ ÷Å‚ - symetria symbolu Newtona,
ìÅ‚k ÷Å‚ ìÅ‚n - k ÷Å‚
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
n n
ëÅ‚ öÅ‚ ëÅ‚ -1 n -1
öÅ‚ ëÅ‚ öÅ‚
b) ìÅ‚ ÷Å‚ = ìÅ‚ ÷Å‚ + ìÅ‚ ÷Å‚ - trójkÄ…t Pascala,
ìÅ‚k ÷Å‚ ìÅ‚ ÷Å‚ ìÅ‚k -1÷Å‚
k
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
n n
ëÅ‚ öÅ‚ ëÅ‚ -1
n öÅ‚
c) ìÅ‚ ÷Å‚ = Å"ìÅ‚ ÷Å‚ - pochÅ‚anianie.
ìÅ‚k ÷Å‚ ìÅ‚k -1÷Å‚
k
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
15. Ile sześciocyfrowych liczb parzystych można utworzyć z cyfr: 1, 1, 1, 2, 3, 4?
16. Danych jest n kart ponumerowanych i k bez numerów. Karty te układamy w rząd jedna po
drugiej. Ile istnieje różnych ułożeń kart, przy założeniu, że karty nienumerowane są
nierozróżnialne?
17. Na ile sposobów można rozłożyć 7 ponumerowanych kul w 5-ciu szufladach, jeśli porządek
ułożenia kul w szufladzie jest istotny?
Odpowiedzi
1. 467
2. a) 15 b) 71
3. 3628800
4. 120
5. 27216
6. n(n -1) / 2
7. n(n -1) / 2 prostych, n(n -1)(n - 2) / 6 płaszczyzn
8. a) 1184040, b) 400400, c) 12232
9. a) 0, b) 840, c) 2401
10. a) 126, b) 120, c) 6125
11. a) 52 Å" 519 , b) 5210 - 52Å"519
12. a) 5k , b) 60, c) 256, d) 369
13. a) 240, b) 480, c) 192
15. 40
(n + k)!
16.
k!
17. 1663200
Dorota Majorkowska-Mech