Комбинаторные объекты

Задача 1. Найти количество элементов в указанном множестве

Варианты

1. Сколько подмножеств множества {1, 2,..., 1000} не содержат чисел ни кратных 6, ни кратных 4?

2. Сколько подмножеств множества {1, 2,...., 1000} содержат по крайней мере одно число кратное 5 и ни одного – кратного 7?

3. Сколько существует подмножеств множества {1, 2, 3,..., 1000} имеющих по крайней мере одно число, кратное трем или четырем.

4. Сколько подмножеств множества {1, 2,..., 1000} не содержат ни одного нечетного числа, но имеют по крайней мере одно число кратное 7?

5. Сколько подмножеств из {1,2,3, …, 300} состоят из чисел, делящихся на 4, и не содержат ни одного числа, делящегося на 3?

6. Сколько подмножеств множества {1,2,3, …, 1000} содержат по крайней мере одно число кратное 4, но ни одного кратного 7?

7. Сколько подмножеств множества {1, 2,..., 1000} не содержат чисел ни кратных 6, ни кратных 15?

8. Сколько подмножеств множества {1, 2,...., 1000} содержат по крайней мере одно число кратное 5 и ни одного – кратного 18?

9. Сколько существует подмножеств множества {1, 2, 3,..., 1000} имеющих по крайней мере одно число, кратное 15 или 21.

10. Сколько подмножеств множества {1, 2,..., 1000} не содержат ни одного нечетного числа, но имеют по крайней мере одно число кратное 21?

11. Сколько подмножеств из {1,2,3, …, 300} состоят из чисел, делящихся на 6, и не содержат ни одного числа, делящегося на 7?

12. Сколько подмножеств множества {1, 2,..., 1000} не содержат чисел ни кратных 8, ни кратных 6?

13. Сколько подмножеств множества {1, 2,...., 1000} содержат по крайней мере одно число кратное 12 и ни одного – кратного 13?

14. Сколько существует подмножеств множества {1, 2, 3,..., 1000} имеющих по крайней мере одно число, кратное 6 или 11.

15. Сколько подмножеств множества {1, 2,..., 1000} не содержат ни одного нечетного числа, но имеют по крайней мере одно число кратное 17?

16. Сколько подмножеств из {1,2,3, …, 300} состоят из чисел, делящихся на 7, и не содержат ни одного числа, делящегося на 3?

17. Сколько подмножеств множества {1, 2,..., 1000} не содержат чисел ни кратных 6, ни кратных 9?

18. Сколько подмножеств множества {1, 2,...., 1000} содержат по крайней мере одно число кратное 11 и ни одного – кратного 7?

19. Сколько существует подмножеств множества {1, 2, 3,..., 1000} имеющих по крайней мере одно число, кратное 12 или 13.

20. Сколько подмножеств множества {1, 2,..., 1000} не содержат ни одного нечетного числа, но имеют по крайней мере одно число кратное 23?

21. Сколько подмножеств из {1,2,3, …, 1000} состоят из чисел, делящихся на 7, и не содержат ни одного числа, делящегося на 12?

22. Сколько подмножеств множества {1, 2,..., 1000} не содержат чисел ни кратных 6, ни кратных 10?

23. Сколько подмножеств множества {1, 2,...., 1000} содержат по крайней мере одно число кратное 12 и ни одного – кратного 7?

24. Сколько существует подмножеств множества {1, 2, 3,..., 1000} имеющих по крайней мере одно число, кратное 11 или четырем.

25. Сколько подмножеств множества {1, 2,..., 1000} не содержат ни одного нечетного числа, но имеют по крайней мере одно число кратное 11?

26. Сколько подмножеств из {1,2,3, …, 300} состоят из чисел, делящихся на 2, и не содержат ни одного числа, делящегося на 3?

27. Сколько подмножеств множества {1, 2,..., 1000} не содержат чисел ни кратных 10, ни кратных 4?

28. Сколько подмножеств множества {1, 2,...., 1000} содержат по крайней мере одно число кратное 4 и ни одного – кратного 7?

29. Сколько существует подмножеств множества {1, 2, 3,..., 1000} имеющих по крайней мере одно число, кратное 3 или 8.

