alt text

Как доказать такое тождество исключительно комбинаторно?

Если что, суммирование идет по трем биномиальным коэффициентам.

U P D:

вариант доказательства, который я не понимаю: $% N = \lbrace 1,2,...,n \rbrace$% $% A,B \in N, \lvert A\rvert = k, \lvert B\rvert = l $%.

Пусть $%f(A,B)$% - количество элементов множества B, попавших в первые k наименьших элементов $%A \bigcup B$%, тогда выражение $% {n+s \choose k+l} {k \choose s}{l \choose s} \left({n \choose k}{n\choose l}\right)^{-1}$% будет вероятностью того, что $% f(A,B) = s $% при случайном выборе А и В

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

задан 5 Сен '19 4:28

изменен 5 Сен '19 17:20

1

@sapere aude: тут плохо различимы буквы. Нельзя ли набрать покрупнее? И заодно проверить все индексы.

Видимо, суммируются произведения трёх биномиальных коэффициентов, но суммирование идёт не по ним, а по какому-то индексу. Вроде как по i, но внутри его нигде нет!

(5 Сен '19 5:05) falcao

@falcao Заменил текст на картинку, с индексом я и впрямь оплошал, поэтому привожу оригинал

(5 Сен '19 5:13) sapere aude

@falcao Добавил решение (придуманное не мной), может Вы его поймете?

(5 Сен '19 18:22) sapere aude
10|600 символов нужно символов осталось
1

Комбинаторные и вероятностные решения в принципе взаимозаменяемы. Можно излагать и в тех терминах, и в других.

Правая часть равенства $%C_n^kC_n^{\ell}$% имеет очень ясный комбинаторный смысл: это число упорядоченных пар вида $%(A,B)$%, где $%|A|=k$%, $%|B|=\ell$% для подмножеств одного и того же $%n$%-элементного множества -- скажем, $%\{1,2,...,n\}$%. В левой части то же самое подсчитывается другим способом -- надо понять, по какому принципу. Для этого необходимо и достаточно разгадать, что принято за $%s$%, то есть каков комбинаторный смысл этой величины. Видя одну лишь формулу, догадаться не так просто. Первая гипотеза -- что это мощность пересечения $%A\cap B$%. По такому принципу можно осуществить подсчёт, получая какое-то из комбинаторных тождеств. Но уже при $%s=0$% получается явно другой ответ.

Итак, случай $%s=0$% на самом деле соответствует числу $%C_n^{k+\ell}$%: именно таково начальное слагаемое суммы для $%s=0$%. Понятно тогда, что мы выбираем $%k+\ell$% номеров, и первые $%k$% должны быть из $%A$%, остальные из $%B$%. Здесь множества не просто не пересекаются, а все элементы $%A$% меньше всех элементов из $%B$%. И именно это значит, что "мистическое" пока значение параметра $%s$% равно нулю.

Продолжим разгадывать: пусть $%s=1$%. Здесь слагаемое равно $%C_{n+1}^{k+\ell}k\ell$%. Первое, на что надо решиться -- это взять $%n+1$% число (при том, что их у нас только $%n$%), и выбрать из них $%k+\ell$%, осознавая, что это будет какой-то "код" будущей пары $%(A,B)$%, закономерность построения которой надо разгадать. При этом мы из первых $%k$% элементов списка выделяем один (это $%k$% способов), и из последних $%\ell$% также выделяем один.

На что нам указывают выделенные элементы? Конечно, на то, что их надо обменять. То есть в $%A$% попадают первые $%k$% элементов за исключением выделенного среди них, вместо которого идёт выделенный элемент из последних $%\ell$%. Аналогично для множества $%B$%. Здесь всё хорошо помимо того, что у нас есть "лишние" номера в виде $%n+1$%. Но легко догадаться, что ту "порцию" второго множества, которая идёт после отданного в $%A$% элемента, нужно сдвинуть на единицу влево. Тогда всё "упакуется" в $%n$% значений. При этом у $%A$% и $%B$% могут возникнуть общие элементы (а могут и не возникнуть), но это ничему не противоречит.

При $%s\ge2$% схема аналогичная: мы выделяем $%k+\ell$% элементов из числа $%n+s$%. Это $%C_{n+s}^{k+\ell}$% способов. Первые $%k$% временно отдаём $%A$%, последние $%\ell$% отдаём $%B$%. Далее выделяем $%s$% элементов среди $%k$% и столько же среди $%\ell$%. Это соответствует умножению на $%C_k^sC_{\ell}^s$%. Далее совершаем обмен, отдавая выделенные элементы в другое множество. Наконец, делаем сдвиги. Тот номер из $%B$%, левее которого стоят, скажем, $%i\ge0$% выделенных элементов второго множества, сдвигаем на $%i$% влево, то есть вычитаем из него $%i$%, и такое множество окончательно заявляем в качестве $%B$%.

Это основная идея, но тут ещё есть что проверять и обосновывать. В частности, нужно доказывать, что процесс работает и в обратную сторону. Это технически не так легко: как минимум, нужно продумать все обозначения, чтобы не было очень длинно. Поэтому я пока остановлюсь на том, что написано.

ссылка

отвечен 6 Сен '19 3:28

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

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

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,462

задан
5 Сен '19 4:28

показан
278 раз

обновлен
6 Сен '19 3:28

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru