2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 придумать биекцию для чисел сочетаний
Сообщение25.09.2015, 01:53 
$ \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 виртуальных шаров, но дальше как-то не сходится, хотя идея выглядит достаточно естественной.

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

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

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

 
 
 
 Re: придумать биекцию для чисел сочетаний
Сообщение25.09.2015, 06:43 
Аватара пользователя
leolev в сообщении #1056431 писал(а):
$ \sum_s  (C_{n+s}^{k+l} \cdot C_{k}^{s} \cdot C_{l}^{s}) = C_{n}^{k} \cdot C_{n}^{l}$
Укажите пределы суммирования

 
 
 
 Re: придумать биекцию для чисел сочетаний
Сообщение25.09.2015, 06:49 
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)$.

 
 
 
 Re: придумать биекцию для чисел сочетаний
Сообщение25.09.2015, 06:53 
Аватара пользователя
arseniiv в сообщении #1056463 писал(а):
Если вполне естественно считать $C_n^m = 0$ при $m < 0$ или $m > n$, сумма срабатывает хоть даже по всем целым. Ненулевые слагаемые в ней при $0\leqslant s\leqslant\min(k, l)$.
То, что естественно считать, можно естественно прямо написать. Почему не написать?

 
 
 
 Re: придумать биекцию для чисел сочетаний
Сообщение25.09.2015, 07:02 

(Оффтоп)

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

 
 
 
 Re: придумать биекцию для чисел сочетаний
Сообщение25.09.2015, 14:06 
TOTAL
Простите, пока нет привычки все обговаривать до мелочей, но здесь имелось ввиду, что суммирование до минимума из l и n


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

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

 
 
 
 Re: придумать биекцию для чисел сочетаний
Сообщение26.09.2015, 00:03 
arseniiv

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

 
 
 
 Re: придумать биекцию для чисел сочетаний
Сообщение26.09.2015, 08:07 
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)$, и там особого разнообразия нет. Но деваться-то некуда! :-) )

 
 
 
 Re: придумать биекцию для чисел сочетаний
Сообщение26.09.2015, 10:27 
Аватара пользователя

(Оффтоп)

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

 
 
 
 Re: придумать биекцию для чисел сочетаний
Сообщение27.09.2015, 16:52 
arseniiv
Спасибо за подробное обьяснение, разобрался с доказательством Вашего тождества и теперь надо похожие идеи применить для исходного.

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

 
 
 
 Re: придумать биекцию для чисел сочетаний
Сообщение01.10.2015, 21:45 
arseniiv в сообщении #1056453 писал(а):
$s$ — это явно не число дважды покрашенных шаров

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

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

 
 
 
 Re: придумать биекцию для чисел сочетаний
Сообщение01.10.2015, 23:53 
arseniiv в сообщении #1058249 писал(а):
Но вы же попробовали выписывать все комбинации для какой-нибудь маленькой размерности?

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

 
 
 
 Re: придумать биекцию для чисел сочетаний
Сообщение02.10.2015, 00:01 
Не, равенство действительно верное, раз уж найдено построение. :-)

leolev в сообщении #1058283 писал(а):
Первое смотрел, но каких-то паттернов не увидел
Жалко. Ну, надеюсь, кто-нибудь лучше меня подскажет.

 
 
 [ Сообщений: 23 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group