30. Сколько подмножеств множества {1, 2,..., 1000} не содержат ни одного нечетного числа, но имеют по крайней мере одно число кратное 5?

31. Сколько подмножеств множества {1, 2,...., 1000} содержат по крайней мере одно число кратное 4 и ни одного – кратного 9?

32. Сколько существует подмножеств множества {1, 2, 3,..., 1000} имеющих по крайней мере одно число, кратное 3 или 5.

33. Сколько подмножеств множества {1, 2,..., 1000} не содержат ни одного нечетного числа, но имеют по крайней мере одно число кратное 15?

34. Сколько подмножеств из {1,2,3, …, 300} состоят из чисел, делящихся на 4, и не содержат ни одного числа, делящегося на 7?

35. Сколько подмножеств множества {1, 2,..., 1000} не содержат чисел ни кратных 12, ни кратных 9?

36. Сколько подмножеств множества {1, 2,...., 1000} содержат по крайней мере одно число кратное 12 и ни одного – кратного 7?

Примеры решения задачи 1.

Пример 1.

Сколько подмножеств множества A={1, 2,...., 1000} содержат ни чисел кратных 8, ни чисел кратных 12?

Решение.

Для произвольного действительного числа x обозначим через [x] его целую часть. (Например [2.5]=2, [1/2]=0, [3]=3.) Пусть 12A – подмножество множества A состоящее из чисел кратных 12, A\12A Í A – подмножество чисел не кратных 12. Элементы, не кратные ни 12 ни 8, составляют множество (A\12A)\8A. Нам нужно найти число подмножеств этого множества. Поскольку число элементов этого множества равно

|(A\12A)\8A|=|A\(12AÈ8A)|=|A|-|12AÈ8A |=

|A|-|12A|-|8A |+|НОК(12,8)A|=1000-[1000/12]-[1000/8]+[1000/24],

то количество его подмножеств равно

Ответ:

Пример 2.

Сколько подмножеств множества A={1, 2,...., 1000} содержат по крайней мере одно число кратное 8 и ни одного – кратного 12?

Решение.

Пусть 12A – подмножество множества A состоящее из чисел кратных 12, A\12A Í A – подмножество чисел не кратных 12. Элементы, не кратные ни 12 ни 8, составляют множество (A\12A)\8A.

Каждое подмножество из A\12A может быть одного из следующих типов:

1. оно не содержит ни одного элемента кратного 8,

2. оно содержит хотя бы один элемент, кратный 8.

Отсюда количество подмножеств множества A\12A равно сумме количеств подмножеств первого и второго типа. Подмножества первого типа – это в точности подмножества не содержащие ни элементов кратных 12, ни элементов, кратных 8. Нам нужно найти количество подмножеств второго типа.

Следовательно, искомое число равно

Ответ:

Пример 3.

Сколько подмножеств множества A={1, 2,...., 1000} содержат по крайней мере одно число кратное 8 или 12?

Решение.

Каждое подмножество множества A обладает одним из следующих взаимоисключающих свойств:

1. оно не содержит ни чисел кратных 8, ни чисел кратных 12,

2. оно содержит по крайней мере одно число, кратное 8 или 12.

Отсюда число подмножеств второго типа (которое как раз нам нужно найти) равно

Ответ:

Задача 2. Найти число разложений заданного числа в сумму слагаемых. Разложения, отличающиеся перестановкой слагаемых, считаются различными.

Варианты

1. Слагаемые состоят из чисел 3 и 4, сумма равна 50.

2. Слагаемые состоят из чисел 3 и 5, сумма равна 50.

3. Слагаемые состоят из чисел 2 и 5, сумма равна 50.

4. Слагаемые состоят из чисел 3 и 4, сумма равна 52.

5. Слагаемые состоят из чисел 3 и 5, сумма равна 52.

6. Слагаемые состоят из чисел 2 и 5, сумма равна 52.

7. Слагаемые состоят из чисел 3 и 4, сумма равна 54.

8. Слагаемые состоят из чисел 3 и 5, сумма равна 54.

9. Слагаемые состоят из чисел 2 и 5, сумма равна 54.

10. Слагаемые состоят из чисел 3 и 4, сумма равна 51.

