Разложения

Существует тесная связь между подмножествами множеств и разложениями целого числа.

Определение. Разложение n есть представление числа n в виде упорядоченной суммы положительных целых. Например, существует восемь разложений числа 4, а именно:

1+1+1+1 3+1

2+1+1 1+3

1+2+1 2+2

1+1+2 4

Если разложение  содержит в точности k слагаемых, то говорят, что  имеет k частей и называется k -разложением. Если a₁ + a₂ +...+ a_k - k -разложение  числа n, определим (k 1) - элементное подмножество () (или (k 1)- подмножество ) множества {1, 2, ..., n-1} формулой

() ={a₁ , a₁+a₂ , ... , a₁ + a₂ + ... + a_k-1 } .

Эта формула устанавливает взаимно однозначное соответствие (биекцию) между всеми k-разложениями и (k 1)- подмножествами () множества {1, 2, ..., n-1}. Следовательно, существует k -разложений n и 2^{n - 1} разложений n. Разложение часто схематично представляют, рисуя в строку n точек и k  1 разделяющую вертикальную черту. Точки разделяются по k линейно упорядоченным “отделениям”, числа точек в отделениях дают k -разложение числа n . Например, последовательность

        

соответствуют разложению 1+2+1+1+3+2 .

Другая проблема, тесно связанная с разложениями, есть задача подсчета числа N(n, k) решений уравнения

x₁ + x₂ +... +x_k = n

в неотрицательных целых числах. Решение такого уравнения называется слабым разложением n на k частей, или слабым k- разложением числа n. (Решение в положительных целых числах есть просто k-разложение n.) Если мы положим y₁ = x₁ +1, y₂ = x₂ +1, ... , y_k =x_k +1, то получим, что N(n, k) есть количество решений в положительных числах уравнения

y₁ + y₂ +... +y_k = n +k ,

то есть число k-разложений числа n+k .

Таким образом, .

Подобным же приемом (найти его предоставляется читателю) доказывается, что число решений неравенства x₁ + x₂ +... +x_k  n в неотрицательных целых числах есть .

k - подмножество T n - множества S иногда называют k - сочетанием из S без повторений. Так возникает задача подсчета числа k - сочетаний из S с повторениями; то есть мы выбираем k элементов из множества S, не взирая на их порядок и допуская повторяющиеся элементы. Обозначим число таких способов . Например, . Если S = {1,2,3}, то подходящие сочетания есть 11, 22, 33, 12, 13, и 23. Эквивалентное, но более точное определение и исследование сочетаний с повторениями может быть проведено, если ввести понятие мультимножества. На интуитивном уровне мультимножество есть множество с повторяющимися элементами, например {1, 1, 2, 5, 5}. Более точно, конечное мультимножество M на множестве S есть функция : S ( - множество натуральных чисел), такая, что ; (x) рассматривается как число повторений элемента x. Целое число называют мощностью или числом элементов M и обозначают M . Если S = {x₁ , x₂ , ... , x_n}, и (x_i) = a_i , то мы пишем . Множество всех k - мультимножеств на S обозначается символом .

Если S = {y₁ , ... , y_n} и мы положим x_i = (y_i), то увидим, что есть число решений в неотрицательных целых числах уравнения x₁ + x₂ + ... + x_n = k . Это число, как мы видели, есть

. (1.9)

Прямое комбинаторное доказательство утверждения ( 1 .9) таково. Пусть

{a₁, a₂, ... , a_k}, 1  a₁ < a₂ < ... < a_k  n + k  1,

есть k -подмножество множества [ n + k  1]= {1, 2, ... , n+k  1}. Положим b_i = a_i  i + 1. Тогда {b₁ , b₂ , ... , b_n} - k -мультимножество на множестве [n].

Обратно, если дано k - мультимножество 1  b₁  b₂  b_k  n на [n], то определив a_i формулой a_i = b_i + i  1, видим, что {a₁ , a₂ , ..., a_k } есть k -подмножество множества [n + k  1] . Следовательно, мы определили взаимно однозначное соответствие между и , что и требовалось доказать.

Поучителен подход к мультимножествам с точки зрения производящих функций. Cовершенно аналогично проведенному исследованию подмножеств множества S = {x₁ , x₂ , ... , x_n } имеем

Положим x_i = x. Тогда

.

Но

,

так что

.

Появление элегантной формулы

не случайно. Это простейший пример комбинаторной теории взаимности.