Формулы комбинаторики и Python

Слайд 1. Формулы комбинаторики и Python

От математических основ до олимпиадного программирования в 10 классе

Слайд 2. Часть 1: Основные правила и понятия

Слайд 3. Правило умножения

Если объект $A$ можно выбрать $n$ способами, а объект $B$ можно выбрать $m$ способами, то пару $(A,B)$ можно выбрать $n\cdot m$ способами.

Это фундамент всей комбинаторики. В Python это реализуется через вложенные циклы или прямое перемножение значений.

Слайд 4. Визуализация: Дерево выбора

Дерево выбора наглядно показывает, как умножение вариантов порождает общее количество исходов. Каждое ветвление — это новый этап выбора.

Слайд 5. Перестановки ($P_n$)

Перестановки — это способы расположить $n$ различных объектов в определенном порядке.

Формула: $P_n=n!$

Где $n!=1\cdot 2\cdot 3\cdot \cdots \cdot n$

Важен только порядок всех имеющихся элементов.

Слайд 6. Перестановки в Python

Для вычисления факториала используем модуль `math`.

```python

import math

n = 5

print(math.factorial(n)) # Выведет 120

```

Если нужно сгенерировать сами перестановки:

```python

from itertools import permutations

data = [1, 2, 3]

print(list(permutations(data)))

```

Слайд 7. Размещения ($A_n^k$)

Размещения — это выбор $k$ элементов из $n$ и их расстановка по местам.

Формула: $A_n^k=\frac{n!}{(n-k)!}$

Здесь важен и состав выбранных элементов, и их порядок.

Пример: выбор золотого, серебряного и бронзового медалистов из 10 участников.

Слайд 8. Размещения в Python

В Python для расчёта количества размещений можно использовать `math.perm(n, k)` (доступно с версии 3.8).

```python

import math

n, k = 10, 3

ans = math.perm(n, k)

print(ans) # 720

```

Функция `itertools.permutations(data, k)` позволяет получить все кортежи длиной $k$.

Слайд 9. Сочетания ($C_n^k$)

Сочетания — это выбор $k$ элементов из $n$ без учета их порядка.

Формула: $C_n^k=\frac{n!}{k!(n-k)!}$

Нам важен только состав группы.

Пример: выбор 3 дежурных из класса в 25 человек.

Слайд 10. Сочетания в Python

Количество сочетаний (биномиальный коэффициент) вычисляется через `math.comb(n, k)`.

```python

import math

n, k = 25, 3

print(math.comb(n, k)) # 2300

```

Для генерации самих подмножеств:

```python

from itertools import combinations

items = ['A', 'B', 'C', 'D']

print(list(combinations(items, 2)))

```

Слайд 11. Сравнение основных формул

Слайд 12. Треугольник Паскаля

Треугольник Паскаля — это бесконечная таблица чисел, где по краям стоят единицы, а каждое число внутри равно сумме двух над ним. Каждое число в треугольнике — это значение $C_n^k$, где $n$ — номер строки, а $k$ — номер элемента в строке.

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

Слайд 13. Как выбрать формулу?

Чтобы не ошибиться в задаче, следуйте простому алгоритму принятия решения. Ответьте на два вопроса: важен ли порядок и все ли элементы используются?

Слайд 14. Часть 2: Разбор олимпиадных задач

Слайд 15. Задача 1: Анаграммы

Сколько различных слов можно составить, переставляя буквы в слове «PYTHON»? А в слове «ALGORITHM»?

В слове «PYTHON» 6 уникальных букв. Это чистая перестановка: $P_6=6!=720$.

В Python: `math.factorial(6)`.

Слайд 16. Задача 2: Коды и пароли

Сколько четырехзначных кодов можно составить из цифр 0-9, если цифры не должны повторяться?

Выбираем 4 цифры из 10, порядок важен: $A_{10}^4=10\cdot 9\cdot 8\cdot 7=5040$.

В Python: `math.perm(10, 4)`.

Слайд 17. Задача 3: Команда знатоков

В классе 15 девочек и 10 мальчиков. Нужно выбрать команду на турнир из 3 девочек и 2 мальчиков. Сколькими способами это можно сделать?

Выбираем девочек: $C_{15}^3$. Выбираем мальчиков: $C_{10}^2$. По правилу умножения: $C_{15}^3\cdot C_{10}^2$.

В Python: `math.comb(15, 3) * math.comb(10, 2)`.

Слайд 18. Инструменты Python для олимпиадника

Быстрое вычисление факториала для любых целых чисел.

Встроенные функции для $C_n^k$ и $A_n^k$, работающие с большими числами.

Модуль для генерации всех возможных комбинаций и перестановок.

Использование треугольника Паскаля (массива), если нужно брать остаток по модулю.

Слайд 19. Подведем итоги

Комбинаторика — это искусство считать, не считая всё подряд.

Главное — определить, важен ли порядок элементов в задаче.

Python предоставляет мощные инструменты `math` и `itertools` для решения задач.

Для олимпиад важно помнить про перестановки с повторениями и формулы включений-исключений.

Практикуйтесь в написании кода для проверки своих математических рассуждений.

Слайд 20. Успехов в решении задач!