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

Формула

How this is calculated

Введіть два невід'ємних цілих числа: n — кількість різних (помічених) елементів, і k — кількість непорожніх підмножин, на які ви хочете їх розбити. Самі підмножини є непоміченими, тому важливе лише групування, а не порядок груп.

Калькулятор використовує класичне рекурентне співвідношення S(n, k) = k · S(n−1, k) + S(n−1, k−1). Інтуїтивно, додаючи n-й елемент, ви або поміщаєте його в одну з k наявних підмножин (k · S(n−1, k) способів), або створюєте нову підмножину лише з нього (S(n−1, k−1) способів). Початкові умови: S(0,0) = 1 (один спосіб розбити порожню множину на порожню) і S(n,0) = 0 при n > 0, а S(n,k) = 0, коли k > n. Рекурентне співвідношення обчислюється методом динамічного програмування по одному рядку для ефективності.

Стовпчиковий графік показує S(n, k) для кожного k від 1 до n, а їхня сума — число Белла B(n), загальна кількість розбиттів n-елементної множини. Результати є точними цілими числами; вхідні значення обмежені n ≤ 170, щоб підрахунки залишалися в межах точності числа подвійної точності. Нецілі значення округлюються до найближчого цілого числа.