Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 20 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Есть n людей, каждый со своей шляпой... Задача Эйлера
СообщениеДобавлено: 15 сен 2017, 12:31 
Не в сети
Начинающий
Зарегистрирован:
08 мар 2016, 16:13
Сообщений: 21
Cпасибо сказано: 0
Спасибо получено:
1 раз в 1 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Есть n людей, каждый со своей шляпой, они случайным образом перемешали шляпы между собой. Сколько есть комбинаций при которых каждый человек не получит свою шляпу? Комбинаторика

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю dexforint "Спасибо" сказали:
Xenia1996
 Заголовок сообщения: Re: Есть n людей, каждый со своей шляпой... Задача Эйлера
СообщениеДобавлено: 15 сен 2017, 13:03 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Формула включений-исключений.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Есть n людей, каждый со своей шляпой... Задача Эйлера
СообщениеДобавлено: 15 сен 2017, 13:57 
Не в сети
Light & Truth
Зарегистрирован:
28 мар 2014, 23:59
Сообщений: 6312
Cпасибо сказано: 633
Спасибо получено:
509 раз в 477 сообщениях
Очков репутации: 47

Добавить очки репутацииУменьшить очки репутации
[math]\left[ \frac{n!}{e} \right][/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю ivashenko "Спасибо" сказали:
bimol, Xenia1996
 Заголовок сообщения: Re: Есть n людей, каждый со своей шляпой... Задача Эйлера
СообщениеДобавлено: 15 сен 2017, 14:37 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Строго говоря, это неверный результат. Возьмите, например, [math]n=4[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю swan "Спасибо" сказали:
Xenia1996
 Заголовок сообщения: Re: Есть n людей, каждый со своей шляпой... Задача Эйлера
СообщениеДобавлено: 15 сен 2017, 14:50 
Не в сети
Light & Truth
Зарегистрирован:
28 мар 2014, 23:59
Сообщений: 6312
Cпасибо сказано: 633
Спасибо получено:
509 раз в 477 сообщениях
Очков репутации: 47

Добавить очки репутацииУменьшить очки репутации
swan писал(а):
Строго говоря, это неверный результат. Возьмите, например, n=4


[math]\left[ \frac{4!}{e} \right]=9[/math]


1234
2341
2413
2143

3142
3412
3421

4123
4312
4321

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Есть n людей, каждый со своей шляпой... Задача Эйлера
СообщениеДобавлено: 15 сен 2017, 15:37 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Вообще-то квадратными скобками обозначают целую часть числа и
[math]\left[ \frac {4!} e \right] =8[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю swan "Спасибо" сказали:
Xenia1996
 Заголовок сообщения: Re: Есть n людей, каждый со своей шляпой... Задача Эйлера
СообщениеДобавлено: 15 сен 2017, 15:52 
Не в сети
Light & Truth
Зарегистрирован:
28 мар 2014, 23:59
Сообщений: 6312
Cпасибо сказано: 633
Спасибо получено:
509 раз в 477 сообщениях
Очков репутации: 47

Добавить очки репутацииУменьшить очки репутации
swan писал(а):
Вообще-то квадратными скобками обозначают целую часть числа и
[math]\left[ \frac {4!} e \right] =8[/math]



А что такое тогда \floor? Я склонен придерживаться таких обозначений, как более понятных интуитивно и более логичных.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Есть n людей, каждый со своей шляпой... Задача Эйлера
СообщениеДобавлено: 16 сен 2017, 11:51 
Не в сети
Одарённый
Зарегистрирован:
12 ноя 2016, 15:04
Сообщений: 100
Cпасибо сказано: 25
Спасибо получено:
27 раз в 26 сообщениях
Очков репутации: 16

Добавить очки репутацииУменьшить очки репутации
Мне не известно, откуда ivashenko взял эту формулу... Совершенно ясно, что приближенно она точно верна. Но откуда точное равенство?! Классическое решение такое.
Обозначим через [math]H=\left\{ 1, 2,..., n \right\}[/math] множество шляп, через [math]P=\left\{ A_{1}, A_{2},..., A_{n} \right\}[/math] - множество людей, причем нижний индекс у [math]A[/math] указывает шляпу, которая соответствует данному [math]A[/math]. Пусть [math]B_{i}[/math] - множество биекций из [math]P[/math] в [math]H[/math], при которых шляпа [math]i[/math] оказывается на человеке [math]A_{i}[/math]. Тогда[math]\bigcup\limits_{i=1}^{n}B_{i}[/math] есть множество биекций, при которых хотя бы один человек одевает свою шляпу. Заметим, что множество всех биекций [math]P \mapsto H[/math] есть объединение двух непустых непересекающихся множеств: искомого множества (вернее, его искомой мощности) биекций, при котором ни один человек не одевает свою шляпу, и множества [math]\bigcup\limits_{i=1}^{n}B_{i}[/math] биекций, при котором хотя бы один человек одевает свою шляпу. Найдем сначала мощность последнего (из двух указанных) множеств. По формуле включений-исключений получаем [math]\left|\bigcup\limits_{i=1}^{n}B_{i} \right|=\sum\limits_{i=1}^{n}\left( - 1\right)^{i-1}\sum\limits_{1 \leqslant k_{1} < k_{2} < ... < k_{i} \leqslant n }\left| \bigcap\limits_{l=1}^{i}B_{k_{l} } \right|[/math]. В выписанной сумме [math]n[/math] слагаемых, каждое из которых в свою очередь состоит из [math]C_{n}^{i}[/math] слагаемых (числа [math]k_{1}, k_{2}, ..., k_{i}[/math] из множества [math]H[/math] могут быть выбраны [math]C_{n}^{i}[/math] способами), причем каждое из этих последних (с точностью до знака [math]\left( -1 \right)^{i-1}[/math]) равно [math]\left( n-i \right)![/math] (люди [math]A_{k_{1}}, A_{k_{2}}, ..., A_{k_{i}}[/math] все одевают свои шляпы, а остальные шляпы распределяются произвольно между оставшимися [math]\left( n-i \right)[/math] людьми). Резюмируя, получаем, что количество биекций, при которых хотя бы один человек надевает свою шляпу, равно [math]n!\left( 1-\frac{ 1 }{ 2! }+\frac{ 1 }{ 3! }-...+\left( -1 \right)^{n-1}\frac{ 1 }{ n! } \right)[/math]. Искомое же количество биекций, при которых ни один не надевает своей шляпы, равно разности [math]n![/math] и выписанного выражения, т. е. равно [math]n!\left(\frac{ 1 }{ 2! }-\frac{ 1 }{ 3! }+...+\left( -1 \right)^{n}\frac{ 1 }{ n! }\right)[/math].
Понятно, что по мере роста [math]n[/math] ответ все ближе к [math]\frac{n! }{ e }[/math]. Но откуда, повторюсь, взялось точное равенство [math]\left[ \frac{ n! }{ e } \right][/math]? ivashenko, поделитесь, пожалуйста, с нами своими знаниями. :)

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Kirill1986 "Спасибо" сказали:
sergebsl
 Заголовок сообщения: Re: Есть n людей, каждый со своей шляпой... Задача Эйлера
СообщениеДобавлено: 16 сен 2017, 11:58 
Не в сети
Оракул
Зарегистрирован:
13 дек 2015, 17:51
Сообщений: 952
Cпасибо сказано: 154
Спасибо получено:
150 раз в 135 сообщениях
Очков репутации: 11

Добавить очки репутацииУменьшить очки репутации
Разница между точным значением и приближенным меньше 1.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю bimol "Спасибо" сказали:
Kirill1986
 Заголовок сообщения: Re: Есть n людей, каждый со своей шляпой... Задача Эйлера
СообщениеДобавлено: 16 сен 2017, 12:05 
Не в сети
Light & Truth
Зарегистрирован:
28 мар 2014, 23:59
Сообщений: 6312
Cпасибо сказано: 633
Спасибо получено:
509 раз в 477 сообщениях
Очков репутации: 47

Добавить очки репутацииУменьшить очки репутации
Kirill1986 писал(а):
ivashenko, поделитесь, пожалуйста, с нами своими знаниями.


Ничего не знаю, эта формула была дана мне Свыше )))

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

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Есть n людей, каждый со своими m тараканами в голове

