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

[iancaple]

Так кто-нибудь знает правильный ответ? Неделя прошла.

[arseniiv]

(Я знаю.)

[iancaple]

(Оффтоп)

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

[leolev]

iancaple в сообщении #1058363 писал(а):

(Оффтоп)

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

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

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

[arseniiv]

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$. В моём случае это работает прекрасно, а в общем, похоже, нет.

[TOTAL]

$ \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 $$

[iancaple]

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$ войдут также во вторую выборку.

[leolev]

Жаль, что чисто комбинаторно решения найти не смог, но наверное это слишком крутая задача для этого.