login
Triangle read by rows, Bell transform of Bell numbers.
187

%I #83 Feb 20 2023 16:30:55

%S 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,

%T 0,203,1029,1330,700,175,21,1,0,877,5635,8946,5845,1890,322,28,1,0,

%U 4140,33387,63917,50358,20055,4410,546,36,1,0,21147,212535,484140,450905,214515,57855,9240,870,45,1

%N Triangle read by rows, Bell transform of Bell numbers.

%C 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

%C S0 = A000012 = <1,1,1,...> then

%C T0 = A048993 # Stirling subset numbers,

%C S1 = A000110 # Bell numbers,

%C T1 = A264428 # Bell transform of Bell numbers,

%C S2 = A187761 # second-order Bell numbers,

%C T2 = A264430 # Bell transform of second-order Bell numbers,

%C S3 = A264432 # third-order Bell numbers.

%C 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.

%C 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

%H G. C. Greubel, <a href="/A264428/b264428.txt">Table of n, a(n) for n = 0..1325</a>

%H Peter Luschny, <a href="https://oeis.org/wiki/User:Peter_Luschny/BellTransform">The Bell transform</a>

%H Peter Luschny, <a href="http://www.oeis.org/wiki/User:Peter_Luschny/PermutationTrees">Permutation Trees</a>

%F From _Peter Bala_, Jun 07 2016: (Start)

%F 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! + ....

%F 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)

%e Triangle starts:

%e [1]

%e [0, 1]

%e [0, 1, 1]

%e [0, 2, 3, 1]

%e [0, 5, 11, 6, 1]

%e [0, 15, 45, 35, 10, 1]

%e [0, 52, 205, 210, 85, 15, 1]

%e [0, 203, 1029, 1330, 700, 175, 21, 1]

%e [0, 877, 5635, 8946, 5845, 1890, 322, 28, 1]

%p # Computes sequence in matrix form.

%p BellMatrix := proc(f, len) local T, A; A := [seq(f(n), n=0..len-2)];

%p T := proc(n, k) option remember; if k=0 then k^n else

%p add(binomial(n-1,j-1)*T(n-j,k-1)*A[j], j=1..n-k+1) fi end;

%p Matrix(len, (n,k)->T(n-1,k-1), shape=triangular[lower]) end:

%p BellMatrix(n -> combinat:-bell(n), 9); # _Peter Luschny_, Jan 21 2016

%p # Alternative, using the recurrence of _Peter Bala_:

%p R := proc(n) option remember; if n = 0 then 1 else

%p t*add(binomial(n-1,k)*combinat:-bell(k)*R(n-k-1,t),k=0..n-1) fi end:

%p T_row := n-> seq(coeff(R(n), t, k), k=0..n):

%p seq(print(T_row(n)),n=0..8); # _Peter Luschny_, Jun 09 2016

%t 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}]];

%t rows = 11;

%t M = BellMatrix[BellB, rows];

%t Table[M[[n, k]], {n, 1, rows}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Jan 21 2016, updated Jul 14 2018 *)

%t With[{r = 8}, Flatten[Table[BellY[n, k, BellB[Range[0, r]]], {n, 0, r}, {k, 0, n}]]] (* _Jan Mangaldan_, May 22 2016 *)

%o (Sage)

%o # The functions below are referenced in various other sequences.

%o def bell_transform(n, a): # partition_based

%o row = []

%o fn = factorial(n)

%o for k in (0..n):

%o result = 0

%o for p in Partitions(n, length=k):

%o factorial_product = 1

%o power_factorial_product = 1

%o for part, count in p.to_exp_dict().items():

%o factorial_product *= factorial(count)

%o power_factorial_product *= factorial(part)**count

%o coefficient = fn//(factorial_product*power_factorial_product)

%o result += coefficient*prod([a[i-1] for i in p])

%o row.append(result)

%o return row

%o def bell_matrix(generator, dim):

%o G = [generator(k) for k in srange(dim)]

%o row = lambda n: bell_transform(n, G)

%o return matrix(ZZ, [row(n)+[0]*(dim-n-1) for n in srange(dim)])

%o def inverse_bell_matrix(generator, dim):

%o G = [generator(k) for k in srange(dim)]

%o row = lambda n: bell_transform(n, G)

%o M = matrix(ZZ, [row(n)+[0]*(dim-n-1) for n in srange(dim)]).inverse()

%o return matrix(ZZ, dim, lambda n,k: (-1)^(n-k)*M[n,k])

%o bell_numbers = [sum(bell_transform(n, [1]*10)) for n in range(11)]

%o for n in range(11): print(bell_transform(n, bell_numbers))

%o (PARI)

%o bell_matrix(f, len) = { my( m = matrix(len, len) ); m[1, 1] = 1;

%o for( n = 1, len-1, m[n+1, 2] = f(n-1) );

%o for( n = 0, len-1, for( k = 1, n,

%o 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]) ));

%o return( m )

%o }

%o f(n) = polcoeff( sum( k=0, n, prod( i=1, k, x / (1 - i*x)), x^n * O(x)), n);

%o bell_matrix(f, 9) \\ _Peter Luschny_, Jan 24 2016

%o (Python)

%o from functools import cache

%o from math import comb as binomial

%o def BellMatrix(f, size):

%o A = [f(n) for n in range(size - 1)]

%o @cache

%o def T(n, k):

%o if k == 0: return k ** n

%o return sum(

%o binomial(n - 1, j) * T(n - j - 1, k - 1) * A[j]

%o for j in range(n - k + 1) )

%o return [[T(n, k) for k in range(n + 1)] for n in range(size)]

%o @cache

%o def b(n, k=0): return n < 1 or k*b(n-1, k) + b(n-1, k+1)

%o print(BellMatrix(b, 9)) # _Peter Luschny_, Jun 14 2022

%Y Cf. A000012, A000110, A000217, A000914, A027801, A048993, A051836, A179455, A187761 (row sums), A264430, A264432, A265312.

%K nonn,tabl

%O 0,8

%A _Peter Luschny_, Nov 13 2015