Пример решения задачи 2
Задание. Найти число разложений заданного числа в сумму слагаемых. Разложения, отличающиеся перестановкой слагаемых, считаются различными. Слагаемые состоят из чисел 3 и 5, сумма равна 40.
Решение. Найдем сначала число слагаемых, равных 3, и число слагаемых, равных 5, дающих в сумме число 40. С этой целью решим уравнение в целых числах
3x + 5y = 40, x0, y0.
Первое решение 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, …, m } { 1, 2, …, n },
неубывающих функций {0,1,2, …, m} {0, 1, 2, …, n},
возрастающих функций {0,1,2, …, m } {0, 1, 2, …, n },
неубывающих сюръекций {0,1,2, …, m } {0, 1, 2, …, n }.
Варианты заданий
|
1. m = 4 , n = 5 |
2. m = 6 , n = 8 |
3.m = 3 , n = 7 |
4. m = 2 , n = 10 |
5.m = 7 , n = 9 |
|
6. m = 5 , n = 6 |
7. m = 5 , n = 8 |
8.m = 2 , n = 7 |
9. m = 3 , n = 10 |
10.m = 8 , n = 9 |
|
11.m = 4, n = 11 |
12. m = 4 , n = 8 |
13. m = 2,n = 11 |
14. m = 4,n = 10 |
15. m = 6 , n = 9 |
|
16. m = 5, n = 9 |
17. m = 3 , n = 8 |
18. m = 4 , n = 6 |
19. m = 5, n = 10 |
20.m = 5, n = 11 |
|
21. m = 4, n = 9 |
22. m = 2 , n = 8 |
23.m = 3 , n = 6 |
24. m = 6, n = 10 |
25.m = 3, n = 9 |
|
26. m = 6, n = 7 |
27. m = 2, n = 6 |
28.m = 7, n = 10 |
29. m= 2,n= 9 |
30. m= 5,n= 7 |
Пример решения задачи 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}.
Решение. ОбозначимLn= {1,2,3, …, n}. Искомые числа вычисляются с помощью таблицы 7.1, в каждой клетке которой указано число функцийLmLnс заданными свойствами.
Таблица 7.1
Число функций
-
функций LmLn
Неубывающих функций LmLn
Всех
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}равно 116=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) вычислим с помощью значений чисел Стирлинга второго рода, приведенных в таблице 7.2.
Получим 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 }равно
.
Таблица 7.2
Числа Стирлинга
|
n k |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
1 |
1 |
|
|
|
|
|
|
|
|
|
2 |
1 |
1 |
|
|
|
|
|
|
|
|
3 |
1 |
3 |
1 |
|
|
|
|
|
|
|
4 |
1 |
7 |
6 |
1 |
|
|
|
|
|
|
5 |
1 |
15 |
25 |
10 |
1 |
|
|
|
|
|
6 |
1 |
31 |
90 |
65 |
15 |
1 |
|
|
|
|
7 |
1 |
63 |
301 |
350 |
140 |
21 |
1 |
|
|
|
8 |
1 |
127 |
966 |
1701 |
1050 |
266 |
28 |
1 |
|
|
9 |
1 |
255 |
3025 |
7770 |
6951 |
2646 |
462 |
36 |
1 |
|
10 |
1 |
511 |
9330 |
34105 |
42525 |
22827 |
5880 |
750 |
45 |
|
11 |
|
|
|
|
|
179487 |
|
|
|
Задача 4. Найти производящую функцию последовательности.