A124303 Number of set partitions of length <= 4; sum of first 4 columns of triangle of Stirling numbers of 2nd kind; dimension of space of symmetric polynomials in 4 noncommuting variables.

1, 1, 2, 5, 15, 51, 187, 715, 2795, 11051, 43947, 175275, 700075, 2798251, 11188907, 44747435, 178973355, 715860651, 2863377067, 11453377195, 45813246635, 183252462251, 733008800427, 2932033104555, 11728128223915, 46912504507051, 187650001250987

Offset

0,3

Comments

Apart from initial term, same as A007581. - Valery A. Liskovets, Nov 16 2006

Links

Colin Barker, Table of n, a(n) for n = 0..1000

Joerg Arndt and N. J. A. Sloane, Counting Words that are in "Standard Order"

N. Bergeron, C. Reutenauer, M. Rosas and M. Zabrocki, Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables, arXiv:math/0502082 [math.CO], 2005; Canad. J. Math. 60 (2008), no. 2, 266-296.

M. Rosas and B. Sagan, Symmetric Functions in Noncommuting Variables, Transactions of the American Mathematical Society, 358 (2006), no. 1, 215-232.

Index entries for linear recurrences with constant coefficients, signature (7,-14,8).

Formula

O.g.f.: (3*q^3 - 9*q^2 + 6*q - 1)/(8*q^3 - 14*q^2 + 7*q - 1) = Sum_{k=0..4} (q^k/Product_{i=1..k} (1-i*q)).

a(n) = 7*a(n-1) - 14*a(n-2) + 8*a(n-3); a(0) = 1, a(1) = 1, a(2) = 2, a(3) = 5, a(n) = Sum_{k=1..4} A008277(n,k).

a(n) = (8 + 3*2^(1+n) + 4^n) / 24 for n>0. - Colin Barker, Nov 03 2017

a(n) = Sum_{k=0..4} Stirling2(n,k). - Robert A. Russell, Mar 29 2018

G.f.: Sum_{j=0..k} A248925(k,j)*x^j / Product_{j=1..k} 1-j*x with k=4. - Robert A. Russell, Apr 25 2018

E.g.f.: (9 + 8*exp(x) + 6*exp(2*x) + exp(4*x))/24. - Peter Luschny, Nov 06 2018

Example

Number of set partitions of {1,2,3,4,5,6} are given by A008277(6,k) = 1, 31, 90, 65, 15, 1 and hence a(6) = 1+31+90+65 = 187.

Maple

a:=proc(n); if n<4 then [1, 1, 2, 5][n+1]; else 7*a(n-1)-14*a(n-2)+8*a(n-3); fi; end:

Mathematica

Join[{1}, LinearRecurrence[{7, -14, 8}, {1, 2, 5}, 26]] (* Jean-François Alcover, Nov 20 2017 *)
Table[Sum[StirlingS2[n, k], {k, 0, 4}], {n, 0, 40}] (* Robert A. Russell, Mar 29 2018 *)

Prog

(PARI) Vec((1 - 6*x + 9*x^2 - 3*x^3) / ((1 - x)*(1 - 2*x)*(1 - 4*x)) + O(x^30)) \\ Colin Barker, Nov 03 2017

Crossrefs

Cf. A124292, A000110, A008277.

A row of the array in A278984.

Sequence in context: A149954 A149955 A007581 * A367414 A073525 A369481

Adjacent sequences: A124300 A124301 A124302 * A124304 A124305 A124306

Keyword

nonn,easy

Author

Mike Zabrocki, Oct 25 2006

Status

approved