Bell's numbers
This example discusses the implementation of the Bell number calculation in the Julia programming language.
Introduction
Bell numbers are a sequence of numbers in combinatorics that is important for counting the number of different ways to divide a set into disjoint subsets.
Bell's number denotes the number of different ways to split a set of elements are divided into nonempty subsets. These numbers are used in probability theory, statistics, and other areas of mathematics.
Examples of such numbers:
-
(an empty set has exactly one partition)
-
-
(for example, the set
{a,b}can be broken down as{{a},{b}}or{{a,b}}) -
(the three elements can be broken down in five different ways)
Implementation of the function bellnum
This function takes an integer n and calculates the corresponding value "Bell's number one." If the passed value is less than zero, the function throws a domain error (DomainError).
The case will be further processed when n >= 2 since the initial values of the Bell numbers are already known: .
"""
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
Next, a vector of the type is created Vector{BigInt} lengths n. We use the type BigInt to avoid overflow, as the Bell numbers themselves grow rapidly. Initially, the first element of the array is set to one because .
Next, the main work takes place on calculating the values of Bell numbers using the Bell Triangle method. The algorithm builds a triangle where each row is i contains (i+1) an element, each of which is a precursor to the next number in the sequence.
Basic steps within cycles:
1. Nested loops update intermediate values in the list to get new members of the Bell sequence.
2. After the inner loop, a new Bell number value is formed, which is stored in the last element of the list.
At the output, the function returns list[n], that is, the last calculated Bell number is exactly the answer for the nth element of the sequence.
Using the function
After defining the function, a simple loop from 1 to 50 is used, which calls our function one at a time. bellnum(i) for each i in this range, and outputs the results to the console via println().
for i in 1:50 # Проходим по числам от 1 до 50
println(bellnum(i)) # Выводим значения чисел Белла
end
Conclusion
We reviewed the implementation of the algorithm for calculating Bell numbers in Julia, understood its logic, and put it into practice by outputting a series of numbers. This approach makes it easy to find large values of Bell numbers without using recursion. This can be useful in problems of discrete mathematics and analysis of combinatorial structures.
The example was developed using materials from Rosetta Code