11. Слагаемые состоят из чисел 3 и 5, сумма равна 51.

12. Слагаемые состоят из чисел 2 и 5, сумма равна 51.

13. Слагаемые состоят из чисел 3 и 4, сумма равна 49.

14. Слагаемые состоят из чисел 3 и 5, сумма равна 49.

15. Слагаемые состоят из чисел 2 и 5, сумма равна 49.

16. Слагаемые состоят из чисел 3 и 4, сумма равна 55.

17. Слагаемые состоят из чисел 3 и 5, сумма равна 55.

18. Слагаемые состоят из чисел 2 и 5, сумма равна 55.

19. Слагаемые состоят из чисел 3 и 4, сумма равна 46.

20. Слагаемые состоят из чисел 3 и 5, сумма равна 46.

21. Слагаемые состоят из чисел 2 и 5, сумма равна 46.

22. Слагаемые состоят из чисел 3 и 4, сумма равна 48.

23. Слагаемые состоят из чисел 3 и 5, сумма равна 48.

24. Слагаемые состоят из чисел 2 и 5, сумма равна 48.

25. Слагаемые состоят из чисел 3 и 4, сумма равна 53.

26. Слагаемые состоят из чисел 3 и 5, сумма равна 53.

27. Слагаемые состоят из чисел 2 и 5, сумма равна 53.

28. Слагаемые состоят из чисел 3 и 4, сумма равна 47.

29. Слагаемые состоят из чисел 3 и 5, сумма равна 47.

30. Слагаемые состоят из чисел 2 и 5, сумма равна 47.

31. Слагаемые состоят из чисел 3 и 4, сумма равна 55.

32. Слагаемые состоят из чисел 3 и 5, сумма равна 45.

33. Слагаемые состоят из чисел 2 и 5, сумма равна 42.

34. Слагаемые состоят из чисел 3 и 4, сумма равна 42.

35. Слагаемые состоят из чисел 3 и 5, сумма равна 41.

36. Слагаемые состоят из чисел 2 и 5, сумма равна 41.

Примеры решения задачи 2.

Пример 1.

Найти число разложений заданного числа в сумму слагаемых. Разложения, отличающиеся перестановкой слагаемых, считаются различными. Слагаемые состоят из чисел 3 и 5, сумма равна 40.

Решение.

Найдем сначала число слагаемых, равных 3, и число слагаемых, равных 5, дающих в сумме число 40. С этой целью решим уравнение в целых числах

3x + 5y = 40, x³0, y³0.

Первое решение x=0, y=8. Чтобы найти другие решения, будем прибавлять по 5 к числу x и вычитать по 3 из числа y. Получим решения

x = 0, y=8;

x = 5, y=5;

x = 10, y=2;

Число последовательностей чисел, состоящих из x троек и y пятерок, равно . Отсюда находим числа разложений

при x = 0, y=8 -

при x = 5, y=5 -

при x = 10, y=2 -

Сумма этих чисел будет искомым числом разложений.

Ответ:

Задача 3. Перечисление функций. Для заданных m и n вычислить числа:

· функций {1,2, …, m} ® { 1, 2, …, n}

· инъекций {1,2, …, m} ® { 1, 2, …, n}

· сюръекций {1,2, …, n} ® { 1, 2, …, m}

· неубывающих функций {0,1,2, …, m} ® {0, 1, 2, …, n}

· возрастающих функций {0,1,2, …, m} ® {0, 1, 2, …, n}

· неубывающих сюръекций {0,1,2, …, n} ® {0, 1, 2, …,m}

Варианты

1. m = 4, n = 5	9. m = 6, n = 8	17. m = 3, n = 7	25. m = 2, n = 10	33. m = 7, n = 9
2. m = 5, n = 6	10. m = 5, n = 8	18. m = 2, n = 7	26. m = 3, n = 10	34. m = 8, n = 9
3. m = 4, n = 11	11. m = 4, n = 8	19. m = 2, n = 11	27. m = 4, n = 10	35. m = 6, n = 9
4. m = 5, n = 9	12. m = 3, n = 8	20. m = 4, n = 6	28. m = 5, n = 10	36. m = 5, n = 11
5. m = 4, n = 9	13. m = 2, n = 8	21. m = 3, n = 6	29. m = 6, n = 10
6. m = 3, n = 9	14. m = 6, n = 7	22. m = 2, n = 6	30. m = 7, n = 10
7. m = 2, n = 9	15. m = 5, n = 7	23. m = 3, n = 5	31. m = 8, n = 10
8. m = 7, n = 8	16. m = 4, n = 7	24. m = 3, n = 11	32. m = 9, n = 10

