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

[wrest]

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

Вот этого я и боялся , так будешь что-нибудь решать , а у задачи нет универсального решения

Поскольку вы написали

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

программисту без комбинаторики плохо, она везде там

то я бы предложил вам проверять решения/ответы моделированием. Например, напечатать все варианты раскладки шаров по урнам из задачи 1, при различных условиях (шары/урны пронумерованы/одинаковы).

(Эйлер о разбиениях)

Эйлер в труде "Разбиение чисел" (De Partitione Numerorum, 1750) писал:

Цитата:

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

Эту цитату приводит Дональд Кнут в 4-м томе "Искусства программирования"
Том 4А. Комбинаторные алгоритмы, часть 1, пункт 7.2.1.4 "Генерация всех разбиений"

[romzes200677]

Добрый день всем!
Спасибо большое ребята что мне помогаете.
Уважаемый Yadryara вас тоже благодарю что тратите на меня свое бесценное время. Я готов попрактиковаться в решении.

Вот решение варианта "В"

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

в)Шары различимы, а корзины нет — ?

Ответ в:
Кол-во сочетаний =С $\binom{3}{7}+4=39$
Расшифровка = я в начале выбираю 3 шарика чтобы было в каждом по одному + оставшиеся варианты комбинации суммы 4 (4+0,3+1,2+2,2+1+1)

Ответ

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

г)И шары, и корзины различимы — ?

:
Кол-во сочетание = $7\cdot 6 \cdot 5 +1 +6 +3+3 =223 $
Здесь т.к порядок важен мы выбираем 3 шара с учетом их порядка + 1 способ (4+0+0) + 6 способ (вариант 3+1 ) +3 вариант (2 +2) + 3 вариант (2+1+1)

Вот такие ответы будут, проверьте пожалуйста

[Yadryara]

romzes200677, и для "в", и для "г" у меня получилось гораздо больше.

Совет дня Кликайте на ник собеседника и он появится в поле для ответа.

[wrest]

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

Кол-во сочетаний

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

Кол-во сочетание =

Рекомендую вам сразу начать внимательно относиться к терминологии. "Сочетания", "размещения", "перестановки" -- это конкретные термины.

[SergeCpp]

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

всем ли дано решать задачи по комбинаторике и теории вероятностей

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

1. Дано всем.
2. Реальные успехи зависят от мотивации, количества вложенных сил, и удачного выбора учебника.

Monty Hall problem писал(а):

Paul Erdős, one of the most prolific mathematicians in history, remained unconvinced until he was shown a computer simulation demonstrating the predicted result (Vazsonyi 1999).

То есть Paul Erdős не обладал достаточной мотивацией, либо вложил мало сил, либо читал не те учебники? А также упоминаемые там же чуть выше "nearly 1,000 with PhDs"?

[romzes200677]

Yadryara
в) ответ 7*6*5=210
г)ответ $7^3=343$

[Munin]

По поводу того, куда зашла тема.

romzes200677, я очень рад, что вы решаете задачи и получаете помощь. Однако есть кое-что ещё.

Вы начали с замечания, что вы программист, и что

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

программисту без комбинаторики плохо, она везде там

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

1. Умение составить алгоритм и программу, осуществляющие тот или иной перебор, а не просто посчитать их количество. Это подразумевает умение конструктивно построить один из перебираемых вариантов. С другой стороны, это означает, что перебор можно упростить (в определённых пределах), например, допуская "лишние" варианты, но отвергая их по мере возникновения.

2. Умение оценить асимптотическое поведение комбинаторных функций и соотношений. Простейший вопрос такого типа, например: оценить поведение $C_{n/2}^{n/2}$ при больших $n,$ или хотя бы записать неравенство с оценками $O(n!),O(2^n),O(n^k).$

3. Умение переформулировать одну комбинаторную задачу в другую, преобразуя вычисления в более оптимальные. Вот это умение действительно тренируется обычными математическими задачами по комбинаторике. Однако иногда стандартные математические переформулировки с вычислительной точки зрения не улучшают, а ухудшают дело (например, приём "считать объекты различными, а потом разделить на их число перестановок"). Здесь тоже нужен "программистский взгляд и подход".

[wrest]

Совершенно согласен с Munin

Вместо угадывания ответа, мне кажется лучше бы вам его проверить выписав все эти способы раскладки шаров, но не на бумаге, а написав программу, которая это сделает за вас. Так вы почувствуете "комбинаторику", так сказать, на практике. Идеи по алгоритму генерации можете подсмотреть например у упоминавшегося Кнута, вот например упоминавшийся пункт 7.2.1.4 из Искусство программирования (ссылка не подставилась, в гугле набираете "генерация всех разбиений", смотрите первый результат в выдаче).

[SergeCpp]

Конкретная математика Кнута тоже будет полезной программисту.

Биномиальные коэффициенты и Дискретная вероятность в числе основных тем книги.

[Yadryara]

romzes200677, нет конечно же, не всё так просто.

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

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

Неплохо бы сначала на бумаге, хотя бы, а потом здесь на форуме, ибо числа в задаче не сильно большие. Неучтённые(дважды учтённые) варианты сразу будут видны. Сначала, пункт "в", как более простой. Шары перенумеровать от $1$ до $7$.

