2014 dxdy logo

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

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




На страницу Пред.  1, 2
 
 Re: придумать биекцию для чисел сочетаний
Сообщение02.10.2015, 00:28 
Аватара пользователя
Так кто-нибудь знает правильный ответ? Неделя прошла.

 
 
 
 Re: придумать биекцию для чисел сочетаний
Сообщение02.10.2015, 01:07 
(Я знаю.)

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

(Оффтоп)

arseniiv
Пришлите, пожалуйста

 
 
 
 Re: придумать биекцию для чисел сочетаний
Сообщение02.10.2015, 14:29 
iancaple в сообщении #1058363 писал(а):

(Оффтоп)

arseniiv
Пришлите, пожалуйста

И мне, если можно.

Конкретно над этой задачей я думал достаточно долго, чтобы понять - сам я её точно не решу.

 
 
 
 Re: придумать биекцию для чисел сочетаний
Сообщение02.10.2015, 17:52 
OK. Тем более что я снова задумался об обобщаемости с того случая $(n,k,l) = (4,2,1)$, который рассматривал, из-за несимметричности, которая будет видна ниже.

arseniiv в сообщении #1056463 писал(а):
Всё, в каком-то виде дошло. Тут есть связь с более простым$$\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$.
Итак, берём все подобные размещения и добавляем к ним $O$ всяческими способами до $n+s$. Теперь у нас по $s$ лишних символов в каждой строке (в каждой по-своему в зависимости от её $s$). Сделаем $s$ таких замен (один раз одновременно все вхождения): $BO\mapsto A$, $BA\mapsto C$. В моём случае это работает прекрасно, а в общем, похоже, нет. :?

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

Это найденный двумя способами коэффициент перед $x^{l}y^{k+l}$ в
$$(1+y)^n(1+(1+y)x)^k(1+x)^l = (1+y)^n((1+x)+yx)^k(1+x)^l $$

 
 
 
 Re: придумать биекцию для чисел сочетаний
Сообщение06.10.2015, 08:42 
Аватара пользователя
TOTAL в сообщении #1059209 писал(а):
$ \sum_s  (C_{n+s}^{k+l} \cdot C_{k}^{s} \cdot C_{l}^{s}) =\sum_s  (C_{n}^{k+l-s} \cdot C_{l+k-s}^{k} \cdot C_{k}^{s}) $
А то, что $\sum_s  (C_{n}^{k+l-s} \cdot C_{l+k-s}^{k} \cdot C_{k}^{s})=C_{n}^{k} \cdot C_{n}^{l}$ -уже имеет комбинаторное доказательство. Пусть поставлена цель сделать из $n$ различимых элементов 2 неупорядоченных выборки объемами $k$ и $l$. Один сделает пометки двух типов на генеральной совокупности, число способов как раз $C_{n}^{k} \cdot C_{n}^{l}$. Другой придумает произвольно число $s$ общих элементов, выберет $k+l-s$ из $n$, потом определит, какие $k$ из них войдут в первую выборку (а оставшиеся $l-s$ точно во вторую), потом определит, какие $s$ из этих $k$ войдут также во вторую выборку.

 
 
 
 Re: придумать биекцию для чисел сочетаний
Сообщение07.10.2015, 23:52 
Жаль, что чисто комбинаторно решения найти не смог, но наверное это слишком крутая задача для этого.

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


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