Показаны сообщения с ярлыком proof. Показать все сообщения
Показаны сообщения с ярлыком proof. Показать все сообщения
суббота, 16 августа 2025 г.
Мой Телеграмм
Время идёт, формат меняется) Сейчас я в Португалии, пишу статьи, работаю с учениками над олимпиадами и экзаменами и продолжаю погружаться в математику. Мой основной канал сейчас в телеграмме:
Там задачи, стримы, полезные материалы для школьников и в целом основная активность. Здесь же будут появляться только большие статьи, которым не уютно в формате постов.
среда, 15 ноября 2017 г.
Выборки неупорядоченные с возвращениями.
Каждый раз, когда начинаю рассказывать комбинаторику я рисую следующую табличку, которая постепенно заполняется:
И каждый раз доходя до неупорядоченных с возвращениями я говорю что-то из серии "попробуйте вывести сами, а если не получится спросите". Надо ли говорить, что спрашивают не часто?) Я оставлю этот пункт на разбор ученикам по ряду причин: во-первых этот тип выборок встречается крайне редко и поэтому мало полезен в олимпиадных задачах, во-вторых доказательство требует некоторого времени и я хочу дать в это время ещё и порешать ( благо комбинаторика в одно занятие обычно не впихивается, хотя и такие экстремальные ситуации встречаются).
Но так или иначе - мне будет удобно оставить здесь доказательство, чтобы каждый желающих смог изучить его в своё время. + я обещала :)
Доказательство. Как и в случае со всеми остальными выборками рассмотрим набор из N различных шаров. Доставая

Любая выборка определяется разбиением данного набора на \( (a_1, \dots, a_k) \) :
Получаем, что выборка зависит от расположения разделителей:
Сколько способов их расставить? Всего шариков N, а разделителей k-1 (чтобы разбить на k областей). Значит N+k-1 мест, из которых в k ставят разделители, причём делаем это неупорядоченно без возвращений ( если мы хотим, чтобы \( a_i \) =0, то ставим разделители рядом последовательно: | |). Таким образом количество неупорядоченных с возвращениями выборок $$C_{N+k-1}^k$$
Без возвращений
|
||
$$N^k$$
|
||
Но так или иначе - мне будет удобно оставить здесь доказательство, чтобы каждый желающих смог изучить его в своё время. + я обещала :)
Теорема. Пусть всего дано N элементов, из них выбирается k неупорядоченно с возвращениями. Тогда таких выборок $$C_{N+k-1}^k$$
Доказательство. Как и в случае со всеми остальными выборками рассмотрим набор из N различных шаров. Доставая
их мы можем получить один и тот же шар несколько раз. Обозначим количество выниманий одного и того же \(i\)-ого шара за \(a_i\). Тогда $$a_1+a_2+\dots + a_k=N$$
Выборки различаются тогда, когда различаются упорядоченные наборы \( (a_1, \dots, a_k) \) и выполняется условие суммы приведённое выше. Поэтому применить формулу \(N^k\) не выйдет. Рассмотрим такую модель:
Любая выборка определяется разбиением данного набора на \( (a_1, \dots, a_k) \) :
Получаем, что выборка зависит от расположения разделителей:
Сколько способов их расставить? Всего шариков N, а разделителей k-1 (чтобы разбить на k областей). Значит N+k-1 мест, из которых в k ставят разделители, причём делаем это неупорядоченно без возвращений ( если мы хотим, чтобы \( a_i \) =0, то ставим разделители рядом последовательно: | |). Таким образом количество неупорядоченных с возвращениями выборок $$C_{N+k-1}^k$$
пятница, 12 декабря 2014 г.
Теорема бабочки
Теорема, которой даётся название и которая не теряется в куче подобных ей - или крайне полезная или очень красивая.
Теорема бабочки - на мой взгляд относится ко второму типу, хотя она несомненна может быть применена в подходящем случае. Звучит она следующим образом:
Теорема бабочки - на мой взгляд относится ко второму типу, хотя она несомненна может быть применена в подходящем случае. Звучит она следующим образом:
Пусть \(P\) - середина хорды \(EF\). Через точку \(P\) проведены две произвольные хорды \(BD\) и \(CA\). Отрезки \(AB\) и \(CD\) пересекают хорду \(EF\) в точках \(X\) и \(Y\) соответственно. Тогда \(P\) - середина отрезка \(XY\).
Подписаться на:
Сообщения (Atom)

