2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 задача на комбинаторику (ни одной правильной пары из n)
Сообщение07.05.2011, 21:16 
Заслуженный участник


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

 Профиль  
                  
 
 Re: задача на комбинаторику
Сообщение07.05.2011, 21:18 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: задача на комбинаторику
Сообщение07.05.2011, 22:18 
Заслуженный участник


13/04/11
564
ИСН в сообщении #443194 писал(а):
Решается многократными включениями-исключениями. Выйдет что-то типа 1/e.

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

 Профиль  
                  
 
 Re: задача на комбинаторику
Сообщение07.05.2011, 22:19 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: задача на комбинаторику
Сообщение07.05.2011, 22:23 
Заслуженный участник


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

 Профиль  
                  
 
 Re: задача на комбинаторику
Сообщение07.05.2011, 22:30 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: задача на комбинаторику
Сообщение07.05.2011, 22:52 
Заслуженный участник


13/04/11
564
ИСН в сообщении #443239 писал(а):
Вычтем те, в которых имеется хотя бы одно правильное соответствие

Именно так я и пробывал решать. Но для того, чтобы найти количество способов с одним соответствием нужно снова таки знать число способов $N_{n-1}$ без соответствия для $n-1$. Все что у меня получилось - это рекуррентное соотношение
$$
\sum_{k=0}^{n}C_n^kN_{n-k}=n!\,,\quad N_0=1.
$$

 Профиль  
                  
 
 Re: задача на комбинаторику
Сообщение07.05.2011, 22:57 
Заслуженный участник
Аватара пользователя


18/05/06
13435
с Территории
Не нужно. Ключевое слово "хотя бы". Одно соответствие, а остальные плевать что там делают.

 Профиль  
                  
 
 Re: задача на комбинаторику
Сообщение08.05.2011, 05:30 
Заслуженный участник


20/12/10
8858
obar в сообщении #443247 писал(а):
Все что у меня получилось - это рекуррентное соотношение
$$
\sum_{k=0}^{n}C_n^kN_{n-k}=n!\,,\quad N_0=1.
$$

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

 Профиль  
                  
 
 Re: задача на комбинаторику
Сообщение08.05.2011, 05:48 
Заслуженный участник


13/04/11
564
nnosipov в сообщении #443305 писал(а):
А теперь можно угадать ответ и доказать его по индукции.

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

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

ИСН в сообщении #443250 писал(а):
Ключевое слово "хотя бы". Одно соответствие, а остальные плевать что там делают.

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

 Профиль  
                  
 
 Re: задача на комбинаторику
Сообщение08.05.2011, 09:24 
Заслуженный участник
Аватара пользователя


18/05/06
13435
с Территории
Сколько у нас раскладов, в которых по первому пункту совпадение, а по остальным неважно что?

 Профиль  
                  
 
 Re: задача на комбинаторику
Сообщение08.05.2011, 12:57 
Заслуженный участник


13/04/11
564
ИСН в сообщении #443341 писал(а):
Сколько у нас раскладов, в которых по первому пункту совпадение, а по остальным неважно что?

$(n-1)!$

 Профиль  
                  
 
 Re: задача на комбинаторику
Сообщение08.05.2011, 13:06 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: задача на комбинаторику
Сообщение08.05.2011, 13:12 
Заслуженный участник


13/04/11
564
ИСН в сообщении #443462 писал(а):
Именно! А сколько таких, в которых совпадение только по второму пункту, а первый и все остальные делают чёрт знает что?

Разумеется, столько же.
ИСН в сообщении #443462 писал(а):
Вот эти все надо вычесть

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

 Профиль  
                  
 
 Re: задача на комбинаторику
Сообщение08.05.2011, 13:27 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 17 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group