Калькулятор чисел Стирлинга

Добро пожаловать в калькулятор чисел Стирлинга — комплексный инструмент комбинаторики для вычисления чисел Стирлинга первого рода (беззнаковые — перестановки в циклы) и второго рода (разбиение множества на непустые подмножества). С интерактивной визуализацией треугольников, пошаговым выводом рекуррентных соотношений, диаграммами распределения и глубокой комбинаторной интерпретацией, этот калькулятор создан для студентов, преподавателей, исследователей и спортивных программистов, которым нужны быстрые и точные результаты с образовательным контекстом.

Что такое числа Стирлинга?

Числа Стирлинга — это два семейства чисел, которые естественным образом возникают в комбинаторике, алгебре и анализе. Названные в честь шотландского математика Джеймса Стирлинга (1692–1770), они связывают факториалы, биномиальные коэффициенты и полиномиальные тождества. Хотя они менее известны, чем треугольник Паскаля, они столь же фундаментальны и встречаются во всей дискретной математике.

Числа Стирлинга первого рода

Беззнаковые числа Стирлинга первого рода, обозначаемые \(|s(n,k)|\) или \(\left[{n \atop k}\right]\), определяют количество перестановок \(n\) элементов, которые распадаются ровно на \(k\) непересекающихся циклов.

Интуиция: Рассмотрите, куда попадает элемент \(n\). Либо он вставляется в один из существующих циклов (есть \(n-1\) позиций для вставки, по одной перед каждым из \(n-1\) других элементов) — это дает слагаемое \((n-1)\cdot|s(n-1,k)|\), либо он образует свой собственный новый 1-цикл, что дает \(|s(n-1,k-1)|\).

Основные факты:

• \(|s(n,1)| = (n-1)!\) — циклические перестановки (один большой цикл)
• \(|s(n,n)| = 1\) — тождественная перестановка (все элементы на своих местах)
• \(|s(n,n-1)| = \binom{n}{2}\) — одна транспозиция
• \(\sum_{k=0}^{n} |s(n,k)| = n!\) — общее количество перестановок

Числа Стирлинга второго рода

Числа Стирлинга второго рода, обозначаемые \(S(n,k)\) или \(\left\{{n \atop k}\right\}\), определяют количество способов разбить множество из \(n\) элементов ровно на \(k\) непустых подмножеств.

Интуиция: Рассмотрите, куда попадает элемент \(n\). Либо он присоединяется к одному из \(k\) существующих подмножеств (\(k\) вариантов) — это дает слагаемое \(k \cdot S(n-1,k)\), либо он образует свое собственное новое одноэлементное подмножество, что дает \(S(n-1,k-1)\).

Основные факты:

• \(S(n,1) = 1\) — только один способ: все элементы в одном множестве
• \(S(n,n) = 1\) — только один способ: каждый элемент в отдельном подмножестве
• \(S(n,2) = 2^{n-1} - 1\) — способы разделения на два непустых подмножества
• \(S(n,n-1) = \binom{n}{2}\) — выбор пары, которая разделит подмножество
• \(\sum_{k=0}^{n} S(n,k) = B(n)\) — n-ое число Белла

Явная формула (Второй род)

Как пользоваться этим калькулятором

1. Введите n: Общее количество элементов (от 0 до 200).
2. Введите k: Количество циклов (первый род) или подмножеств (второй род), при этом 0 ≤ k ≤ n.
3. Выберите род: Выберите Первый род, Второй род или оба для параллельного сравнения.
4. Рассчитать: Нажмите "Рассчитать числа Стирлинга", чтобы увидеть результаты с пошаговым выводом, визуализацией треугольника и диаграммой распределения.

Сравнение: Первый род против Второго рода

Применение чисел Стирлинга

Преобразование многочленов

Числа Стирлинга связывают различные базисы многочленов:

• Возрастающий факториал: \(x^{(n)} = \sum_{k} |s(n,k)|\, x^k\)
• Обычная степень: \(x^n = \sum_{k} S(n,k)\, x^{\underline{k}}\) (убывающий факториал)

Вероятность и статистика

Числа Стирлинга появляются при вычислении моментов вероятностных распределений, особенно при переходе между обычными и факториальными моментами. Они важны в анализе случайных перестановок и задач о размещении.

Информатика

В анализе алгоритмов числа Стирлинга возникают при подсчете способов распределения объектов по контейнерам, анализе хэш-таблиц и изучении случайных перестановок. Второй род напрямую связан с подсчетом сюръективных функций: количество функций "на" из n-множества в k-множество равно \(k!\, S(n,k)\).

Теория чисел

Числа Стирлинга связаны с числами Бернулли, гармоническими числами и различными суммарными тождествами. Они встречаются в исчислении конечных разностей и в формуле Эйлера-Маклорена.

Часто задаваемые вопросы

Что такое числа Стирлинга первого рода?

Беззнаковые числа Стирлинга первого рода, обозначаемые |s(n,k)|, определяют количество перестановок n элементов, состоящих ровно из k непересекающихся циклов. Они удовлетворяют рекуррентному соотношению |s(n,k)| = (n−1)·|s(n−1,k)| + |s(n−1,k−1)| с начальным значением |s(0,0)| = 1. Сумма строк дает n!, так как любая перестановка имеет определенное количество циклов.

Что такое числа Стирлинга второго рода?

Числа Стирлинга второго рода, обозначаемые S(n,k), определяют количество способов разбиения множества из n элементов на k непустых подмножеств. Они удовлетворяют рекуррентному соотношению S(n,k) = k·S(n−1,k) + S(n−1,k−1) с начальным значением S(0,0) = 1. Сумма строк дает числа Белла B(n).

В чем разница между числами Стирлинга первого и второго рода?

Первый род (беззнаковый) считает перестановки с k циклами — порядок внутри каждого цикла важен. Второй род считает разбиения множества на k подмножеств — порядок внутри подмножеств не важен. Они связаны через обращение матриц: треугольник знаковых чисел первого рода является обратным для треугольника чисел второго рода.

Как числа Стирлинга используются в математике?

Числа Стирлинга используются для преобразования многочленов между убывающими/возрастающими факториалами и обычными степенями, при вычислении моментов распределений вероятностей, в комбинаторных тождествах, теории чисел и анализе алгоритмов.

Какова связь между числами Стирлинга и числами Белла?

n-ое число Белла B(n) равно сумме всех чисел Стирлинга второго рода в строке n: B(n) = Σ S(n,k) для k от 0 до n. Числа Белла считают общее количество разбиений множества из n элементов на любое количество непустых подмножеств.

Существует ли явная формула для чисел Стирлинга?

Да, для второго рода существует явная формула через включение-исключение: S(n,k) = (1/k!) Σ (−1)^(k−j) C(k,j) j^n для j от 0 до k. Первый род можно вычислить по рекурсии или через связь с возрастающими факториалами.

Дополнительные ресурсы

• Числа Стирлинга первого рода — Википедия
• Числа Стирлинга второго рода — Википедия
• OEIS A008277 — Числа Стирлинга второго рода
• OEIS A130534 — Беззнаковые числа Стирлинга первого рода