Меню Главная Случайная статья Настройки Композиция числа Материал из https://ru.wikipedia.org В теории чисел композицией, или разложением натурального числа называется такое его представление в виде суммы натуральных чисел, которое учитывает порядок следования слагаемых. Слагаемые, входящие в композицию, называют частями, а их количество — длиной композиции. Разбиение числа, в отличие от композиции, не учитывает порядок следования частей. Следовательно, число разбиений числа никогда не превосходит числа композиций. При фиксированной длине композиций в них иногда допускают слагаемые, равные 0. Примеры Существует 16 композиций числа 5: ${\displaystyle {\begin{alignedat}{2}5&=5=\\&=4+1=\\&=3+2=\\&=3+1+1=\\&=2+3=\\&=2+2+1=\\&=2+1+2=\\&=2+1+1+1=\\&=1+4=\\&=1+3+1=\\&=1+2+2=\\&=1+2+1+1=\\&=1+1+3=\\&=1+1+2+1=\\&=1+1+1+2=\\&=1+1+1+1+1.\end{alignedat}}}$ Количество композиций В общем случае существует ${\displaystyle 2^{n-1}}$ композиций числа n, из которых в точности ${\displaystyle {\tbinom {n-1}{k-1}}}$ имеют длину k, где ${\displaystyle {\tbinom {n-1}{k-1}}}$ — биномиальный коэффициент, или число сочетаний. Самый длинный способ записать число ${\displaystyle n}$ — представить его в виде суммы ${\displaystyle n}$ единиц: $${\displaystyle n=\underbrace {1+1+\ldots +1} _{n\ {\text{раз}}}}$$ Заменим теперь в этой записи все плюсы на пустые квадраты. Всего этих пустых квадратов ${\displaystyle n-1}$, на единицу меньше, чем количество единиц: $${\displaystyle n=1\ \Box \ 1\ \Box \ldots \Box \ 1\ \Box \ 1}$$ В каждый из этих квадратов можно писать либо (${\displaystyle +}$), либо запятую (${\displaystyle ,}$). Каждое заполнение всех квадратов даст в результате очередное разложение числа. Получается, что каждое разложение числа ${\displaystyle n}$ на слагаемые можно представить как размещение с повторением из двух символов (плюса и запятой) по ${\displaystyle n-1}$ квадратам: $${\displaystyle {\overline {A}}_{2}^{n-1}=2^{n-1}}$$