Показаны сообщения с ярлыком proof. Показать все сообщения
Показаны сообщения с ярлыком proof. Показать все сообщения

суббота, 16 августа 2025 г.

Мой Телеграмм


 Время идёт, формат меняется) Сейчас я в Португалии, пишу статьи, работаю с учениками над олимпиадами и экзаменами и продолжаю погружаться в математику. Мой основной канал сейчас в телеграмме:


Там задачи, стримы, полезные материалы для школьников и в целом основная активность. Здесь же будут появляться только большие статьи, которым не уютно в формате постов. 

среда, 15 ноября 2017 г.

Выборки неупорядоченные с возвращениями.

Каждый раз, когда начинаю рассказывать комбинаторику я рисую следующую табличку, которая постепенно заполняется:


 С возвращениями 
Без возвращений 
 Упорядоченные

$$N^k$$
 $$\frac{N!}{(N-k)!}$$
 Неупорядоченные

 $$C_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\).