Вот например, раскладка $115$, то есть по одному шару в две корзины и $5$ в третью.

$1 \quad 2 \quad 34567$

$1 \quad 3 \quad 24567$

$1 \quad 4 \quad 23567$
...

$6 \quad 7 \quad 12345$

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

$1 \quad 2$

$1 \quad 3$

$1 \quad 4$
...

$6 \quad 7$

romzes200677, сколько вариантов для раскладки $115$ ? Легко же считается.

Затем посчитайте способы для трёх других раскладок: $124$, $133$ и $223$.

Потом уже можно пробовать обобщать, когда в голове всё окончательно устаканится.

[romzes200677]

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

Что касается алгоритмов я задачу в) и г) уже набросал за пару минут на java )
перебор это легко , а из-за чего весь сыр - бор с комбинаторикой , на собеседовании задали задачу "Задача о рюкзаке или задача о сдаче(размен монет)" по динамическому программированию https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D1%80%D1%8E%D0%BA%D0%B7%D0%B0%D0%BA%D0%B5 и я ее не решил, собеседование провалено и тут я понял что проблемы у меня с комбинаторикой и составлением рекурентных формул .
Вот зачем мне комбинаторика , я год программистом проработал и комбинаторика если честно не пригодилась особенно, но захотел сменить работу пройти собеседование и его не пройдешь без задач по алгоритмам , которые предполагают хорошее знание математики это факт.

И вот когда я в итоге разобрал как решают задачу о сдаче не пойму все равно некоторые моменты :
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=3tE1Ht6fm7I&list=PLUfHxBkkFMScqPOn8J0aHvd48wykQNcWS&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=eOpyywcbfbU&list=PLUfHxBkkFMScqPOn8J0aHvd48wykQNcWS&index=21

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

[wrest]

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

Что касается алгоритмов я задачу в) и г) уже набросал за пару минут на java )

И где же результат?

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

на собеседовании задали задачу "Задача о рюкзаке или задача о сдаче(размен монет)"

Так эта задача только перебором и решается, но лучше бы вам сперва закончить тут с раскладкой $n$ шаров по $k$ урнам, иначе эта тема станет хаосом.

[romzes200677]

вот г задача :

class Main {
  public static void main(String[] args) {
    int[] a={1,2,3,4,5,6,7};
        int counter=0;
        for(int i : a){
           for(int j : a){
               for(int k : a){
                   counter++;
                    System.out.println( counter +" - "+i+j+k);
                }
                
            }
        }
              
            
  }      
}

-- 22.03.2019, 19:14 --

в) алогично , только отличается условием , i != j во втором цикле и в третьем цикле условие k != j && k != i .Просто я его стер , если надо могу перенабрать код
Но тут как бы форум по математике , думаю код по программированию будет здесь лишним.
Понятное дело что этот код в лоб решает задачу, возможно более оптимальное решение думаю есть

-- 22.03.2019, 19:21 --

Yadryara
Правильно я понял что мне нужно расписать раскладку 115 шаров по 3 корзинам ?

[Yadryara]

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

Правильно я понял что мне нужно расписать раскладку 115 шаров по 3 корзинам ?

Конечно нет. По-прежнему решается задача распределения 7(семи) шаров по 3-м корзинам. Запись 115(один-один-пять) означает, что в одну корзину положили один шар, в другую тоже один, а в третью — пять.

Кстати, присоединяюсь к wrest. Зачем же переходить к другим задачам, если мы ещё не сверили ответы по всем пунктам по текущей?

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

Сколькими различными способами можно разместить 7 шаров по 3-м корзинам, если

а)И шары, и корзины неразличимы — 4.

Раз не различимы, то цифрами обозначено только количество шаров в корзинах:

1. 115
2. 124
3. 133
4. 223


б)Корзины различимы, а шары нет — 15.

Цифрами пока по-прежнему обозначено количество шаров в корзинах:

115 — 3 способа
124 — 6 способов
133 — 3 способа
233 — 3 способа

1. 115
2. 151
3. 511

4. 124
5. 142
6. 214
7. 241
8. 412
9. 421

10. 133
11. 313
12. 331

13. 223
14. 232
15. 322

В варианте "в" некоторая сложность в том, что цифры в одном случае означают количества шаров, а в другом случае — их номера.

[Munin]

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

Идеи по алгоритму генерации можете подсмотреть например у упоминавшегося Кнута

Но вначале стоит попробовать придумать их самостоятельно.

-- 22.03.2019 18:42:50 --

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

на собеседовании задали задачу "Задача о рюкзаке или задача о сдаче(размен монет)" по динамическому программированию

Динамическое программирование - отдельная тема. Её стоит изучить по стандартным книгам по алгоритмам и структурам данных. Обычно оно объясняется на задачах на графах.

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

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

Чувствую, вам не хватает именно курса "Алгоритмы и структуры данных". Например, такие книги, как Седжвик, или Кормен, Лейзерсон, Ривест.

Это совсем другой разговор. Там далеко не только одна комбинаторика.