Перестановки с повторениями [Комбинаторика]

[Whitaker]

Здравствуйте!

Докажите, что число способов разместит в ряд некоторое количество из $m$ белых и $n$ черных шаров (пустое размещение отбрасывается), равно $P(m+1, n+1)-2$.
Я решил таким образом:
Разобьем все все размещения на $r$ классов, где $1 \leq r \leq m$.
К $r$-му классу отнесем размещения, в котором ровно $r$ белых шаров и $k$ черных шаров, где $0 \leq k \leq n$.
Очевидно, что мощность k-го класса равно $\sum_{k=0}^{n} P(r,k)$. Получаем, что в первом, во втором, .... $m$-ом классе всего: $\sum_{k=0}^{n} P(1,k)+\sum_{k=0}^{n} P(2,k)+...+\sum_{k=0}^{n} P(m,k)$.
Но еще существует класс, где $0$ белых шаров и $k$ черных шаров, где $1 \leq k \leq n$ ($k$ не может быть равен нулю, так как по условию пустое размещение отбрасывается).
Всего получаем, что:
$\sum_{k=1}^{n} P(0,k)+\sum_{k=0}^{n} P(1,k)+\sum_{k=0}^{n} P(2,k)+...+\sum_{k=0}^{n} P(m,k)=\Big(\sum_{k=0}^{n} P(0,k)+\sum_{k=0}^{n} P(1,k)+\sum_{k=0}^{n} P(2,k)+...+\sum_{k=0}^{n} P(m,k) \Big)-1$.
Но как сделать чтоб мое равенство было равно $P(m+1, n+1)-2$?
Буду рад любой помощи.
С уважением, Whitaker.

[gris]

Я по привычке подставил один белый и один чётный шар. Вроде бы должно получиться два способа: БЧ и ЧБ. А по формуле не получается
Я что-то не так понял?

[Whitaker]

gris в сообщении #480066 писал(а):

Я по привычке подставил один белый и один чётный шар. Вроде бы должно получиться два способа: БЧ и ЧБ. А по формуле не получается
Я что-то не так понял?

Получается же gris.
$m=n=1$, тогда по формуле $P(m+1,n+1)-2=P(2,2)-2=\dfrac{4!}{2!2!}-2=6-2=4$ способа.
1) ЧБ; 2) БЧ; 3) Ч; 4) Б;

[purser]

Дык, P(1,1)=2

[Whitaker]

Я Вас не понял purser! Ну да $P(1,1)=2$ и что?

[gris]

Понял. Пропустил слово "из". Могут быть короткие ряды.
И вроде бы общепринятая формула $P(n,k)=\dfrac{n!}{(n-k)!}$?
Я с этим ещё запутался.

[Whitaker]

gris в сообщении #480086 писал(а):

Понял. Пропустил слово "из". Могут быть короткие ряды.
И вроде бы общепринятая формула $P(n,k)=\dfrac{n!}{(n-k)!}$?
Я с этим ещё запутался.

Не совсем так gris.
$P(n,k)=\dfrac{(n+k)!}{k! \cdot n!}=C_{n+k}^{k}=C_{n+k}^{n}$

[gris]

Пардон. По невнимательности не заметил, что в заголовке стоит.
Просто как-то привык обозначать это

$$ {n \choose k_1, k_2, \ldots, k_m} = \frac{n!}{k_1!\, k_2! \cdots k_m!}$$

[Whitaker]

gris в сообщении #480094 писал(а):

Пардон. По невнимательности не заметил, что в заголовке стоит.
Просто как-то привык обозначать это

$$ {n \choose k_1, k_2, \ldots, k_m} = \frac{n!}{k_1!\, k_2! \cdots k_m!}$$

Здесь еще наверное такое условие, что: $n=\sum_{i=1}^{m} k_i$

[gris]

Ну да. А по индукции никак нельзя?
Если $m=0$, то должно получиться ровно $n$ рядов. Проверка:
$C^{n+1}_{n+2}-2=n+2-2=n$. Правильно. Теперь пусть верно для $m$ и посмотрим, что будет, если добавить один белый шар.

[PAV]

Это можно решить чисто комбинаторно. Возьмем произвольную последовательность, в которой использовано $m-v$ белых шаров и $n-w$ черных. Добавим в конец ее еще один (дополнительный) черный шар, а за ним - недоиспользованные $v$ белых, а в начало поставим один лишний белый, а перед ним - недоиспользованные $w$ черных. Получим некоторую перестановку, в которой $m+1$ белых шаров и $n+1$ черных. Наоборот, взяв произвольную такую перестановку, удалим из начала первые черные шары и один белый, а из конца - все завершающие белые и один черный. Получим допустимую в задаче перестановку.

Судя по всему, какие-то две длинные перестановки окажутся запрещенными, и их-то и надо вычесть.

[Whitaker]

PAV в сообщении #480116 писал(а):

Это можно решить чисто комбинаторно. Возьмем произвольную последовательность, в которой использовано $m-v$ белых шаров и $n-w$ черных. Добавим в конец ее еще один (дополнительный) черный шар, а за ним - недоиспользованные $v$ белых, а в начало поставим один лишний белый, а перед ним - недоиспользованные $w$ черных. Получим некоторую перестановку, в которой $m+1$ белых шаров и $n+1$ черных. Наоборот, взяв произвольную такую перестановку, удалим из начала первые черные шары и один белый, а из конца - все завершающие белые и один черный. Получим допустимую в задаче перестановку.

Судя по всему, какие-то две длинные перестановки окажутся запрещенными, и их-то и надо вычесть.

PAV скажите пожалуйста а что такое $v$ и $w$? Не совсем понял что это такое

-- Сб сен 03, 2011 23:53:55 --

PAV в сообщении #480116 писал(а):

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

Объясните пожалуйста это. И зачем нужен один добавленный черный и белый шар?

[PAV]

У нас есть две кучки шаров: $m$ белых и $n$ черных. Мы выкладываем какую-то последовательность шаров, причем можем использовать их не все, а только часть. Допустим, мы взяли некоторую последовательность, при этом у нас осталось неиспользованными $v$ белых и $w$ черных. Для того, чтобы было проще подсчитать варианты, мы хотим использовать все имеющиеся шары, но при этом так, чтобы была возможность однозначно восстановить нашу последовательность.

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

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

Можно было бы, кстати, добавлять шары немного иначе, а именно: все в конец.

(детали второго способа)

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