- Композиция числа
-
Не следует путать с Композиция функций.
В теории чисел композицией, или разложением, натурального числа называется его представление в виде упорядоченной суммы натуральных слагаемых. Слагаемые, входящие в композицию, называют частями, а их количество — длиной композиции.
В отличие от композиции, разбиение числа не учитывает порядок следования частей. Поэтому число разбиений числа никогда не превосходит числа композиций.
При фиксированной длине композиций в них иногда также допускают нулевые части.
Содержание
Примеры
Существует 16 композиций числа 5:
Количество композиций
В общем случае существует композиций числа n, из которых в точности имеют длину k. Для доказательства этого утверждения достаточно построить биекцию между композициями n длины k и -элементными подмножествами -элементного множества. Поставим в соответствие композиции подмножество множества , состоящее из частичных сумм: . Очевидно, у этого соответствия есть обратное: по подмножеству , элементы которого упорядочены по возрастанию, можно восстановить исходную композицию:
- , при и, наконец, .
Таким образом, построенное отображение биективно, и поэтому количество композиций числа n длины k равно количеству -элементных подмножеств -элементного множества, то есть биномиальному коэффициенту . Для подсчета общего числа композиций числа n достаточно или просуммировать эти биномиальные коэффициенты, или использовать то же отображение для построения биекции между всеми композициями числа n и всеми подмножествами -элементного множества.
Если в композициях числа n длины k разрешить нулевые части, то количество таких композиций будет равно , поскольку прибавление 1 к каждой части даёт композицию числа n + k уже без нулевых частей. Вопрос об общем количестве композиций числа n с возможными нулевыми частями лишён смысла, так как оно бесконечно.
См. также
Литература
- Сачков В. Н. Комбинаторные методы дискретной математики. — М.: Наука, 1977. — С. 241. — 319 с.
Категории:- Комбинаторика
- Теория чисел
Wikimedia Foundation. 2010.