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

Введение

Числа Стирлинга первого рода — это важные целые числа в комбинаторике, которые появляются при изучении перестановок. Они обозначаются, как [nk]\left[ {n \atop k} \right], где nn и kk — неотрицательные целые числа. Эти числа показывают количество перестановок nn элементов с образованием kk циклов. Они полезны при анализе циклов в перестановках и других задачах, связанных с комбинаторными структурами.

Операция

Числа Стирлинга первого рода можно вычислить рекурсивно с использованием следующих соотношений:

  1. Базовые условия:

    • [00]=1\left[ {0 \atop 0} \right] = 1
    • [n0]=0\left[ {n \atop 0} \right] = 0 для n>0n > 0
    • [0k]=0\left[ {0 \atop k} \right] = 0 для k>0k > 0

  2. Рекурсивная формула:

    [nk]=[n−1k−1]+(n−1)[n−1k]\begin{equation*} \begin{aligned} \left[ {n \atop k} \right] = \left[ {n-1 \atop k-1} \right] + (n-1) \left[ {n-1 \atop k} \right] \end{aligned} \end{equation*}

Свойства

  • Знакочередование: Числа Стирлинга первого рода имеют чередование знаков в зависимости от четности n−kn-k.
  • Связь с факториалами: Их можно выразить через подстановки факториалов и разделительные свойства при перестановках.
  • Порождающая функция: Для чисел Стирлинга первого рода можно записать порождающую функцию: ∑k=0n[nk]xk=x(x+1)(x+2)⋯(x+n−1)\begin{equation*} \begin{aligned} \sum_{k=0}^{n} \left[ {n \atop k} \right] x^k = x(x+1)(x+2)\cdots(x+n-1) \end{aligned} \end{equation*}

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

Пример 1

Найдем число Стирлинга первого рода [42]\left[ {4 \atop 2} \right]:

Используя рекурсивную формулу:

[42]=[31]+3[32]=(1+3×2)=7\begin{equation*} \begin{aligned} \left[ {4 \atop 2} \right] &= \left[ {3 \atop 1} \right] + 3 \left[ {3 \atop 2} \right]\\ &= (1 + 3 \times 2) = 7 \end{aligned} \end{equation*}

Пример 2

Вычислим число Стирлинга первого рода [33]\left[ {3 \atop 3} \right]:

По определению:

[33]=[22]=1\begin{equation*} \begin{aligned} \left[ {3 \atop 3} \right] = \left[ {2 \atop 2} \right] = 1 \end{aligned} \end{equation*}

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

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

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

  • Программирование: Используются в алгоритмах, связанных с генерацией и анализом перестановок.
  • Статистика: Исследование данных с помощью моделей, основанных на циклических структурах, может требовать использования этих чисел.
  • Экономика: В анализе временных рядов, где изучаются циклические колебания, могут применяться подобные математические модели.

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