18.3 Compute Bell and Uppuluri-Carpenter numbers

Module: sage.combinat.expnums

Compute Bell and Uppuluri-Carpenter numbers.

Author: Nick Alexander

Module-level Functions

clear_mpz_globals( )

expnums( )

Compute the first $ n$ exponential numbers around $ aa$ , starting with the zero-th.

Input:

n
- C machine int
aa
- C machine int

Output: A list of length $ n$ .

ALGORITHM: We use the same integer addition algorithm as GAP. This is an extension of Bell's triangle to the general case of exponential numbers. The recursion performs $ O(n^2)$ additions, but the running time is dominated by the cost of the last integer addition, because the growth of the integer results of partial computations is exponential in $ n$ . The algorithm stores $ O(n)$ integers, but each is exponential in $ n$ .

sage: expnums(10, 1)
[1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147]

sage: expnums(10, -1)
[1, -1, 0, 1, 1, -2, -9, -9, 50, 267]

sage: expnums(1, 1)
[1]
sage: expnums(0, 1)
[]
sage: expnums(-1, 0)
[]

Author: Nick Alexander

expnums2( )

A vanilla python (but compiled via pyrex) implementation of expnums.

We Compute the first $ n$ exponential numbers around $ aa$ , starting with the zero-th.

sage: from sage.combinat.expnums import expnums2
sage: expnums2(10, 1)
[1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147]

gmp_randrange( )

init_mpz_globals( )

See About this document... for information on suggesting changes.