Сложности в изучении комбинаторики(совсем в отчаянии)

[Yadryara]

romzes200677 в сообщении #1396686 писал(а):

далее добавляю единицу ко второму разряду слева :
1219

Сразу стоп. Если вы решили придерживаться естественного порядка, то есть не убывания, то после 2-ки не может идти единица. То есть на третьем месте должна стоять 2-ка или большая цифра! Неужто это не очевидно?

romzes200677 в сообщении #1396686 писал(а):

Мне тут Munin предложил свести задачу я так понимаю к рекурентной, может так проще мне будь подсчитать (если конечно я правильно все понял)?

Думаю, да. Я тоже вам это предлагал:

Yadryara в сообщении #1394302 писал(а):

Продолжайте добросовестно выписывать способы для $9$-и шаров, $10$-и и так далее.

От 4-х до 8-ми шаров я вам уже расписал. Надо сравнивать соседние варианты между собой, разумеется.

[Munin]

romzes200677 в сообщении #1396686 писал(а):

Мне тут Munin предложил свести задачу я так понимаю к рекуррентной, может так проще мне будь подсчитать (если конечно я правильно все понял)?

Не "проще", а "вообще возможно". Потому что ясно, что перебором - это не подсчёт.

-- 30.05.2019 19:49:14 --

romzes200677 в сообщении #1396686 писал(а):

Но вот рекуррентное отношение не придумаю.

А почему бы это?

(пишется с двумя "р": рекуррентное)

[Yadryara]

Кстати, на всякий случай, дополню.

romzes200677 в сообщении #1396686 писал(а):

У меня идут повторы , я что-то не так неверно делаю и вас не понял ?

Похоже, и то, и другое.

Yadryara в сообщении #1396696 писал(а):

Если вы решили придерживаться естественного порядка, то есть не убывания, то после 2-ки не может идти единица. То есть на третьем месте должна стоять 2-ка или большая цифра! Неужто это не очевидно?

Это же справедливо для всех цифр. Уж коли я располагаю расклады по не убыванию, то имею в виду, что каждая правая цифра не меньше любой из более левых. Обратите внимание на эти $18$ раскладов, они все такие. И все другие разбиения, которые я приводил — тоже. Как это можно было не заметить-то...

romzes200677 в сообщении #1396686 писал(а):

1318
1327

Соответственно, здесь на третьем месте должна стоять $3$-ка или большая цифра. Эти соображения сильно упрощают перебор.

[romzes200677]

Yadryara
ОГРОМНОЕ вам спасибо !!! Наконец то с перебором разобрался , действительно упрощается в разы . Вариантов на порядок меньше. Круто.
Теперь осталось рекурсивно решить .

Munin
Я немного не понял вопрос

Munin в сообщении #1396714 писал(а):

А почему бы это?

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

[romzes200677]

Yadryara
К сожалению идей новых не пришло, для меня слишком сложная задача. Вроде и видео посмотрел про упорядоченное и неупорядоченное разбиение на слагаемые. Но у нас ограничение на количество корзин, такого в том видео нет. Вот такие дела. Тут я так понял не закономерность перекладывания шаров нужно искать (как я в начале думал) ,а в целом использовать количество вариантов (с меньшим количество шаров) для расчета большего.Для неупорядоченных разбиений где не ограничено количество слагаемых рекуррентная формула $F(n;n_1,n_2,..,n_k)=F(n-n_1;n_1...n_k)+F(n;n_2,...n_k)$ , но я бы до такого никогда сам не додумался.

[Yadryara]

romzes200677, это не страшно, что вы не догадались. Страшно будет, если вы не посчитаете варианты "б", "в" и "г" для $13$ по $4$. Давайте уже сверять результаты. Мои с вашими.

[romzes200677]

Yadryara
Здравствуйте.

Наконец я посчитал.Проверьте пожалуйста.

Ответы :

б) 220 вариантов
в) 2532530 вариантов
г) 25572976 вариантов

[Yadryara]

romzes200677, доброго времени суток.

"б" и "в" — совпали, "г" — конечно нет. Приведите, пожалуйста, расчёты.

[romzes200677]

Yadryara
Прошу прощения , по невнимательности формулу неправильно записал.
Для варианта
г) 60780720 вариантов.
Проверьте пожалуйста.

[Yadryara]

romzes200677 в сообщении #1398585 писал(а):

г) 60780720 вариантов.

Да! А как получено? Умножили количество для "в" на $4!$ или все ж таки другим способом?

[Yadryara]

romzes200677, я свой вопрос не снимаю, но попробую подытожить.

Если нам надо разложить $n$ шаров по $m$ непустым корзинам, то количество способов для соответствующих вариантов равно

a) Количеству разбиений натурального $n$ на $m$ ненулевых натуральных слагаемых $P(m,n)$

б) $\binom{n-1}{m-1}$

в) Числам Стирлинга второго рода $S(n,m)$

г) $m!S(n,m)$

[romzes200677]

Yadryara
Да , я умножил вариант в) на 4! .

[Yadryara]

romzes200677, а вариант "в" как посчитали?

[romzes200677]

Yadryara
Вариант в) посчитал по ранее выведенной нами формуле.Подставил все раскладки и посчитал.

Yadryara в сообщении #1387958 писал(а):

ПМСМ, итоговая формула варианта "в" заслуживает крупного плана. Исправляем скобки на крупные, убираем необязательные $z$ и точки:

$$ \frac{\left(\sum\limits_i {a_i}{k_i}\right)!}{\prod \limits_i a_i!^{k_i} k_i! } $$

[Yadryara]

romzes200677, так я и думал. Я тоже это делал. $18$ не самых коротких дробей обсчитать — способ, мягко говоря, не самый эффективный.

Я ранее уже предлагал обратиться к степенному способу.

Вот мы раскладывали $5$ шаров по $2$-м корзинам.

Connector в сообщении #1392810 писал(а):

$30=2^{5}-2$

Поскольку у нас пустых корзин нет, мы из общего количества, то есть из $2^5$ вычли все $2$ варианта с одной пустой корзиной.


Ещё мы раскладывали $7$ шаров по $3$-м корзинам.

Yadryara в сообщении #1389100 писал(а):

$3^7-\binom31-\left(2^7-\binom21\right)\cdot\binom31=1806$

Поскольку у нас пустых корзин нет, мы из общего количества, то есть из $3^7$ вычли все $3$ варианта с двумя пустыми корзинами, а затем вычли все $378$ вариантов с одной пустой корзиной.


А теперь мы раскладываем $13$ шаров по $4$-м корзинам:

$4^{13}-\binom41-\left(2^{13}-\binom21\right)\cdot\binom42-\left(3^{13}-\binom31-\left(2^{13}-\binom21\right) \cdot\binom31\right)\cdot\binom41=60780720$

Поскольку у нас пустых корзин нет, мы из общего количества, то есть из $4^{13}$ вычли все $4$ варианта с тремя пустыми корзинами, вычли все $49140$ вариантов с двумя пустыми корзинами, а затем вычли все $6279000$ вариантов с одной пустой корзиной.

А затем уже можно разделить на $4!$ и получить количество для "в".

romzes200677 в сообщении #1394292 писал(а):

Я даже не представляю что будет если мне дать разложить 15 шариков по 7 корзинам , наверно мои мозги взорвутся

Не взорвутся Только лучше всё же не перескакивать от $4$-х корзин к $7$-и, а разложить пока что $15$ по $5$.