Пример решения задачи 3. Заданы m=6, n=11.

Вычислить числа:

· функций {1,2, …, 6} ® { 1, 2, …, 11}

· инъекций {1,2, …, 6} ® { 1, 2, …, 11}

· сюръекций {1,2, …, 11} ® { 1, 2, …,6}

· неубывающих функций {0,1,2, …, 6} ® {0, 1, 2, …, 11}

· возрастающих функций {0,1,2, …, 6} ® {0, 1, 2, …, 11}

· неубывающих сюръекций {0,1,2, …, 11} ® {0, 1, 2, …,6}

Решение.

Обозначим L_n = {1,2,3, …, n}. Искомые числа вычисляются с помощью таблицы, в каждой клетке которой указано число функций L_m®L_n с заданными свойствами

	функций Lm®Ln	Неубывающих функций Lm®Ln
Всех	nm
Инъективных
Сюръективных	n! S(m,n)
Биективных	n!, если m=n, иначе 0	1, если m=n, иначе 0

Возрастающие функции – это в точности неубывающие инъективные функции. Находим

· число функций {1,2,3,4,5,6 } ® { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11} равно 11⁶=1771561

· число инъекций {1,2,3,4,5,6 } ® { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11 } равно = 332640

· число сюръекций { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11 } ® {1,2,3,4,5,6 } равно 6! S(11,6). Число S(11,6) вычислим с помощью таблицы

n k

Получим 6!S(11,6) =6!179487

· число неубывающих функций {0,1,2,3,4,5,6 } ® { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11 } равно

· число возрастающих функций {0,1,2,3,4,5,6 } ® { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11 } равно

· число неубывающих сюръекций { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11 } ® {0,1,2,3,4,5,6 } равно

Задача 4. Найти производящую функцию последовательности

Варианты

1. 2nn(n+1) 2. 2n/n 3. 2nn2 4. 2n/(n(n+1)) 5. 3nsin(2n) 6. 3ncos(2n) 7. 4nn(n+1) 8. 4n/n 9. 4nn2 10. 4n/(n(n+1)) 11. 6n/n 12. 3nsin(4n)

13. 3ncos(4n) 14. 7nn(n+1) 15. 7n/n 16. 7nn2 17. 7n/(n(n+1)) 18. sin(7n) 19. cos(7n) 20. 5nn(n+1) 21. 5n/n 22. 6nn2 23. 5nn2 24. 5n/(n(n+1))

25. 5nsin(5n) 26. 5ncos(5n) 27. 3nn(n+1) 28. 3n/n 29. 3nn2 30. 3n/(n(n+1)) 31. sin(3n) 32. cos(3n) 33. 7nn(n+1) 34. 7n/n 35. 7nn2 36. 3n/(n(n+1))

Пример решения задачи 4.

Найти производящую функцию последовательности a_n = 10ⁿ/(n(n+1))

Решение.

Производящая функция будет равна сумме ряда .

Поскольку , то

С помощью преобразования

получаем

Вычислим =

Следовательно

Ответ:

Задача 5. Коды Прюфера

Построить дерево по его коду Прюфера и сделать проверку

Варианты

1. 15371 2. 76412 3. 26415 4. 76421 5. 16415 6. 65413 7. 36412 8. 46715 9. 16415 10. 77411 11. 74422 12. 17251

13. 15311 14. 76422 15. 26425 16. 76431 17. 16425 18. 65423 19. 36421 20. 46725 21. 16425 22. 77421 23. 74431 24. 31625

25. 11371 26. 73412 27. 22415 28. 71421 29. 13415 30. 62413 31. 31412 32. 43715 33. 12415 34. 71411 35. 72422 36. 72112