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

[wrest]

romzes200677
Что-то у вас не выходит каменный цветок.
Давайте я подскажу.
Разберем пример подсчета способов раскладки пронумерованных шаров по непронумерованным урнам, при условии что в каждую урну попадает различное количество шаров.
Разберем раскладку 124
В первую урну можно положить шар 7 способами. Как это получается? Это количество сочетаний из семи по одному, $C_7^1$
Во вторую урну останется положить из шести два шара (т.к. один уже в первой урне). Это можно сделать $C_6^2=15$ способами.
Наконец, в третью урну останется положить оставшиеся четыре шара из четырех. Тут способ один, т.к. $C_4^4=1$
Таким образом, всего способов будет $7 \cdot 15 \cdot 1=105$

Посчитаем то же самое с другого конца, запишем расклад как 421
В первую урну кладем сочетания из 7 по 4, $C_7^4=35$, во вторую кладем сочетания из 3 по 2 $C_3^2=3$ и в последнюю кладем сочетания из 1 по 1 $C_1^1=1$
Перемножаем, получаем $35 \cdot 3 \cdot 1= 105$

Для убедительности, посчитаем расклад 241
$C_7^2 \cdot C_5^4 \cdot C_1^1 = 21 \cdot 5 \cdot 1 =105$

Пожалуйста, запишите это теперь в виде формулы, исходные данные такие: сколькими способами можно разложить по трем непронумерованным урнам $i+j+k=n$ шаров, так что количество шаров во всех урнах разное, т.е. $i\ne j;j \ne k; i \ne k$ Численные значения всех букв известны.

В следующей серии будем считать количество способов на случай какого-то совпадения $i=j$ и/или $j=k$ и/или $i=k$

[romzes200677]

wrest
Здравствуйте. Вот формула получается :
$C_n^i \cdot C_{n-i}^j \cdot C_{n-i-j}^k$

[wrest]

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

Здравствуйте. Вот формула получается :
$C_n^i \cdot C_{n-i}^j \cdot C_{n-i-j}^k$

Хорошо. Теперь допустим расклад такой, что в двух урнах одинаковое количество шаров.

Например имеем расклад 223

По нашей, покашта неоконченной формуле, получается
$N=C_7^2 \cdot C_5^2 \cdot C_3^3 = 21 \cdot 10 \cdot 1= 210$
А должно быть $105$.

Почему? И как исправить?

[romzes200677]

wrest
Нужно поделить на 2 т.к у нас в двух корзинах могут повторяться шары т.е 24 в первой корзине и 42 во второй корзине , но т.к у нас корзины не различимы мы делим на количество корзин с одинаковым количеством шаров и тогда мы исключим дубли

[wrest]

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

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

Хорошо, а если корзин с одинаковым количеством шаров будет не 2, а 3?
Например расклад 222

[romzes200677]

wrest
Путем перебора посчитал что вариантов 15 и делить нужно на 6 . Но вот закономерность пока не уловил .

-- 12.04.2019, 18:47 --

раскладку 333 нужно делить тоже на 6 , а вот раскладку 4444 нужно делить на 24

[Munin]

Это волшебное число есть число перестановок $P_n=n!$

[romzes200677]

Как мне стыдно , не увидеть очевидного

[wrest]

romzes200677
Хорошо, теперь запишите скорректированную формулу, с учетом урн с повторяющимся количеством шаров.

Тут переходим на следующий уровень обозначений.

Представим разбиение числа на слагаемые шаров на урны ($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$

Пример для расклада 2223345777 имеем всего 42 ($n=42$) шара в десяти ($m=\sum \limits_ik_i=10$) урнах пяти ($i=1...5$) типов:
$a_1=2;k_1=3$ (3 урны по 2 шара)
$a_2=3;k_2=2$ (2 урны по 3 шара)
$a_3=4;k_3=1$ (1 урна с 4 шарами)
$a_4=5;k_4=1$ (1 урна с 5 шарами)
$a_5=7;k_5=3$ (3 урны с 7 шарами)
$n=2\cdot 3+3\cdot 2 + 4 \cdot 1 + 5\cdot 1 + 7\cdot 3=42$

Сможете записать теперь формулу для количества способов, $N=...$?

[romzes200677]

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

[romzes200677]

wrest
Здравствуйте , подумал и в голову пришло только одна формула :
$\frac{C_{42}^{2}\cdot C_{40}^{2}\cdot C_{38}^{2}\cdot C_{36}^{3}\cdot C_{33}^{3}\cdot C_{30}^{4}\cdot C_{26}^{5}\cdot C_{21}^{7}\cdot C_{14}^{7}\cdot C_{7}^{7}\cdot}{3!\cdot2!\cdot3!}$

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

[wrest]

romzes200677
Сорри, я понял только знаменатель.
А... у вас "С" кириллическая или после \cdot нет пробела..
Чтобы нижний/верхний индекс записать из нескольких символов, берем его в фигурные скобки:
$C^{111}_{222} \cdot C^{444}_{555}$

-- 13.04.2019, 23:38 --

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

одна формула :
$\frac{C_{42}^{2}\cdot C_{40}^{2}\cdot C_{38}^{2}\cdot C_{36}^{3}\cdot C_{33}^{3}\cdot C_{30}^{4}\cdot C_{26}^{5}\cdot C_{21}^{7}\cdot C_{14}^{7}\cdot C_{7}^{7}\cdot}{3!\cdot2!\cdot3!}$

Да, верно.
Конечно, лучше записать универсально.
Произведение делается так:
$\prod \limits_{i=downlimit}^{uplimit}prod text$

Ещё, я бы предложил внимательней посмотреть на числитель. $C_n^k=\dfrac{n!}{k!(n-k)!}$, возможно произведение в числителе как-то упростится.

[romzes200677]

Да , я понял спасибо , формулу упрощу и от знаменателя избавлюсь.
Мне вот непонятно для составления формулы на дано только n , m , a , k ? Просто количество типов не могу выразить через формулу для первого цикла 1..5

[wrest]

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

Мне вот непонятно для составления формулы на дано только n , m , a , k ? Просто количество типов не могу выразить через формулу для первого цикла 1..5

Ну пусть будет $i=1..z$
Но в принципе, можно записать произведение по всем $i$-ым проще, вот так: $\prod \limits_i prodtext$
Ещё намекну, что добавление множителей-единиц не меняет произведение

Зачем, на мой взгляд, надо получить "красивую" формулу? Затем, что следующим шагом должна быть запрограммирована функция, которая её вычисляет.

-- 14.04.2019, 00:17 --

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

Мне вот непонятно для составления формулы на дано только n , m , a , k

Ну вообще-то, прямо сейчас мы рассматриваем, что даны только $a_i$ и $k_i$, а $n$ и $m$ вычисляются.

Но в самой (изначальной) задаче наоборот - даны только $n$ шаров и $m$ урн, а остальное надо сгенерировать\вычислить.

-- 14.04.2019, 00:20 --

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

и от знаменателя избавлюсь.

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

[romzes200677]

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