Числа Белла

В этом примере рассматривается реализация вычисления чисел Белла на языке программирования Julia.

Введение

Числа Белла — это последовательность чисел в комбинаторике, которая имеет важное значение для подсчета количества различных способов разбиения множества на непересекающиеся подмножества.

Число Белла обозначает количество различных способов разбить множество из элементов на непустые подмножества. Эти числа находят применение в теории вероятностей, статистике и других областях математики.

Примеры таких чисел:

(пустое множество имеет ровно одно разбиение)
(например, множество {a,b} можно разбить как {{a},{b}} или {{a,b}})
(три элемента можно разбить пятью различными способами)

Реализация функции `bellnum`

Эта функция принимает целое число n и вычисляет соответствующее ему -ое число Белла. Если переданное значение меньше нуля, функция выбрасывает ошибку доменной области (DomainError).

Дальнейшей обработке будет подвергнут случай, когда n >= 2, поскольку начальные значения чисел Белла уже известны: .

"""
    bellnum(n)
Compute the ``n``th Bell number.
"""
function bellnum(n::Integer)
    if n < 0
        throw(DomainError(n)) # Выкидываем ошибку для недопустимых значений
    elseif n < 2
        return 1              # Для n=0 и n=1 значение равно 1
    end
    
    list = Vector{BigInt}(undef, n)   # Создаем вектор размером n
    list[1] = 1                       # Начальное значение

    for i = 2:n             # Для каждой строки от 2 до n
        for j = 1:i - 2     # Обновляем все промежуточные значения
            list[i - j - 1] += list[i - j]
        end
        list[i] = list[1] + list[i - 1]  # Получаем новое число Белла
    end

    return list[n]       # Возвращаем результат
end

bellnum

Далее создаётся вектор типа Vector{BigInt} длины n. Мы используем тип BigInt, чтобы избежать переполнения, так как сами числа Белла быстро растут. Изначально первый элемент массива устанавливается равным единице, потому что .

Далее происходит основная работа по вычислению значений чисел Белла с помощью метода Белла (Bell Triangle). Алгоритм строит треугольник, где каждая строка i содержит (i+1) элемент, каждый из которых является предшественником следующего числа последовательности.

Основные шаги внутри циклов:

1. Вложенные циклы обновляют промежуточные значения в списке, чтобы получить новые члены последовательности Белла.

2. После внутреннего цикла формируется новое значение числа Белла, которое сохраняется в последний элемент списка.

На выходе функция возвращает list[n], т.е. последнее вычисленное число Белла — именно ответ для n-ого элемента последовательности.

Использование функции

После определения функции используется простой цикл от 1 до 50, который поочерёдно вызывает нашу функцию bellnum(i) для каждого i в этом диапазоне и выводит результаты в консоль через println().

for i in 1:50          # Проходим по числам от 1 до 50
    println(bellnum(i)) # Выводим значения чисел Белла
end

1
2
5
15
52
203
877
4140
21147
115975
678570
4213597
27644437
190899322
1382958545
10480142147
82864869804
682076806159
5832742205057
51724158235372
474869816156751
4506715738447323
44152005855084346
445958869294805289
4638590332229999353
49631246523618756274
545717047936059989389
6160539404599934652455
71339801938860275191172
846749014511809332450147
10293358946226376485095653
128064670049908713818925644
1629595892846007606764728147
21195039388640360462388656799
281600203019560266563340426570
3819714729894818339975525681317
52868366208550447901945575624941
746289892095625330523099540639146
10738823330774692832768857986425209
157450588391204931289324344702531067
2351152507740617628200694077243788988
35742549198872617291353508656626642567
552950118797165484321714693280737767385
8701963427387055089023600531855797148876
139258505266263669602347053993654079693415
2265418219334494002928484444705392276158355
37450059502461511196505342096431510120174682
628919796303118415420210454071849537746015761
10726137154573358400342215518590002633917247281
185724268771078270438257767181908917499221852770

Заключение

Мы рассмотрели реализацию алгоритма для вычисления чисел Белла на языке Julia, поняли его логику работы, а также применили его на практике, выводя серию чисел. Такой подход позволяет легко находить большие значения чисел Белла без использования рекурсии. Это может быть полезно в задачах дискретной математики и анализа комбинаторных структур.

Пример разработан с использованием материалов Rosetta Code

Числа Белла