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

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

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

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

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




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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Есть n людей, каждый со своей шляпой... Задача Эйлера
СообщениеДобавлено: 15 сен 2017, 14:03 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 10:11
Сообщений: 3194
Cпасибо сказано: 55
Спасибо получено:
698 раз в 631 сообщениях
Очков репутации: 201

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Есть n людей, каждый со своей шляпой... Задача Эйлера
СообщениеДобавлено: 15 сен 2017, 14:57 
Не в сети
Light & Truth
Зарегистрирован:
29 мар 2014, 00:59
Сообщений: 3272
Cпасибо сказано: 229
Спасибо получено:
207 раз в 196 сообщениях
Очков репутации: 21

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю ivashenko "Спасибо" сказали:
bimol
 Заголовок сообщения: Re: Есть n людей, каждый со своей шляпой... Задача Эйлера
СообщениеДобавлено: 15 сен 2017, 15:37 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 10:11
Сообщений: 3194
Cпасибо сказано: 55
Спасибо получено:
698 раз в 631 сообщениях
Очков репутации: 201

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Есть n людей, каждый со своей шляпой... Задача Эйлера
СообщениеДобавлено: 15 сен 2017, 15:50 
Не в сети
Light & Truth
Зарегистрирован:
29 мар 2014, 00:59
Сообщений: 3272
Cпасибо сказано: 229
Спасибо получено:
207 раз в 196 сообщениях
Очков репутации: 21

Добавить очки репутацииУменьшить очки репутации
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, 16:37 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 10:11
Сообщений: 3194
Cпасибо сказано: 55
Спасибо получено:
698 раз в 631 сообщениях
Очков репутации: 201

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Есть n людей, каждый со своей шляпой... Задача Эйлера
СообщениеДобавлено: 15 сен 2017, 16:52 
Не в сети
Light & Truth
Зарегистрирован:
29 мар 2014, 00:59
Сообщений: 3272
Cпасибо сказано: 229
Спасибо получено:
207 раз в 196 сообщениях
Очков репутации: 21

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



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

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

Добавить очки репутацииУменьшить очки репутации
Мне не известно, откуда 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пасибо сказано 
 Заголовок сообщения: Re: Есть n людей, каждый со своей шляпой... Задача Эйлера
СообщениеДобавлено: 16 сен 2017, 12:58 
Не в сети
Оракул
Зарегистрирован:
13 дек 2015, 18:51
Сообщений: 705
Cпасибо сказано: 79
Спасибо получено:
109 раз в 98 сообщениях
Очков репутации: 3

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю bimol "Спасибо" сказали:
Kirill1986
 Заголовок сообщения: Re: Есть n людей, каждый со своей шляпой... Задача Эйлера
СообщениеДобавлено: 16 сен 2017, 13:05 
Не в сети
Light & Truth
Зарегистрирован:
29 мар 2014, 00:59
Сообщений: 3272
Cпасибо сказано: 229
Спасибо получено:
207 раз в 196 сообщениях
Очков репутации: 21

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


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

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

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

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

ivashenko

0

59

18 сен 2017, 12:51

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

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

afraumar

5

1029

07 апр 2015, 14:25

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

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

Chestr1

7

386

09 ноя 2016, 11:54

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

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

wrobel

0

439

16 сен 2015, 17:32

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

в форуме Maple

Avgust

3

576

04 авг 2013, 09:49

Найти решение уравнения Эйлера или Эйлера-Пуассона для функц

в форуме Функциональный анализ, Топология и Дифференциальная геометрия

NaisVery

12

952

04 дек 2012, 16:41

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

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

Gargantua

0

82

10 дек 2016, 02:41

Задача на применение функции Эйлера

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

mathematician

4

430

07 окт 2012, 20:31

Задача мет. Эйлера и Рунге-Кутта

в форуме Численные методы

FiTo

6

480

05 ноя 2013, 13:50

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

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

Elizabett2017

8

142

16 май 2017, 14:00


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



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

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


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

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

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

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