cp's OEIS Frontend

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.

%I A124303 #51 Mar 20 2022 02:37:29
%S A124303 1,1,2,5,15,51,187,715,2795,11051,43947,175275,700075,2798251,
%T A124303 11188907,44747435,178973355,715860651,2863377067,11453377195,
%U A124303 45813246635,183252462251,733008800427,2932033104555,11728128223915,46912504507051,187650001250987
%N 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.
%C A124303 Apart from initial term, same as A007581. - _Valery A. Liskovets_, Nov 16 2006
%H A124303 Colin Barker, <a href="/A124303/b124303.txt">Table of n, a(n) for n = 0..1000</a>
%H A124303 Joerg Arndt and N. J. A. Sloane, <a href="/A278984/a278984.txt">Counting Words that are in "Standard Order"</a>
%H A124303 N. Bergeron, C. Reutenauer, M. Rosas and M. Zabrocki, <a href="https://arxiv.org/abs/math/0502082">Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables</a>, arXiv:math/0502082 [math.CO], 2005; Canad. J. Math. 60 (2008), no. 2, 266-296.
%H A124303 M. Rosas and B. Sagan, <a href="http://dx.doi.org/10.1090/S0002-9947-04-03623-2">Symmetric Functions in Noncommuting Variables</a>, Transactions of the American Mathematical Society, 358 (2006), no. 1, 215-232.
%H A124303 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (7,-14,8).
%F A124303 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)).
%F A124303 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).
%F A124303 a(n) = (8 + 3*2^(1+n) + 4^n) / 24 for n>0. - _Colin Barker_, Nov 03 2017
%F A124303 a(n) = Sum_{k=0..4} Stirling2(n,k). - _Robert A. Russell_, Mar 29 2018
%F A124303 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
%F A124303 E.g.f.: (9 + 8*exp(x) + 6*exp(2*x) + exp(4*x))/24. - _Peter Luschny_, Nov 06 2018
%e A124303 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.
%p A124303 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:
%t A124303 Join[{1}, LinearRecurrence[{7, -14, 8}, {1, 2, 5}, 26]] (* _Jean-François Alcover_, Nov 20 2017 *)
%t A124303 Table[Sum[StirlingS2[n,k],{k,0,4}],{n,0,40}] (* _Robert A. Russell_, Mar 29 2018 *)
%o A124303 (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
%Y A124303 Cf. A124292, A000110, A008277.
%Y A124303 A row of the array in A278984.
%K A124303 nonn,easy
%O A124303 0,3
%A A124303 _Mike Zabrocki_, Oct 25 2006