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

[Lia]

Придется и мне сделать неприятное дело.

vpb
Munin
Предупреждение за использование раздела не по назначению: сообщения
post1400854.html#p1400854
post1400864.html#p1400864
post1401525.html#p1401525
и упомянутые здесь удаленные.

[wrest]

Ещё о разбиениях.
В OEIS есть последовательность, A000041 -- количество разбиений числа на слагаемые.
Там написана куча всего, и что это не только количество разбиений но и то и сё и пятое и десятое... Большая, можно сказать, статья.
Там есть и несколько способов расчета количества разбиений, в т.ч. через производящие функции как нравится ув. arseniiv, и рекурсивные способы и другие.

в PARI/GP есть специальные функции которые считают количество разбиений, например для варианта a) задачи им. Yadryara (разложить непомеченные шары в непомеченные урны не менее одного шара в урну) есть функция посчета numbpart, работает она так:
? numbpart(7)
%1 = 15
Это общее количество разбиений числа 7 на слагемые.
Есть также генератор разбиений, функция partitions, которая выдаёт все разбиения, или только соответствующие ограничениям.
Для нашего случая работает так
? partitions(7,,[3,3])
%1 = [Vecsmall([1, 1, 5]), Vecsmall([1, 2, 4]), Vecsmall([1, 3, 3]), Vecsmall([2, 2, 3])]
Выдает разбиения числа 7 на не менее 3 и не более 3 частей (т.е. ровно на три части).
В PARI/GP есть оператор # который выдает количество элементов массива, вектора и т.п., так что количество по варианту а) задачи считается так:
? #partitions(7,,[3,3])
%1 = 4
То есть таких разбиений 4.
Дальше можно пользоваться этим результатом и по каждому из 4 разбиений посчитать количество вариантов.
Обозначения:

wrest в сообщении #1387316 писал(а):

Представим разбиение числа на слагаемые шаров на урны ($n$ шаров по $m$ урнам) в новых обозначениях так
$n=\sum \limits_i {k_ia_i};m=\sum \limits_ik_i$ и $\forall i\ne j:a_i \ne a_j$
То есть $a_i$ - это сколько шаров в урне, а $k_i$ - это сколько таких урн, при том что $a_i$ не повторяются (все $a_i$ различны)
Например для расклада 223
$a_1=2;k_1=2$
$a_2=3;k_2=1$

Формула:

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

$$ \dfrac{(\sum\limits_{i} {a_i}\cdot{k_i})!}{\prod \limits_i a_i!^{k_i} \cdot k_i! } $$

Для облегчения итерирования по разбиениям, в PARI/GP есть оператор forpart, которые пербирает все разбиения удовлетворяющие условию. На нашего варианта а) он работает так:
? forpart(v=7,print(v),,[3,3])
Vecsmall([1, 1, 5])
Vecsmall([1, 2, 4])
Vecsmall([1, 3, 3])
Vecsmall([2, 2, 3])
Соответственно, вместо print(v) можем вставить обработку конкретного разбиения (которое помещается в вектор v) - подсчет количества вариантов, накопление суммы.

Если надо только проверить правильно ли считается количество, то в PARI/GP есть специальные функции которые прямо вычисляют все варианты. Так что для всех наших вариантов ответы получаем прямо вот так, не мудрствуя лукаво:
? variant_a(n,m)=#partitions(n,,[m,m]);
? variant_a(7,3)
%1 = 4

? variant_b(n,m)=binomial(n-1,m-1);
? variant_b(7,3)
%1 = 15

? variant_v(n,m)=stirling(n,m,2);
? variant_v(7,3)
%1 = 301

? variant_g(n,m)=m!*stirling(n,m,2);
? variant_g(7,3)
%1 = 1806

Для чего я это написал: я всё ещё думаю что romzes200677 надо написать и отладить программы для расчета вариантов а-г, а чтобы не сверяться все время с форумом, пользоваться короткими функциями которые уже есть в матпакетах, в том же PARI/GP
И освоить не только задачи а-г, но освоить всё "двенадцатизадачие", сформулированное в книжке Кнута (4 Том "Искусства программирования", раздел 7.2.1.4):

[Yadryara]

wrest, я вам больше скажу, я специально не упоминал OEIS, дабы не искушать нашего ТС, ибо там есть все числа, встречавшиеся в рассмотренных задачах "а"-"г". Хотелось бы, чтобы он всё-таки решал сам, не подглядывая в ответ.

Спасибо, очень интересно. Вообще, про PARI на русском языке интересно. Возможно, ваш пост больше подходит для темы «интерактивный курс: введение в программирование на PARI/GP»

Давайте попросим модераторов отделить эти два наших поста в ту тему.

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

[wrest]

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

я вам больше скажу, я специально не упоминал OEIS, дабы не искушать нашего ТС,

Да, ну так времени-то сколько прошло... Пора, ящетаю, открыть двери в новый дивный мир

[_Ivana]

Набрел на тему из жалобы модераторам в соответствующем разделе

