bell numbers represent the number of ways to partition a set into nonempty subsets this module provides functions to calculate bell numbers for sets of integers in other words the first n 1 bell numbers for more information about bell numbers refer to https en wikipedia orgwikibellnumber calculate bell numbers for the sets of lengths from 0 to maxsetlength in other words calculate first maxsetlength 1 bell numbers args maxsetlength int the maximum length of the sets for which bell numbers are calculated returns list a list of bell numbers for sets of lengths from 0 to maxsetlength examples bellnumbers0 1 bellnumbers1 1 1 bellnumbers5 1 1 2 5 15 52 calculate the binomial coefficient ctotalelements elementstochoose args totalelements int the total number of elements elementstochoose int the number of elements to choose returns int the binomial coefficient ctotalelements elementstochoose examples binomialcoefficient5 2 10 binomialcoefficient6 3 20 calculate bell numbers for the sets of lengths from 0 to max_set_length in other words calculate first max_set_length 1 bell numbers args max_set_length int the maximum length of the sets for which bell numbers are calculated returns list a list of bell numbers for sets of lengths from 0 to max_set_length examples bell_numbers 0 1 bell_numbers 1 1 1 bell_numbers 5 1 1 2 5 15 52 calculate the binomial coefficient c total_elements elements_to_choose args total_elements int the total number of elements elements_to_choose int the number of elements to choose returns int the binomial coefficient c total_elements elements_to_choose examples _binomial_coefficient 5 2 10 _binomial_coefficient 6 3 20
def bell_numbers(max_set_length: int) -> list[int]:
    
    if max_set_length < 0:
        raise ValueError("max_set_length must be non-negative")

    bell = [0] * (max_set_length + 1)
    bell[0] = 1

    for i in range(1, max_set_length + 1):
        for j in range(i):
            bell[i] += _binomial_coefficient(i - 1, j) * bell[j]

    return bell


def _binomial_coefficient(total_elements: int, elements_to_choose: int) -> int:
    
    if elements_to_choose in {0, total_elements}:
        return 1

    if elements_to_choose > total_elements - elements_to_choose:
        elements_to_choose = total_elements - elements_to_choose

    coefficient = 1
    for i in range(elements_to_choose):
        coefficient *= total_elements - i
        coefficient //= i + 1

    return coefficient


if __name__ == "__main__":
    import doctest

    doctest.testmod()