Функции из n-множества на k меток
Сюръекция: каждый элемент области получает метку, и ни одна из k меток не пустует. Метки различны (красные / синие ящики). Раздел: комбинаторика.
Контроль: 3→2 даёт 6; 4→2 даёт 14; 5→1 даёт 1; 4→4 даёт 24.
n, k целые 0…15, для ненулевых 1 ≤ k ≤ n. Родитель математика.
N = k! S(n, k)
N = k! · S(n, k)
Сначала неподписанные блоки S(n,k), затем раскраска блоков k! способами. Искомое — N. Буквы e в полях нет.
Не n^k всех функций
Не A = k^n подождите: основание — число меток: все отображения в k точек это k^n, не n^k. На странице слов алфавит n и длина k — другая постановка. Здесь область n, кообласть k, формула k! S(n,k), что равно Σ (−1)^{k−i} C(k,i) i^n.
Как пользоваться
n писем, k различных ящиков, ни один ящик пуст. Получите число раскладок. Если ящики неотличимы — страница Стирлинга. Если пустые можно — k^n в тетради (основание k, показатель n).
Примеры
1. Три на две. 6.
2. Четыре на две. 14 = 2!·7.
3. Все в одну. 1.
4. Перестановка. 4! = 24.
5. Запрет. k = 4 при n = 3.
Ещё задачи
Семь гномов на три именные кровати, все кровати заняты: N(7,3) = 3! S(7,3) = 6×301 = 1806.
Проверка включения для 3→2: C(2,1)1^3 − C(2,0)0^3 wait standard: k=2, Σ (−1)^{2−i} C(2,i) i^3 = C(2,0)(−1)^2 0^3 + … лучше: 2^3 − 2·1^3 = 8−2 = 6. Сошлось.
Связь с C: член включения C(k,i) i^n.
Не кладите пустые как «можно»: тогда не сюръекция.
Состав (n₁,…,n_k) фиксирует, сколько кому. Сумма мультиномиалов по составам с ненулевыми nᵢ даёт N.
N(n,2) = 2^n − 2. Проверка: 2^4 − 2 = 14. Не 2^n: вычли две константы.
Одна размерность: число функций-на.
Два независимых отображения — произведение.
Инъекции k≤n это P(n,k), не сюръекции. Сюръекция требует n ≥ k.
Биекция n = k есть n! = N(n,n) = P(n,n).
Покрасить блоки
Чертёж: n точек, стрелки в k подписанных корзин, ни одна корзина пуста.
Памятка: сначала S, потом × k!.
Хаб комбинаторики держит N рядом с S, чтобы не забыть имена.
Итог: 1 ≤ k ≤ n ≤ 15, N(n,n)=n!.
Знаки включения
Все функции k^n минус те, что промахнулись хотя бы по одной метке, плюс промахнулись по двум, и так далее: N = Σ_{i=0}^{k} (−1)^{k−i} C(k,i) i^n. Страница считает через Стирлинг, сумма — проверка.
0^n в члене i = 0: для n > 0 это 0. Не поле e.
Родитель математика. Сосед по словам: алфавит^длина с другими ролями n и k.
Итог журнала: k! S(n,k), метки заняты, не все k^n.
Контроль: 6; 14; 1; 24. k > n нельзя.
Пример: N(5,2) = 30 = 2^5 − 2.
Не подставляйте 5² = 25.
Рабочий пример: N(5,3) = 6 × 25 = 150.
Связь с k!: множитель имён блоков.
Итог для отчёта: область n, кообласть k, накрытие.
Финальный якорь: 3 на 2 → 6. k = 4 при трёх нельзя.
Добор: не называйте это размещениями P(n,k): P — инъекции в ряд без обязательного накрытия, если k < n инъекция не сюръекция.
Ещё якорь: N(6,1) = 1. N(6,6) = 720.
Журнал: 4 письма в 3 подписанных папки, все папки непусты: N(4,3) = 6 × 6 = 36. S(4,3) = 6.
Не путайте с !n: там кообласть та же, что область, плюс запрет диагонали. Число сюръекций n→n есть n!, среди них беспорядки !n.
Финальный блок: накрытие меток, × k!, n ≤ 15, без пустых.
Ещё контроль: N(4,1) = 1. N(3,3) = 6.
Почему не n^k? На странице кортежей n — алфавит, k — длина. Здесь n — письма, k — ящики, пишут k^n всех функций. Сюръекции строго меньше при k > 1, n > 1? Для 2^3 = 8 всех против 6 сюръекций.
Итог абзаца: каждый ящик получил хотя бы одно письмо, ящики именные.
Связь с C(k,i) во включении.
Две почты — два N.
Финальный добор: k! S(n,k), не S, не k^n, не P(n,k), не !n.
Отчёт: «шесть сюръекций» без 3 и 2 не проверить.
Стык с S(3,2): 3 безымянных, 6 именных.
Не кладите k = 0 при n > 0.
Якорь: 6; 14; 1; 24. k > n нельзя.
Приложение: 8 задач на 4 обязательные темы доклада: N(8,4) = 24 × S(8,4). S(8,4) = 1050, N = 25200.
Одинаковые письма (копии) ломают «область-множество».
Повторный расчёт после снятия имён ящиков: делите на k!, получите S.
Включение-исключение: N = Σ_{i=0}^{k} (−1)^{k−i} C(k,i) i^n. Для 3→2: C(2,0)0³ нет вклада при i=0, C(2,1)·1³ со знаком минус, C(2,2)·2³ = 8, итог 8 − 2 = 6. Страница считает через Стирлинг, сумму можно сверить в тетради.
Все функции без требования накрытия — k^n на соседней логике кортежей, только основание и показатель меняются ролями: здесь метки в основании. Пустые ящики разрешены в k^n и запрещены здесь.
Типичные ошибки
- Ответить k^n со всеми функциями.
- Забыть k! и выдать S(n,k).
- Перепутать, что основание степени — метки, показатель — элементы.
- k > n.
- Смешать с P(n,k).
Соседи: Стирлинг 2-го рода, n^k кортежей, сочетания, факториал, мультиномиал.
Итог добора: сюръекции N = k! S(n,k), каждая метка занята, n и k до 15, 1 ≤ k ≤ n.
Частые вопросы
- Сколько сюръекций из 3 в 2?
- N = 2! · S(3,2) = 2 · 3 = 6. Каждая метка хотя бы раз.
- N(n,n) и N(n,1)?
- N(n,n) = n! — перестановки. N(n,1) = 1 — все в одну метку.
- Это все функции в k точек?
- n^k считает любые, в том числе с пустым образом. Сюръекция пустых не допускает.
- Без имён ящиков?
- S(n,k). Здесь ящики подписаны, поэтому × k!.
- k больше n?
- Ошибка: нельзя накрыть больше меток, чем элементов, без пустых.
- Где хаб?
- Комбинаторика.
Источники
- Школьная комбинаторика: P(n,k) = n!/(n−k)!, C(n,k) = n!/(k!(n−k)!), размещения с повторениями n^k, сочетания с повторениями C(n+k−1, k), полиномиальный коэффициент n!/(n₁! n₂! …).