A143815 Let A(0)=1, B(0)=0 and C(0)=0. Let B(n+1) = Sum_{k = 0..n} binomial(n,k)*A(k), C(n+1) = Sum_{k = 0..n} binomial(n,k)*B(k) and A(n+1) = Sum_{k = 0..n} binomial(n,k)*C(k). This entry gives the sequence A(n).

1, 0, 0, 1, 6, 25, 91, 322, 1232, 5672, 32202, 209143, 1432454, 9942517, 69363840, 490303335, 3565609732, 27118060170, 218183781871, 1861370544934, 16729411124821, 156706028787827, 1514442896327792, 14999698898942772, 151838974745743228, 1571513300578303070

Offset: 0

Author

Peter Bala, Sep 03 2008

Keywords

• easy
• nonn

Comments

Compare with A024429 and A024430.

This sequence and its companion sequences B(n) = A143816(n) and C(n) = A143817(n) may be viewed as generalizations of the Bell numbers A000110. Define a sequence R(n) of real numbers by R(n) = Sum_{k >= 0} (3*k)^n/(3*k)! for n = 0, 1, 2, .... It is easy to verify that this sequence satisfies the recurrence relation u(n+3) = 3*u(n+2) - 2*u(n+1) + Sum_{i = 0..n} binomial(n, i)*3^(n-i)*u(i). Hence R(n) is an integral linear combination of R(0), R(1) and R(2). Some examples are given below.

To find the precise form of the linear relation define two other sequences of real numbers by S(n) = Sum_{k >= 0} (3*k+1)^n/(3*k+1)! and T(n) = Sum_{k >= 0} (3*k+2)^n/(3*k+2)! for n = 0, 1, 2, .... Both S(n) and T(n) satisfy the above recurrence. Then by means of the identities S(n+1) = Sum_{i = 0..n} binomial(n, i)*R(i), T(n+1) = Sum_{i = 0..n} binomial(n, i)*S(i) and R(n+1) = Sum_{i = 0..n} binomial(n, i)*T(i) we obtain the result R(n) = A(n)*R(0) + (B(n) - C(n))*R(1) + C(n)*R(2) = A(n)*R(0) + B(n)*R(1) + C(n)*(R(2) - R(1)) (with corresponding expressions for S(n) and T(n)). This generalizes the Dobinski's relation for the Bell numbers Sum_{k >= 0} k^n/k! = A000110(n)*exp(1).

Some examples of R(n) as a linear combination of R(0), R(1) and R(2) - R(1) are given below. The decimal expansions of R(0) = 1 + 1/3! + 1/6! + 1/9! + ..., R(2) - R(1) = 1/1! + 1/4! + 1/7! + ... and R(1) = 1/2! + 1/5! + 1/8! + ... may be found in A143819, A143820 and A143821 respectively. Compare with A143628 through A143631.

For n > 0, the number of partitions of {1,2,...,n} into 3,6,9,... classes. - Geoffrey Critzer, Mar 05 2010

Examples

			R(n) as a linear combination of R(i), i = 0..2.
  ==================================
  R(n)  |     R(0)    R(1)    R(2)
  ==================================
  R(3)  |       1      -2       3
  R(4)  |       6      -5       7
  R(5)  |      25      -5      16
  R(6)  |      91      20      46
  R(7)  |     322     149     203
  R(8)  |    1232     552    1178
  R(9)  |    5672     991    7242
  R(10) |   32202   -3799   43786
  ...
Column 2 of the above table is A143818.
R(n) as a linear combination of R(0),R(1) and R(2) - R(1).
  =====================================
  R(n)  |     R(0)     R(1)   R(2)-R(1)
  =====================================
  R(3)  |       1        1        3
  R(4)  |       6        2        7
  R(5)  |      25       11       16
  R(6)  |      91       66       46
  R(7)  |     322      352      203
  R(8)  |    1232     1730     1178
  R(9)  |    5672     8233     7242
  R(10) |   32202    39987    43786
  ...
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..576
• Eric Weisstein's World of Mathematics, Bell Polynomial.

Crossrefs

Cf. A000110, A024429, A024430, A143628, A143629, A143630, A143631, A143816, A143817, A143818, A143819, A143820, A143821.

Programs

Maple

# (1)
M:=24: a:=array(0..100): b:=array(0..100): c:=array(0..100):
a[0]:=1: b[0]:=0: c[0]:=0:
for n from 1 to M do
b[n]:=add(binomial(n-1,k)*a[k], k=0..n-1);
c[n]:=add(binomial(n-1,k)*b[k], k=0..n-1);
a[n]:=add(binomial(n-1,k)*c[k], k=0..n-1);
end do:
A143815:=[seq(a[n], n=0..M)];
# (2)
seq(add(Stirling2(n,3*i),i = 0..floor(n/3)), n = 0..24);
# third Maple program:
b:= proc(n, t) option remember; `if`(n=0, irem(t, 2),
      add(b(n-j, irem(t+1, 3))*binomial(n-1, j-1), j=1..n))
    end:
a:= n-> b(n, 1):
seq(a(n), n=0..25);  # Alois P. Heinz, Feb 20 2018

Mathematica

a = Exp[x] - 1; f[x_] := 1/3 (E^x + 2 E^(-x/2) Cos[(Sqrt[3] x)/2]); CoefficientList[Series[f[a], {x, 0, 25}], x]*Table[n!, {n, 0, 25}] (* Geoffrey Critzer, Mar 05 2010 *)

PARI

Bell_poly(n, x) = exp(-x)*suminf(k=0, k^n*x^k/k!);
a(n) = my(w=(-1+sqrt(3)*I)/2); round(Bell_poly(n, 1)+Bell_poly(n, w)+Bell_poly(n, w^2))/3; \\ Seiichi Manyama, Oct 13 2022

Formula

a(n) = Sum_{k = 0..floor(n/3)} Stirling2(n, 3*k).

Let w = exp(2*Pi*i/3) and set F(x) = (exp(x) + exp(w*x) + exp(w^2*x))/3 = 1 + x^3/3! + x^6/6! + ... . Then the e.g.f. for the sequence is F(exp(x) - 1).

A143815(n) + A143816(n) + A143817(n) = Bell(n).

E.g.f. is B(A(x)) where A(x) = exp(x) - 1 and B(x) = (1/3)*(exp(x) + 2*exp(-x/2)*cos(sqrt(3)*x/2)). - Geoffrey Critzer, Mar 05 2010

a(n) = ( Bell_n(1) + Bell_n(w) + Bell_n(w^2) )/3, where Bell_n(x) is n-th Bell polynomial and w = exp(2*Pi*i/3). - Seiichi Manyama, Oct 13 2022

a(n) ~ n^n / (3 * (LambertW(n))^n * exp(n+1-n/LambertW(n)) * sqrt(1+LambertW(n))). - Vaclav Kotesovec, Jun 10 2025