login
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.
11
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
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.
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
A row of the array in A278984.
Sequence in context: A149955 A374553 A007581 * A367414 A073525 A369481
KEYWORD
nonn,easy
AUTHOR
Mike Zabrocki, Oct 25 2006
STATUS
approved