2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Количество разбиений числа на суммы из m слагаемых
Сообщение25.10.2007, 20:58 
Дано некоторое число $n$. Сколько существует кортежей $<a_1,a_2,..,a_m>$
состоящих из $m$ элементов таких, что $a_1+a_2+\cdots +a_m = n$ ?

 
 
 
 Re: Количество разбиений числа на суммы из m слагаемых
Сообщение25.10.2007, 21:23 
Аватара пользователя
Amigo писал(а):
Дано некоторое число n. Сколько существует кортежей <a_1,a_2,..,a_m>
состоящих из m элементов таких, что a_1+a_2+,..,+a_m = n ?
Бесконечно много (даже несчётно), если ничего не сказано про свойства элементов кортежей.

 
 
 
 
Сообщение25.10.2007, 21:30 
Все рассматриваемые здесь числа натуральные плюс ноль.

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

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

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

 
 
 
 
Сообщение25.10.2007, 22:04 
незваный гость писал(а):
при фиксированном $m$?

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

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

 
 
 
 
Сообщение25.10.2007, 22:27 
Аватара пользователя
Возможно, это: 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$.
(выделение -моё)

 
 
 
 
Сообщение26.10.2007, 02:29 
Аватара пользователя
Цитата:
Все рассматриваемые здесь числа натуральные плюс ноль.

а чтобы получить $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

 
 
 
 
Сообщение26.10.2007, 09:13 
Аватара пользователя
:evil:
Итак, $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. Если нули мешают понять, что происходит, можно «приклеить» по единичке слева к запятой…

 
 
 
 
Сообщение26.10.2007, 09:18 
Аватара пользователя
Если две или более запятых на одно место, сложнее посчитать кол-во вариантов.

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

 
 
 
 
Сообщение26.10.2007, 09:25 
Аватара пользователя
:evil:
Не знаю. Я пытался помочь Amigo решить его задачу. Прочитайте про приклеивание.

 
 
 
 
Сообщение26.10.2007, 09:48 
Аватара пользователя
Теперь помощь уже нужна мне, а не Amigo :)

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

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

 
 
 
 
Сообщение26.10.2007, 10:16 
Аватара пользователя
:evil:
О связи двух задач:

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

, , 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.

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

 
 
 
 
Сообщение26.10.2007, 12:19 
кортежей длины 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}$.

 
 
 
 
Сообщение26.10.2007, 12:30 
Аватара пользователя
Это же количество сочетаний с повторениями из $n$ по $k-1$.
Понятно, выбираем для $k-1$ запятых места из $n$ возможных.

 
 
 [ Сообщений: 16 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group