Дисклеймер для ТС: я не математик, простой программист, и не знаю все эти страшные сочетания/размещения и прочие биномиальные коэффициенты. Но, как уже писал Munin, при решении алгоритмических задач чаще всего важно не просто получить число вариантов, жонглируя комбинаторными формулами, а написать алгоритм, перебирающий сами эти варианты (с отсечением лишних веток), для получения самих вариантов перебора. И здесь я бы рекомендовал вам забыть отложить на время волшебные формулы получения одних чисел их других, а обратить больше внимания на алгоритмы. Например, вы писали:

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

И вот когда я в итоге разобрал как решают задачу о сдаче не пойму все равно некоторые моменты :
1)
(какое кол-во монет можно выдать выдавая сумму n , если есть неограниченное кол-во монет номиналом 1,3,5 , порядок выдачи сдачи важен)
Рекурентая формула $S_n=\min ( 1+S(n-1),1+S(n-3),1+S(n-5))$ , S[0]=1,S[1]=1 (так до суммы 4), остальное вычисляем по рекурентной формуле

Вот по этому видео я разбирал задачу 1 https://www.youtube.com/watch?v=3tE1Ht6 ... S&index=17

2)
Так вот подобно комбинаторике , немного изменив условие задачи опять решается она совсем по другому
(какое минимальное кол-во монет можно выдать выдавая сумму n , если есть неограниченное кол-во монет номиналом 1,3,5 , порядок выдачи сдачи важен)
$S_n=1+S(n-1)+1+S(n-3)+1+S(n-5)$ , S[0]=0,S[1]=1

Вот по этому видео я разбирал задачу 2 https://www.youtube.com/watch?v=eOpyywc ... S&index=21


Почему во второй задаче прибавляется единица , $1 +S[n-k] $ и затем находится минимум из полученных сумм .. .в формуле , а в первой выданная монета не учитывается просто .. ?

И если вы не понимаете почему это все (а также, что рекуррентные формулы к вариантам у вас перепутаны с точностью до наоборот и что важность порядка выдачи монет во второй задаче - лишнее условие, никак не влияющее на ответ), то стоит это разобрать. Здесь 1 - это одна монета (а не ее номинал! нам же надо выяснить количество монет), номинал которой вычитается из общей суммы. При этом задача сводится к самой себе на уменьшенном значении аргумента - а значит на натуральных аргументах наша рекурсивная формула вычислится за конечное число шагов. Как видите, в обоих рекуррентных формулах нет никаких страшных комбинаторных букв. Хотя и рассчитываться в таком наивном виде они будут неоптимально и долго. Но тут мы призываем на помощь волшебную динамику (судя по цитате, вы не стесняетесь смотреть видео на ютубе - стрим про ДП https://www.youtube.com/watch?v=OnUXYVd-EuY )

[romzes200677]

Привет всем , решил так сказать подытожить все мои старания, проблемы начались у меня при попытке устроиться на работу программистом и решении задач по алгоритмам.Выяснилось что нужна математика но вот какой раздел тут был вопрос. В итоге все таки я устрился работать программистом c# (обычная поддержка и сопровождение копроративного приложения на IIS сервере) в средней по размеру для региона России компании и работаю там успешно 1 год уже с моим текущим уровнем знаний по математике. На данной должности мне оказались нужны лишь поверхностные знания по комбинаторике .

Основная сложность в том чтобы помнить(найти/определить) все зависимости изменяемого участка кода , чтобы не сломать что работает. Получается ты придумываешь условие при котором должно что-то отработать , все запускаешь , бах ,не учел еще какие то зависимости, переписал условие , опять проверяешь , еще одна зависимость найдена , переписываешь по сто раз этот кусок кода и такая лапша получается .Потом получается огровное неоптимальное ветвление с кучей условий, его начинаешь упрощать , и это дается мне крайне тяжело. Вобщем огромное преимущество дает хорошая память , грубо говоря ты помнишь алгоритм какого-то блока и его зависимости . Возможно со временем все таки я запомню логику программы , но пока лишь в общих чертах за 1 год. Мне кажется хорошие математики более быстро разбираются в коде программы и быстрее вникают в ее алгоритм , вот где их гланое преимущество. Программу мою разрабатывали 4 человека в серьезной фирме в течении 1 года. Теперь я один на поддержке :) .

Вобщем если уровень математики посредственный программистом работать можно , но будете медленно въезжать в существующий код и долго возиться с задачами, но если приводить аналогию с летчиками - не все летчики являются летчиками испытателями , есть и обычные которые управляют небольшими самолетами. Не знаю , может со временем разгонюсь, но пока за 1 год я начал работать быстрее процентов на 20 % . Добавить кнопку с табличкой и формой на страницу(+ код извлечения нужных данных) в моем приложении чтобы ничего не поломать занимает у меня неделю ( бизнес логика там не простая , правда на мне front + backend ) .Короче здесь я fullstack джун . В очень серьезную фирму вряд ли я смогу устроиться с моим уровнем подготовки математики , а вот что-то попроще возможно. Так что может кто-то найдет из программистов начинающих тему думаю будет интересна кем можно устроиться с таким уровнем знаний. А форуму и всем ребятам огромное спасибо что помогали, думаю все равно часть этих знаний у меня все равно осталась и когда-то пригодится все равно. Всем удачи ...

[vpb]

Пожалуйста. И Вам наилучшие пожелания на новом месте работы. А математика, да, способствует тому, чтобы ум в порядок приводить.