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

[romzes200677]

Yadryara
Здравствуйте снова.
Я прорешал задачу для 5 шаров и 2-х корзин. Ответы следующие:
а) 2 способа : (4ш,1ш ; 3ш,2ш)
б) 4 способа (4,1; 1,4; 3,2 ; 2,3)
в) 15 способов :
раскладки следующие для варианта (3ш,2ш):
123 45
124 35
125 34
134 25
135 24
145 23
234 15
235 14
345 12
452 13

раскладки следующие для варианта (4ш,1ш) :
1234 5
1235 4
1245 3
1345 2
2345 1

г) 30 способов $15 \cdot 2! =30 $

Проверьте пожалуйста.

[Connector]

Я проверил — правильно. Вариант г) я бы просчитал так: $30=2^{5}-2$, но у Вас тоже правильно.

[Yadryara]

romzes200677, Доброго! Да, всё верно. Ну что ж, теперь попробуйте получить формулу для раскладок для варианта "г". По аналогии с "в".

После чего, полагаю, вам не составит труда разложить $13$ шаров по $4$-м корзинам.

-- 13.05.2019, 19:53 --

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

235 14
345 12
452 13

Кстати, здесь лучше бы смотрелось

$235\; 14$

$245\; 13$

$345\;12$

А то у вас все варианты трёх шаров, кроме одного, шли в порядке неубывания.

[Yadryara]

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

раскладки следующие для варианта (3ш,2ш):

Кстати, чтобы не запутаться, лучше придерживаться уже использовавшейся нами ранее терминологии. $3$ш, $2$ш — это один из двух имеющихся раскладов. И фразу лучше было бы построить так:

"Варианты следующие для расклада (3ш,2ш):"

Можно вместо "вариантов" писать "способов". Но слово "расклад" у нас уже зарезервировано. Напомню формулу для количества вариантов "в" того или иного расклада:

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

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

Как её изменить, чтобы она сгодилась для количества вариантов "г" того или иного расклада?

[romzes200677]

Yadryara
Здравствуйте. К сожалению забываются немного со временем мои наработки и расчеты , которые я ранее с вами делал, без практики. Пришлось снова вспоминать всю мою логику расчетов , благо что все сообщения есть и я могу воспроизвести все подводные камни на которые я наступал . Эта переписка для меня бесценный учебный материал по комбинаторике в который я могу в любой момент посмотреть. Спасибо всем большое , мне кажется хороший кусочек комбинаторики мы на этих 4 задачах рассмотрели .

По логике вариант г) отличается от варианта в) как уже ранее сказали на $n!$ перестановок корзин , соответственно можно просто домножить предыдущую формулу на число перестановок корзин.

Мой вариант формулы

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

Получается мы для каждого варианта раскладки шаров считаем по данной формуле и складываем далее результаты

Проверьте пожалуйста.

Мне считать раскладку для 13 шаров по 4 корзинам ?

[Yadryara]

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

Эта переписка для меня бесценный учебный материал по комбинаторике в который я могу в любой момент посмотреть.

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

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

По логике вариант г) отличается от варианта в) как уже ранее сказали на $n!$ перестановок корзин , соответственно можно просто домножить предыдущую формулу на число перестановок корзин.

Да, конечно. Так что формула верная, ПМСМ.

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

Получается мы для каждого варианта раскладки шаров считаем по данной формуле и складываем далее результаты

Можно и так. А можно сначала получить количество для "в", а потом умножить.

Ещё короче сделать "степенны́м" способом.

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

Мне считать раскладку для 13 шаров по 4 корзинам ?

Да. Желательно разными способами. Я уже давно подсчитал двумя способами, у меня сошлось. Теперь с нетерпением жду, когда же мы будем сверять результаты...

[romzes200677]

Yadryara
Здравствуйте. У меня получилось 18 уникальных раскладок и ответ 25572976 вариантов разложить 13 шаров по 4 корзинам.
Проверьте пожалуйста.

[Yadryara]

romzes200677, ответ $18$ для "a" верный. Кстати, знаете как его проверить?

А $25$ миллионов для какого пункта?

[Yadryara]

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

25572976 вариантов разложить 13 шаров по 4 корзинам.

Что-то вы замолчали. Это неверно для любого из 3-х оставшихся пунктов("б", "в" или "г"). Выкладывайте решение, плиз. Чего уж там. Будет проверено до первой ошибки.

[romzes200677]

Yadryara
Здравствуйте. Это ответ для варианта г) .

Но к сожалению признаюсь что вариант а) у меня получился довольно тяжело. Пришлось писать программу для проверки правильности перебора.И вы знаете я заметил что мне крайне тяжело дается перебор.Вы вот когда перебираете варианты у вас какой то алгоритм есть , а вот для 4 корзин я алгоритма не нашел и запутался . Я даже не представляю что будет если мне дать разложить 15 шариков по 7 корзинам , наверно мои мозги взорвутся , для меня это почему то тяжело. Это практикой тренируется опять же или от природы дано , вот не пойму. Конечно я могу написать программу которая распечатает все варианты , но так я не пойму закономерности перебора. Знаю с точки зрения программирования это решается рекурсивно(разбиение на слагаемые) , но придумать как не смог , только итеративное решение .

