придумать биекцию для чисел сочетаний

[leolev]

$ \sum_s (C_{n+s}^{k+l} \cdot C_{k}^{s} \cdot C_{l}^{s}) = C_{n}^{k} \cdot C_{n}^{l}$

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

[arseniiv]

$s$ — это явно не число дважды покрашенных шаров. При $(n,k,l) = (4,2,1)$ число раскрасок с одним зелёным и с нулём зелёных совпадают, тогда как слагаемые в левой части равны соответственно 20 и 4.

-- Пт сен 25, 2015 07:10:35 --

P. S. Меня тоже что-то заклинило (но я и не комбинатор).

[TOTAL]

leolev в сообщении #1056431 писал(а):

$ \sum_s (C_{n+s}^{k+l} \cdot C_{k}^{s} \cdot C_{l}^{s}) = C_{n}^{k} \cdot C_{n}^{l}$

Укажите пределы суммирования

[arseniiv]

leolev
Всё, в каком-то виде дошло. Тут есть связь с более простым

$$\sum_s C_k^s C_l^s = C_{k+l}^k,$$

которое соответствует разбиению всех размещений $k$ штук $A$ и $l$ штук $B$ на классы, получающиеся из размещения $A\ldots AB\ldots B$ данным числом $s\in 0..\min(k, l)$ транспозиций $s$ позиций, выбранных из тех, где стоят $A$ и такого же числа позиций из тех, где стоят $B$.

Попробуйте воспользоваться этой подсказкой!

TOTAL
Если вполне естественно считать $C_n^m = 0$ при $m < 0$ или $m > n$, сумма срабатывает хоть даже по всем целым. Ненулевые слагаемые в ней при $0\leqslant s\leqslant\min(k, l)$.

[TOTAL]

arseniiv в сообщении #1056463 писал(а):

Если вполне естественно считать $C_n^m = 0$ при $m < 0$ или $m > n$, сумма срабатывает хоть даже по всем целым. Ненулевые слагаемые в ней при $0\leqslant s\leqslant\min(k, l)$.

То, что естественно считать, можно естественно прямо написать. Почему не написать?

[arseniiv]

(Оффтоп)

Не могу судить, насколько полезно неуказанные пределы понимать как всё $\mathbb Z$ по умолчанию, когда дело касается комбинаторных чисел. (В моём небольшом опыте пределы можно было всегда «раздвинуть», доопределив то, по чему сумма.)

[leolev]

TOTAL
Простите, пока нет привычки все обговаривать до мелочей, но здесь имелось ввиду, что суммирование до минимума из l и n


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

Прошу комбинаторщиков всея dxdy помочь найти красивое решение)

[leolev]

arseniiv

под транспозициями Вы подразумеваете какой-то особый вид подстановок (именно это пока не изучал)? Сама подсказка просто тоже неочевидна

[arseniiv]

leolev в сообщении #1056526 писал(а):

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

Какими заменами? Не, я не предлагал свою маленькую сумму как-то приделывать к вашей.

leolev в сообщении #1056725 писал(а):

под транспозициями Вы подразумеваете какой-то особый вид подстановок (именно это пока не изучал)? Сама подсказка просто тоже неочевидна

Транспозиции — перестановки, меняющие ровно два элемента (самые «маленькие» из меняющих хоть что-то). Пример соответствующих посту выше количеств $s$ транспозиций из $AAABB$ в

$$\begin{array}{cc} AAABB & 0 \\ AABAB & 1 \\ AABBA & 1 \\ ABAAB & 1 \\ ABABA & 1 \\ ABBAA & 2 \\ BAAAB & 1 \\ BAABA & 1 \\ BABAA & 2 \\ BBAAA & 2 \\ \end{array}$$

По другому, $s$ — это сколько $A$ (или $B$) не осталось на месте.

Подскажу ещё: получается, если я прав (а это так — но это известно сейчас, а не тогда, когда пытался решить), те раскраски шаров можно получить все по одной, добавляя к размещениям $k$ синих и $l$ жёлтых шаров ещё каких-то штук (пусть будут снежки, чтобы не путать ни с чем) всеми возможными способами до общего количества шаров $n+s$, где $s$ — см. выше, и делая какую-то операцию. Операция на поверку оказывается очень простой.

-- Сб сен 26, 2015 10:11:41 --

(Или не совсем простой — я проверял на $(n,k,l) = (4,2,1)$, и там особого разнообразия нет. Но деваться-то некуда! )

[iancaple]

(Оффтоп)

Какие все-таки тут люди географически разные. У одного шары обязательно синие и желтые, у другого снежки, а я уж забыл, как они выглядят. Есть такая модель, почему-то приводящая к верной правой части , но несовпадающей левой.
В сети появился новый сайт, на котором $n$ роликов для скачивания. Из них Асе понравилось $k$ роликов, а Васе $l$ роликов. Ася скачала себе в папку, а когда пошел качать в свою папку Вася, про $s$ роликов выскакивало окно"Вы правда хотите заменить?".(такой баг видел в одной прежней версии оперы). Вася не знал, где искать папку ТМР (это в ней промежуточно скапливалось все, что качалось) ,а заменять побоялся, пришлось ему просить у старшей сестры скопировать $s$ "общих" роликов у нее. Мораль: каждому ребенку - отдельный комп.

[leolev]

arseniiv
Спасибо за подробное обьяснение, разобрался с доказательством Вашего тождества и теперь надо похожие идеи применить для исходного.

iancaple
Вообще в науке принято все это через алфавит оформлять, конкретно здесь можно рассмотреть два алфавита с s общими символами, хотя не уверен что это лучшая интерпретация

[leolev]

arseniiv в сообщении #1056453 писал(а):

$s$ — это явно не число дважды покрашенных шаров

Может быть это число блоков (подряд идущих последовательных синих/желтых шаров) в упорядоченном представлении 'цветных' шаров?

[arseniiv]

Если вы имеете в виду блоки из одинаковых шаров, а не пары шаров разного цвета, не-а. Что-нибудь бы ещё подсказал, но ничего в голову не приходит. (Но вы же попробовали выписывать все комбинации для какой-нибудь маленькой размерности?)

[leolev]

arseniiv в сообщении #1058249 писал(а):

Но вы же попробовали выписывать все комбинации для какой-нибудь маленькой размерности?

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

[arseniiv]

Не, равенство действительно верное, раз уж найдено построение.

leolev в сообщении #1058283 писал(а):

Первое смотрел, но каких-то паттернов не увидел

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