[туплю] комбиноторика

evor

помогите посчитать количество различных наборов из n групп элементов, то есть, если есть группы 1 и 2
то ответ будет:
(1,1)
(2,2)
(1,2) и (2,1) одно и то же
если 3 группы (1,2,3 то соответственно:
(1,1,1) (2,2,2) (3,3,3)
(1,2,3) (1,2,2) (1,3,3) (1,1,2) (1,1,3) (2,2,3) (2,3,3)
то есть (1,1,2)=(1,2,1)=(2,1,1)
вообще это не то же самое, что шарики и перегородки? - то есть есть n шариков, нужно расставить n-1 перегородку, соответственно между 2 соседними перегородками количество шариков будет соответствовать элементам из группы по порядку

gr_nik

вообще это не то же самое, что шарики и перегородки? - то есть есть n шариков, нужно расставить n-1 перегородку, соответственно между 2 соседними перегородками количество шариков будет соответствовать элементам из группы по порядку
Почти, только надо добавить k шариков, чтобы в каждой группе был, как минимум, один. Итого, n+k-1 мест под перегородки, и k-1 одна перегородка.
Итого получается:
[math]$C_{n+k-1}^{k-1}=C_{n+k-1}^n$[/math]
если я ничего не напутал.

evor

а мне не надо, чтобы в каждой группе был один, мне надо чтобы их было n

evor

вообще соль в том, что всего под перегородки n+1 место, но в одном месте может стоять несколько штук, то есть вроде как (n-1n+1) будет тупо

komBAR

Ну да, шарики и перегородки, только надо учесть, что каких-то элементов может быть 0 (две перегородки совпадают чтоб от этого избавиться, надо добавить еще n позиций (типа нулевых шариков). Ну и ответ получится C_{2n-1}^n

evor

но ведь могут и 3 совпасть

komBAR

а мне не надо, чтобы в каждой группе был один, мне надо чтобы их было n
Ничего не понял. Объясню подробнее. У тебя всего n типов элементво и n позиций под них.
Пусть количества элементов a_1, a_2, ..., a_n. При этом a_i могут быть нулями и их сумма равна n. Ты переходишь к b_i = a_i + 1. Их сумма равна 2n, и они натуральные. Задача о выборе b_i - это задача о разделении 2n шариков n-1 перегородкой. Поэтому ответ C_{2n-1}^n

komBAR

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

evor

да, спасибо, понял
сейчас пытаюсь понять, что было неправильно в моих рассуждениях
упд: понял, там не (n-1n+1 а (n+1)^(n-1 что имеет тот же порядок, что и биномиальный кэф, но тут ещё надо вычитать-прибавлять как раз
Оставить комментарий
Имя или ник:
Комментарий: