OFFSET
0,5
COMMENTS
The Bell-transform is a sequence-to-triangle transformation B: G(n) -> T(n, k) defined by Sum_{k=1..n} T(n, k) * u^k * x^n / n! = exp(Sum_{n>0} u * G(n) * x^n / n!). The input sequence G is called the 'generating sequence' of the triangle. We assume it to be a 0-based sequence with G(0) = 0 and G(1) != 0. This sequence appears as column 1 of the triangle, T(n, 1) = G(n) for n >= 1. (G(0) = 0 is a convention that is often replaced by the requirement that the function is 1-based.)
By applying the triangle-to-sequence transformation n -> Sum(Trow(n)) to the triangle T, we obtain the exponential transform of the generating function. This means that one typically considers a triple of sequences, G -> T -> E, whose paradigmatic and eponymous example is (A000012, A048993, A000110). A second example: The triple (A000142, A132393, A000142) shows that the unsigned Stirling cycle numbers map the factorial numbers onto themselves.
A reference implementation is the Python function BellTransform(seq: list[int]) -> list[list[int]] given below. Note that it is defined by recursion since T(n, k) is expressed in terms of T(n-m, k-1) for m = 1, ..., n - k + 1.
LINKS
Peter Luschny, The Bell transform.
Peter Luschny, Examples of the Bell transform, a SageMath notebook.
EXAMPLE
Triangle begins:
[0] [1]
[1] [0, 1]
[2] [0, 3, 1]
[3] [0, 4, 9, 1]
[4] [0, 7, 43, 18, 1]
[5] [0, 11, 155, 175, 30, 1]
[6] [0, 18, 541, 1230, 485, 45, 1]
[7] [0, 29, 1799, 7336, 5600, 1085, 63, 1]
[8] [0, 47, 5923, 40558, 52661, 18550, 2114, 84, 1]
MAPLE
with(combinat): lucas := n -> fibonacci(n+1) + fibonacci(n-1):
T := proc(n, k) option remember; local j; if k = 0 then return 0^n fi;
add(ifelse(j > 0, 1, 0) * binomial(n - 1, j - 1) * lucas(j) * T(n - j, k - 1), j = 0..n - k + 1) end: seq(print(seq(T(n, k), k = 0..n)), n = 0..8);
MATHEMATICA
T[n_, 0] := Boole[n == 0]; T[n_, k_] := T[n, k] = Sum[Boole[j > 0] * Binomial[n - 1, j - 1] * LucasL[j] * T[n - j, k - 1], {j, 0, n - k + 1}]; Table[T[n, k], {n, 0, 10}, {k, 0, n}]
PROG
(Python)
from math import comb as binomial
def BellTransform(seq: list[int]) -> list[list[int]]:
N = len(seq) - 1
T = [[0]*(n+1) for n in range(N+1)]
T[0][0] = 1
for n in range(1, N+1):
for k in range(1, n+1):
T[n][k] = sum(binomial(n-1, j-1) * seq[j] * T[n-j][k-1] for j in range(1, n-k+2))
return T
(Python) # The function BellTransform applied to the Lucas numbers:
F = lambda n: (1<<((n+1)*(n+1)))//((4<<(2*n))-(2<<n)-1)&((2<<n)-1)
N = 8; seq = [0]+[F(2*n)//F(n) for n in range(1, N+1)]
T = BellTransform(seq)
for row in T: print(row)
CROSSREFS
Triangles that are generated by the Bell-transform. See the SageMath notebook in the Links for these examples.
| A-index | Triangle | generating sequence | exp-transform |
| --------------------------------------------------------- |
KEYWORD
nonn,tabl
AUTHOR
Peter Luschny, Mar 29 2026
STATUS
approved