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

Введение

Числа Стирлинга второго рода — это целые числа, описывающие количество способов разбиения множества из nn элементов на kk непересекающихся непустых подмножеств. Эти числа играют важную роль в комбинаторике и ряде других математических дисциплин, включая теорию вероятностей и статистику.

Операция

Числа Стирлинга второго рода обозначаются как S(n,k)S(n, k). Они могут быть вычислены с использованием рекуррентной формулы:

S(n,k)=k⋅S(n−1,k)+S(n−1,k−1)\begin{equation*} \begin{aligned} S(n, k) = k \cdot S(n-1, k) + S(n-1, k-1) \end{aligned} \end{equation*}

с начальными условиями:

S(0,0)=1,S(n,0)=0для n>0,S(0,k)=0для k>0\begin{equation*} \begin{aligned} S(0, 0) = 1, \quad S(n, 0) = 0 \quad \text{для}\, n > 0, \quad S(0, k) = 0 \quad \text{для}\, k > 0 \end{aligned} \end{equation*}

Свойства

  • Неотрицательность: Все числа Стирлинга второго рода неотрицательны.
  • Симметрия: За счет разбиений множества, числа обладают интересными симметриями в комбинаторных тождествах.
  • Связь с факториалом: Можно выразить через произведения и комбинаторные коэффициенты.

Примеры использования

Пример 1

Рассчитайте S(4,2)S(4, 2) — число способов разбиения множества из 4 элементов на 2 подмножества:

  1. Используем рекуррентную формулу:
S(4,2)=2⋅S(3,2)+S(3,1)\begin{equation*} \begin{aligned} S(4, 2) = 2 \cdot S(3, 2) + S(3, 1) \end{aligned} \end{equation*}
  1. Находим S(3,2)S(3, 2) и S(3,1)S(3, 1):
S(3,2)=2⋅S(2,2)+S(2,1)=2⋅1+1=3S(3,1)=1\begin{equation*} \begin{aligned} S(3, 2) &= 2 \cdot S(2, 2) + S(2, 1) \\&= 2 \cdot 1 + 1 = 3 \\ S(3, 1) &= 1 \end{aligned} \end{equation*}
  1. Подставляем в формулу:
S(4,2)=2⋅3+1=7\begin{equation*} \begin{aligned} S(4, 2) = 2 \cdot 3 + 1 = 7 \end{aligned} \end{equation*}

Пример 2

Вычислите S(5,3)S(5, 3) — количество способов разбиения множества из 5 элементов на 3 подмножества:

  1. Используем рекурсию:
S(5,3)=3⋅S(4,3)+S(4,2)\begin{equation*} \begin{aligned} S(5, 3) = 3 \cdot S(4, 3) + S(4, 2) \end{aligned} \end{equation*}
  1. Из предыдущих вычислений знаем S(4,2)=7S(4, 2) = 7. Находим S(4,3)S(4, 3):
S(4,3)=3⋅S(3,3)+S(3,2)=3⋅1+3=6\begin{equation*} \begin{aligned} S(4, 3) &= 3 \cdot S(3, 3) + S(3, 2) \\&= 3 \cdot 1 + 3 = 6 \end{aligned} \end{equation*}
  1. Подставляем:
S(5,3)=3⋅6+7=25\begin{equation*} \begin{aligned} S(5, 3) = 3 \cdot 6 + 7 = 25 \end{aligned} \end{equation*}

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

  • Что такое число Стирлинга второго рода?
    • Это количество способов разбиения множества из nn элементов на kk непустых подмножеств.
  • Как можно вычислить числа Стирлинга второго рода?
    • Используя рекуррентные соотношения, с начальным условием S(0,0)=1S(0, 0) = 1.

Примеры из жизни

  • Классификация объектов: Разбиение обучающих данных на несколько классов в задачах классификации может описываться числами Стирлинга второго рода.
  • Организация событий: Разделение гостей на группы по интересам во время конференций.
  • Интернет-маркетинг: Анализ сегментации рынка и целевой аудитории, где необходимо распределить пользователей по непересекающимся категориям.

Ссылки на литературу и ресурсы