задача на комбинаторику (ни одной правильной пары из n)

[obar]

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

[ИСН]

Решается многократными включениями-исключениями. Выйдет что-то типа 1/e.

[obar]

ИСН в сообщении #443194 писал(а):

Решается многократными включениями-исключениями. Выйдет что-то типа 1/e.

Не понял, что значит 1/e если это функция от $n$? Можно ли найти общую формулу для любого $n$?

[ИСН]

Можно, конечно, но я Вам её пока не скажу. 1/e - это предел при $n\to\infty$.

[obar]

Ваша фраза "Решается многократными включениями-исключениями" мне ни о чем не говорит. Можно ли по подробней?

[ИСН]

Короче, всего раскладов $n!$. Вычтем те, в которых имеется хотя бы одно правильное соответствие. (Их будет столько-то.) Но при этом те расклады, у которых по два правильных соответствия, оказались вычтены дважды, а это лишнее. Значит, добавим их обратно. Но при этом что-то там оказалось недопереучтено с теми, у которых три...
и так до упора.

[obar]

ИСН в сообщении #443239 писал(а):

Вычтем те, в которых имеется хотя бы одно правильное соответствие

Именно так я и пробывал решать. Но для того, чтобы найти количество способов с одним соответствием нужно снова таки знать число способов $N_{n-1}$ без соответствия для $n-1$. Все что у меня получилось - это рекуррентное соотношение

$$ \sum_{k=0}^{n}C_n^kN_{n-k}=n!\,,\quad N_0=1. $$

[ИСН]

Не нужно. Ключевое слово "хотя бы". Одно соответствие, а остальные плевать что там делают.

[nnosipov]

obar в сообщении #443247 писал(а):

Все что у меня получилось - это рекуррентное соотношение

$$ \sum_{k=0}^{n}C_n^kN_{n-k}=n!\,,\quad N_0=1. $$

А теперь можно угадать ответ и доказать его по индукции.

[obar]

nnosipov в сообщении #443305 писал(а):

А теперь можно угадать ответ и доказать его по индукции.

Что-то не угадывается. Может подскажите?

-- Вс май 08, 2011 06:10:39 --

ИСН в сообщении #443250 писал(а):

Ключевое слово "хотя бы". Одно соответствие, а остальные плевать что там делают.

Если знать число комбинаций с хобя бы одним совпадением ($S_n$), то интересующее меня число раскладов без совпадений ($N_n$) получается простым отниманием: $N_n=n!-S_n$. И не нужно ни каких добавлений-вычетаний. Только я не вижу, как найти $S_n$.

[ИСН]

Сколько у нас раскладов, в которых по первому пункту совпадение, а по остальным неважно что?

[obar]

ИСН в сообщении #443341 писал(а):

Сколько у нас раскладов, в которых по первому пункту совпадение, а по остальным неважно что?

$(n-1)!$

[ИСН]

Именно! А сколько таких, в которых совпадение только по второму пункту, а первый и все остальные делают чёрт знает что?
Вот эти все надо вычесть.

[obar]

ИСН в сообщении #443462 писал(а):

Именно! А сколько таких, в которых совпадение только по второму пункту, а первый и все остальные делают чёрт знает что?

Разумеется, столько же.

ИСН в сообщении #443462 писал(а):

Вот эти все надо вычесть

Что-то я не догоняю... Пойду еще сам подумаю. Спасибо.

[ИСН]

Разумеется. И т.д. Итого: всех, у кого хоть одно соответствие - столько-то. Теперь перечитайте моё третье сообщение в теме.