в форуме Теория вероятностей

ivashenko

0

267

18 сен 2017, 11:51

В.Ф. Чудесенко Задача 18 Вариант 2 На каждый лотерейный

в форуме Теория вероятностей

dimon17115

0

787

18 июл 2018, 21:22

Задача на рассаживание людей

в форуме Комбинаторика и Теория вероятностей

afraumar

5

2583

07 апр 2015, 13:25

Задача по рассаживанию людей за круглым столом

в форуме Комбинаторика и Теория вероятностей

Chestr1

7

1748

09 ноя 2016, 10:54

Задача с рассадкой людей за круглый стол

в форуме Комбинаторика и Теория вероятностей

Mark1035

7

452

20 мар 2022, 14:14

Удаление своей темы

в форуме Предложения, Замечания, Обратная связь

Elizabett2017

8

852

16 май 2017, 13:00

Задача Эйлера

в форуме Объявления участников Форума

wrobel

0

665

16 сен 2015, 16:32

Задача с кругами эйлера

в форуме Начала анализа и Другие разделы школьной математики

vavucho

2

426

08 сен 2022, 22:46

Задача на уравнение Эйлера

в форуме Исследование операций и Задачи оптимизации

Gargantua

0

385

10 дек 2016, 01:41

Выберите все аналитические в своей области определения функц

в форуме Комплексный анализ и Операционное исчисление

Vladiikkkkk

2

199

15 янв 2022, 16:43


Часовой пояс: UTC + 3 часа [ Летнее время ]



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

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


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

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved