Треугольник Паскаля

Лаборатория по комбинаторике для 8-9 классов. Всё строится вокруг одного вопроса: Ана хочет каждый день ходить в школу новым маршрутом — на сколько дней ей хватит? Город Аны — сетка улиц, на которой ученик рисует маршруты, нажимая на перекрёстки, а анимации показывают, как маршруты складываются от перекрёстка к перекрёстку, пока сетка не поворачивается и не превращается в треугольник Паскаля.

Комнаты 1-4 повторяют степени и факториалы; 5-9 — задача Аны; 10-13 подводят к выбору без учёта порядка; 14-16 вводят треугольник и биномиальные коэффициенты с анимированными комбинаторными доказательствами; 17-20 — для углубления: подмножества, закономерности треугольника, Серпинский и бином Ньютона.

Чему учатся

• Правило произведения: n^k (монеты, кости, пин-коды) и n! (люди в ряд); если первый выбран, остаётся (n − 1)! способов.
• Неразличимые элементы: каждая расстановка повторяется k! раз, поэтому делим на k! (фрукты в понедельник, повторяющиеся буквы слова PALABRA). Типичная ошибка — делить на 3 вместо 3!.
• Правило суммы: к перекрёстку приходят слева или снизу, но не с обеих сторон сразу. Так считаются маршруты в любом городе, в том числе с перекрытыми улицами.
• Правило произведения на маршрутах: проход через перекрёсток — умножение; через одно место или другое (не оба) — сложение. Подсчёт через дополнение.
• Биекции: каждый ряд банок с вареньем — это маршрут Аны, а каждый маршрут — ряд; поэтому их поровну.
• Выбор k из n без учёта порядка: $\binom{n}{k} = \frac{n!}{k!,(n-k)!}$ (треугольники на 7 точках, команды).
• Треугольник Паскаля — повёрнутая сетка Аны; строка n, место k (считая от 0).
• Комбинаторные доказательства без вычислений: симметрия $\binom{n}{k} = \binom{n}{n-k}$ (выбрать идущих — то же, что выбрать остающихся) и правило Паскаля (опоздавший Евгений делит команды на две кучки).
• У множества из n элементов 2^n подмножеств — двумя способами: лампочки и сумма строки треугольника.
• Закономерности: треугольные числа, «хоккейная клюшка», Фибоначчи, степени 11 и треугольник Серпинского из нечётных чисел.
• Бином Ньютона: коэффициент при $a^k b^{n-k}$ в $(a+b)^n$ равен $\binom{n}{k}$.

Как устроена работа

Перед подсчётом делается ставка (сколько маршрутов?) и сравнивается с ответом. Первые перекрёстки считают, рисуя все маршруты; когда рисовать становится долго, появляется идея, которая решает задачу. Ответы проверяются сразу, с подсказками после ошибок и решением после четвёртой.

Материалы

Презентации «Combinatoria desde cero» I-III (в материалах лаборатории, на испанском) идут по той же линии: маршруты Аны, банки, опоздавший Евгений и классические пари.