OFFSET
0,8
COMMENTS
Consider the sequence S0 -> T0 -> S1 -> T1 -> S2 -> T2 -> ... Here Sn -> Tn indicates the Bell transform mapping a sequence Sn to a triangle Tn as defined in the link and Tn -> S{n+1} the operator associating a triangle with the sequence of its row sums. If
S0 = A000012 = <1,1,1,...> then
T0 = A048993 # Stirling subset numbers,
S1 = A000110 # Bell numbers,
T1 = A264428 # Bell transform of Bell numbers,
S2 = A187761 # second-order Bell numbers,
T2 = A264430 # Bell transform of second-order Bell numbers,
S3 = A264432 # third-order Bell numbers.
This construction is closely related to permutations trees and A179455. Sn is A179455_col(n+1) prepended by A179455_diag(k) = k! for k <= n. In other words, Sn 'converges' to n! for n -> oo.
Given a sequence (s(n))n>=0 with s(0) = 0 and with e.g.f. B(x) = Sum_{n >= 1} s(n)*x^n/n!, then the Bell matrix associated with s(n) equals the exponential Riordan array [1, B(x)] belonging to the Lagrange subgroup of the exponential Riordan group. Omitting the first row and column from the Bell matrix produces the exponential Riordan array [d/dx(B(x)), B(x)] belonging to the Derivative subgroup of the exponential Riordan group. - Peter Bala, Jun 07 2016
LINKS
G. C. Greubel, Table of n, a(n) for n = 0..1325
Peter Luschny, The Bell transform
Peter Luschny, Permutation Trees
FORMULA
From Peter Bala, Jun 07 2016: (Start)
E.g.f.: exp(t*B(x)), where B(x) = Integral_{u = 0..x} exp(exp(u) - 1) du = x + x^2/2! + 2*x^3/3! + 5*x^4/4! + 15*x^5/5! + 52*x^6/6! + ....
Row polynomial recurrence: R(n+1,t) = t*Sum_{k = 0 ..n} binomial(n,k)*Bell(k)* R(n-k,t) with R(0,t) = 1. (End)
EXAMPLE
Triangle starts:
[1]
[0, 1]
[0, 1, 1]
[0, 2, 3, 1]
[0, 5, 11, 6, 1]
[0, 15, 45, 35, 10, 1]
[0, 52, 205, 210, 85, 15, 1]
[0, 203, 1029, 1330, 700, 175, 21, 1]
[0, 877, 5635, 8946, 5845, 1890, 322, 28, 1]
MAPLE
# Computes sequence in matrix form.
BellMatrix := proc(f, len) local T, A; A := [seq(f(n), n=0..len-2)];
T := proc(n, k) option remember; if k=0 then k^n else
add(binomial(n-1, j-1)*T(n-j, k-1)*A[j], j=1..n-k+1) fi end;
Matrix(len, (n, k)->T(n-1, k-1), shape=triangular[lower]) end:
BellMatrix(n -> combinat:-bell(n), 9); # Peter Luschny, Jan 21 2016
# Alternative, using the recurrence of Peter Bala:
R := proc(n) option remember; if n = 0 then 1 else
t*add(binomial(n-1, k)*combinat:-bell(k)*R(n-k-1, t), k=0..n-1) fi end:
T_row := n-> seq(coeff(R(n), t, k), k=0..n):
seq(print(T_row(n)), n=0..8); # Peter Luschny, Jun 09 2016
MATHEMATICA
BellMatrix[f_Function|f_Symbol, len_] := With[{t = Array[f, len, 0]}, Table[BellY[n, k, t], {n, 0, len-1}, {k, 0, len-1}]];
rows = 11;
M = BellMatrix[BellB, rows];
Table[M[[n, k]], {n, 1, rows}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jan 21 2016, updated Jul 14 2018 *)
With[{r = 8}, Flatten[Table[BellY[n, k, BellB[Range[0, r]]], {n, 0, r}, {k, 0, n}]]] (* Jan Mangaldan, May 22 2016 *)
PROG
(Sage)
# The functions below are referenced in various other sequences.
def bell_transform(n, a): # partition_based
row = []
fn = factorial(n)
for k in (0..n):
result = 0
for p in Partitions(n, length=k):
factorial_product = 1
power_factorial_product = 1
for part, count in p.to_exp_dict().items():
factorial_product *= factorial(count)
power_factorial_product *= factorial(part)**count
coefficient = fn//(factorial_product*power_factorial_product)
result += coefficient*prod([a[i-1] for i in p])
row.append(result)
return row
def bell_matrix(generator, dim):
G = [generator(k) for k in srange(dim)]
row = lambda n: bell_transform(n, G)
return matrix(ZZ, [row(n)+[0]*(dim-n-1) for n in srange(dim)])
def inverse_bell_matrix(generator, dim):
G = [generator(k) for k in srange(dim)]
row = lambda n: bell_transform(n, G)
M = matrix(ZZ, [row(n)+[0]*(dim-n-1) for n in srange(dim)]).inverse()
return matrix(ZZ, dim, lambda n, k: (-1)^(n-k)*M[n, k])
bell_numbers = [sum(bell_transform(n, [1]*10)) for n in range(11)]
for n in range(11): print(bell_transform(n, bell_numbers))
(PARI)
bell_matrix(f, len) = { my( m = matrix(len, len) ); m[1, 1] = 1;
for( n = 1, len-1, m[n+1, 2] = f(n-1) );
for( n = 0, len-1, for( k = 1, n,
m[n+1, k+1] = sum(j = 1, n-k+1, binomial(n-1, j-1)*m[n-j+1, k]*m[j+1, 2]) ));
return( m )
}
f(n) = polcoeff( sum( k=0, n, prod( i=1, k, x / (1 - i*x)), x^n * O(x)), n);
bell_matrix(f, 9) \\ Peter Luschny, Jan 24 2016
(Python)
from functools import cache
from math import comb as binomial
def BellMatrix(f, size):
A = [f(n) for n in range(size - 1)]
@cache
def T(n, k):
if k == 0: return k ** n
return sum(
binomial(n - 1, j) * T(n - j - 1, k - 1) * A[j]
for j in range(n - k + 1) )
return [[T(n, k) for k in range(n + 1)] for n in range(size)]
@cache
def b(n, k=0): return n < 1 or k*b(n-1, k) + b(n-1, k+1)
print(BellMatrix(b, 9)) # Peter Luschny, Jun 14 2022
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Peter Luschny, Nov 13 2015
STATUS
approved