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
Examples
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.
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).
Programs
-
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 *) -
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
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
Comments