2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Количество разбиений числа на суммы из m слагаемых
Сообщение25.10.2007, 20:58 


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

 Профиль  
                  
 
 Re: Количество разбиений числа на суммы из m слагаемых
Сообщение25.10.2007, 21:23 
Заслуженный участник
Аватара пользователя


01/03/06
13626
Москва
Amigo писал(а):
Дано некоторое число n. Сколько существует кортежей <a_1,a_2,..,a_m>
состоящих из m элементов таких, что a_1+a_2+,..,+a_m = n ?
Бесконечно много (даже несчётно), если ничего не сказано про свойства элементов кортежей.

 Профиль  
                  
 
 
Сообщение25.10.2007, 21:30 


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

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

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

 Профиль  
                  
 
 
Сообщение25.10.2007, 21:51 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение25.10.2007, 22:04 


11/03/06
236
незваный гость писал(а):
при фиксированном $m$?

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

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

 Профиль  
                  
 
 
Сообщение25.10.2007, 22:27 
Заслуженный участник
Аватара пользователя


01/03/06
13626
Москва
Возможно, это: 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 
Аватара пользователя


19/08/07
113
Краснодар
Цитата:
Все рассматриваемые здесь числа натуральные плюс ноль.

а чтобы получить $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 
Заслуженный участник
Аватара пользователя


17/10/05
3709
: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 
Аватара пользователя


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

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

 Профиль  
                  
 
 
Сообщение26.10.2007, 09:25 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение26.10.2007, 09:48 
Аватара пользователя


19/08/07
113
Краснодар
Теперь помощь уже нужна мне, а не Amigo :)

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

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

 Профиль  
                  
 
 
Сообщение26.10.2007, 10:16 
Заслуженный участник
Аватара пользователя


17/10/05
3709
: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 
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение26.10.2007, 12:19 
Заслуженный участник


09/02/06
4382
Москва
кортежей длины 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 
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 16 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group