Мой алгоритм для перебора 13 шаров по 4 корзинам такой(вариант а):
Берем раскладываем в каждую корзину по 1 шару, из 13 осталось 9 шаров.Итого сводится задача к разложению 9 шаров по 4 корзинам.Вначале мы берем 9 шаров раскладываем по 2 корзинам (8-1-0-0,7-2-0-0,6-3-0-0,5-4-0-0). Все дальше идут повторы. Теперь раскладываем по 3 и 4 корзинам шары.Для этого дополнительно разделяем варианты 6-3-0-0(т.к 3 шара можно переложить по оставшимся корзинам) 6-2-1-0 и 6-1-1-1.Далее берем вариант 5-4-0-0 и раскладываем 4 шара по оставшимся корзинам.
5-3-1-0,5-2-2-0,5-2-1-1. И вот дальше я совсем запутался т.к идут повторы и закономерности не уловил .Скорее всего мой алгоритм перебора частично правильный .Может подскажете где я неправильно размышляю и ошибаюсь?

[Yadryara]

Хорошо, давайте снова разберём вариант "а". Это задача на разбиение. Разложить $13$ шаров по $4$-м непустым корзинам — то же самое, что разбить число $13$ на $4$ ненулевых натуральных слагаемых.

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

Берем раскладываем в каждую корзину по 1 шару, из 13 осталось 9 шаров.Итого сводится задача к разложению 9 шаров по 4 корзинам.

Я так обычно не делаю. Раскладываю сразу $13$.

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

Скорее всего мой алгоритм перебора частично правильный

Да, просто вы не довели его до конца.

Давайте пойдём от простого к сложному. Очевидно, разложить $4$ шара по $4$-м непустым корзинам можно единственным способом. И $5$ шаров по $4$-м непустым корзинам — тоже. А вот $6$ по $4$-м — уже двумя способами.

Запишем эти способы по не убыванию:

$4$ по $4$-м — 1 способ. $1111$.
$5$ по $4$-м — 1 способ. $1112$.
$6$ по $4$-м — 2 способа. $1113$, $1122$.
$7$ по $4$-м — 3 способа. $1114$, $1123$, $1222$.
$8$ по $4$-м — 5 способов. $1115$, $1124$, $1133$, $1223$, $2222$.

Продолжайте добросовестно выписывать способы для $9$-и шаров, $10$-и и так далее. Группируйте их так, как вам удобно. Рано или поздно вы подметите некоторые закономерности и научитесь ничего не пропускать и не дублировать. Напишите здесь все результаты.

[romzes200677]

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

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

Рано или поздно вы подметите некоторые закономерности

- этого момента не наступило и видимо не всем это дается так легко.
Мне пришел только в голову алгоритм последовательного перебора с ручным вычеркиванием дублей. Я просто взял и начал перебирать числа последовательности 1 шт(1 корз) -1 шт(2 корз) -1 шт(3корз)-10 шт(4 корз). И поочередно как бы перекладывал шарик из одной корзины .
Получилась такая возрастающая последовательность раскладок:
1:1:1:10
1:1:2:9
1:1:3:8
1:1:4:7
1:1:5:6
1:2:2:8
1:2:3:7
1:2:4:6
1:2:5:5
1:3:3:6
1:3:4:5
1:4:4:4
2:2:2:7
2:2:3:6
2:2:4:5
2:3:3:5
2:3:4:4
3:3:3:4

Однако мне пришлось перебрать около 120 вариантов и вычеркнуть около 100 дублей , задача я бы сказал на очень внимательных , а если 1000 вариантов перебирать , это же не реально. Т.е я хотел найти алгоритм который исключает перебор дублей , а перебирает только уникальные раскладки(без повторений предыдущих).
К сожалению алгоритм мной не найден , сколько я не думал. Может кто-нибудь подсказку даст , или наводящий вопрос, а не ответ сразу , что бы я сам решение нашел ?

[Munin]

Вы упёрлись в один способ перебора вариантов.
Попробуйте свести задачу к другим. Что если бы вам были известны количества раскладок меньшего числа шариков? Или по меньшему числу корзин? Или и то и другое?

[Yadryara]

romzes200677, да я тоже на форуме стал реже бывать.

Во-первых, нужен удобный способ записи. Зачем вам эти двоеточия? У меня же их нет. Всё те же $18$ вариантов можно было бы записать гораздо короче, строго следуя правилу: количество шаров в той или иной корзине записывается ровно одной буквой. Для этого надо брать систему счисления с основанием больше наибольшего используемого числа. В данном случае, раз уж у нас в одном из раскладов встречается десятка, лучше взять знакомую 16-ричную СС, хотя можно и 11-ричную. И записывать расклады как числа:

$1. 111A$

$2. 1129$

$3. 1138$
...

$18. 3334$

Обратите внимание, что соотв. числа строго возрастают. И, как только мы уже не сможем увеличить число хотя бы на единицу, перебор закончен. У меня такой перебор обычно получается очень быстро.

Есть рекуррентная формула, а есть и точная явная. Явную, помнится, сам выводил. Например, если нам надо разбить $n$ на $4$ и если $b$ — остаток от деления $n$ на $3$, то общая формула для количества разбиений для нечётных $n$:

$$P(4, n) = \frac{n^3 + 3n^2 - 9n - 24b^2 + 56b - 27}{144}$$

Подставьте сюда $13$ вместо $n$ и $1$ вместо $b$. Что вы получите?

Можете попробовать вывести аналогичную формулу для чётных $n$. Или для $3$-х корзин.

[romzes200677]

Yadryara
Все равно не понял как вы избегали повторов.

Моя последовательность наборов в 16-ричной системе счисления:
111A
1129
1138
1147
1156

далее добавляю единицу ко второму разряду слева :
1219
1228
1237
1246
1255
Далее еще единицу ко второму разряду пока не дойдем до 10 (А)
1318
1327
1336
1345

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



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

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