Количество разбиений числа на суммы из m слагаемых

[Amigo]

Дано некоторое число $n$. Сколько существует кортежей $<a_1,a_2,..,a_m>$
состоящих из $m$ элементов таких, что $a_1+a_2+\cdots +a_m = n$ ?

[Brukvalub]

Amigo писал(а):

Дано некоторое число n. Сколько существует кортежей <a_1,a_2,..,a_m>
состоящих из m элементов таких, что a_1+a_2+,..,+a_m = n ?

Бесконечно много (даже несчётно), если ничего не сказано про свойства элементов кортежей.

[Amigo]

Все рассматриваемые здесь числа натуральные плюс ноль.

Добавлено спустя 3 минуты 40 секунд:

Ясно, что если у нас имеется число n и рассматриваются кортежи длины 2. То их количество равно n+1. Но как расчитать их количество для кортежей произвольной длины?

[незваный гость]

при фиксированном $m$? Рассмотрите ряд из $n$ единиц. Вам в него надо кинуть $m-1$ запятую (между единицами, до или после). Все единицы между соседними запятыми складываем, и называем $a_k$.

[Amigo]

незваный гость писал(а):

при фиксированном $m$?

Конечно.

незваный гость писал(а):

Рассмотрите ряд из $n$ единиц. Вам в него надо кинуть $m-1$ запятую (между единицами, до или после). Все единицы между соседними запятыми складываем, и называем $a_k$.

Я вообще не понимаю каким образом Вы к этому пришли а также что именно нужно сделать.
Вот выписали 5 едениц
,1,1,1,1,1,
начинаем складывать еденицы между соседними запятыми. Между соседними всегда
только одна еденица.Того получим пять. И что это нам дало?

[Brukvalub]

Возможно, это: http://lelina114.ucoz.ru/_ld/0/16_tauhen-new.pdf Вам поможет?

Добавлено спустя 3 минуты 57 секунд:

Amigo писал(а):

Вот выписали 5 едениц
,1,1,1,1,1,
начинаем складывать еденицы между соседними запятыми. Между соседними всегда
только одна еденица.Того получим пять. И что это нам дало?

Запятых должно быть ровно на 1 меньше, чем требуемое число слагаемых. а Вы их "от фонаря" понаставили и ждете чудес, не пытаясь вникнуть в суть.

незваный гость писал(а):

при фиксированном $m$? Рассмотрите ряд из $n$ единиц. Вам в него надо кинуть $m-1$ запятую (между единицами, до или после). Все единицы между соседними запятыми складываем, и называем $a_k$.

(выделение -моё)

[enko]

Цитата:

Все рассматриваемые здесь числа натуральные плюс ноль.

а чтобы получить $a_k=0$ нужно кинуть две запятые на одно место?
что если два соседних $a_j=0$; $a_k=0$ ?
может чтобы не было путаницы рассмотреть $n+1$ и исключить$0$

тогда нужно будет выбрать для m-1 запятой места из n вариантов т.е. $C_n^{m-1}$

вот похожая задача http://www.lib.mexmat.ru/forum/viewtopic.php?t=9482

[незваный гость]

Итак, $n = 5$, $m = 3$. Кидаем две запятые:

$, , 1 1 1 1 1 \to ‹0,0,5›$
$ 1, 1 1 1, 1 \to ‹1,3,1›$
$ 1 1, 1 1 1, \to ‹2,3,0›$

Дальнейшее, надеюсь, понятно.

P.S. Если нули мешают понять, что происходит, можно «приклеить» по единичке слева к запятой…

[enko]

Если две или более запятых на одно место, сложнее посчитать кол-во вариантов.

Ответ у меня не правильный?

[незваный гость]

Не знаю. Я пытался помочь Amigo решить его задачу. Прочитайте про приклеивание.

[enko]

Теперь помощь уже нужна мне, а не Amigo

Не понимаю зачем и как приклеивать, как тогода посчитать кол-во вариантов?
Поясните точным математическим языком, что значит приклеить к запятым...?

Ну всё-таки мой ответ правильный или нет?!!!

[незваный гость]

О связи двух задач:

Исходные единицы — синие. Приклеенные единицы — коричневые.

, , 1 1 1 1 1 $\to$ ‹0,0,5› $\Leftrightarrow$ 1, 1, 1 1 1 1 1
1, 1 1 1, 1 $\to$ ‹1,3,1› $\Leftrightarrow$ 1 1, 1 1 1 1, 1
1 1, 1 1 1, $\to$ ‹2,3,0› $\Leftrightarrow$ 1 1 1, 1 1 1 1,

То есть, каждому левому раскладу мы поставили во взаимно-однозначное соответствие правый. Но в правом уже нет 0.

[enko]

А если рассматривать случаи когда нулей 1,2,3 и больше?
Не понимаю как при таком рассуждении посчитать кол-во вариантов..
И каков же Ваш ответ?
Проведите, пожалуйста, решение до конца.

[Руст]

кортежей длины 1 - $1=C_n^0=C_{n+1}^1-C_n^1$, отсюда получаются кортежей длины 2

$$\sum_{k=0}^n(C_{n+1-k}^1-C_{n-k}^1)=C_{n+1}^1=C_{n+2}^2-C_{n+1}^2$$

и так по индукции кортежей длины k $C_{n+k-1}^{k-1}$.

[enko]

Это же количество сочетаний с повторениями из $n$ по $k-1$.
Понятно, выбираем для $k-1$ запятых места из $n$ возможных.