%I M4722 N2018 #89 Feb 22 2023 18:32:11
%S 1,10,65,350,1701,7770,34105,145750,611501,2532530,10391745,42355950,
%T 171798901,694337290,2798806985,11259666950,45232115901,181509070050,
%U 727778623825,2916342574750,11681056634501,46771289738810,187226356946265,749329038535350
%N Stirling numbers of the second kind, S(n,4).
%C Given a set {1,2,3,4}, a(n) is the number of occurrences where the first 2 comes after the first '1', the first '3' after the first '2' and the first '4' after the first '3' in a list of n+3. For example, a(1): 1234; a(2): 11234, 12134, 12314, 12341, 12234, 12324, 12342, 12334, 12343, 12344. Related to the cereal box problem. - _Kevin Nowaczyk_, Aug 02 2007
%C a(n) is the number of partitions of [n] into 4 nonempty subsets. - _Enrique Navarrete_, Aug 27 2021
%D M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 835.
%D F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 223.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A000453/b000453.txt">Table of n, a(n) for n = 4..200</a>
%H M. Abramowitz and I. A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
%H J. Brandts and C. Cihangir, <a href="http://am2013.math.cas.cz/proceedings/contributions/brandts.pdf">Counting triangles that share their vertices with the unit n-cube</a>, in Conference Applications of Mathematics 2013 in honor of the 70th birthday of Karel Segeth. Jan Brandts, Sergey Korotov, et al., eds., Institute of Mathematics AS CR, Prague 2013.
%H Eldar Fischer, Johann A. Makowsky, and Vsevolod Rakita, <a href="https://arxiv.org/abs/2302.08265">MC-finiteness of restricted set partition functions</a>, arXiv:2302.08265 [math.CO], 2023.
%H M. Griffiths and I. Mezo, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Griffiths/griffiths11.html">A generalization of Stirling Numbers of the Second Kind via a special multiset</a>, JIS 13 (2010) #10.2.5.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=347">Encyclopedia of Combinatorial Structures 347</a>
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992.
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (10,-35,50,-24).
%F G.f.: x^4/((1-x)*(1-2*x)*(1-3*x)*(1-4*x)).
%F E.g.f.: (exp(x)-1)^4/4!.
%F a(n) = (4^n - 4*3^n + 6*2^n - 4)/24. - _Kevin Nowaczyk_, Aug 02 2007
%F a(n) = det(|s(i+4,j+3)|, 1 <= i,j <= n-4), where s(n,k) are Stirling numbers of the first kind. - _Mircea Merca_, Apr 06 2013
%F a(n) = 10*a(n-1) - 35*a(n-2) + 50*a(n-3) - 24*a(n-4). - _Wesley Ivan Hurt_, Oct 10 2021
%p A000453:=1/(z-1)/(3*z-1)/(2*z-1)/(4*z-1); # conjectured by _Simon Plouffe_ in his 1992 dissertation
%t t={}; Do[f=StirlingS2[n, 4]; AppendTo[t, f], {n, 120}]; t (* _Vladimir Joseph Stephan Orlovsky_, Sep 27 2008 *)
%t CoefficientList[Series[1/((1 - x) (1 - 2 x) (1 - 3 x) (1 - 4 x)), {x, 0, 25}], x] (* _Vladimir Joseph Stephan Orlovsky_, Jun 20 2011 *)
%t LinearRecurrence[{10, -35, 50, -24}, {1, 10, 65, 350}, 100] (* _Vladimir Joseph Stephan Orlovsky_, Feb 23 2012 *)
%o (PARI) a(n)=(4^n-4*3^n+6*2^n-4)/24 \\ _Charles R Greathouse IV_, Sep 24 2015
%Y Cf. A008277 (Stirling2 triangle), A016269, A056280 (Mobius transform).
%K nonn,easy
%O 4,2
%A _N. J. A. Sloane_