%I #133 Oct 25 2023 09:30:56
%S 1,1,2,5,14,41,122,365,1094,3281,9842,29525,88574,265721,797162,
%T 2391485,7174454,21523361,64570082,193710245,581130734,1743392201,
%U 5230176602,15690529805,47071589414,141214768241,423644304722,1270932914165,3812798742494,11438396227481
%N Number of set partitions with at most 3 blocks; number of Dyck paths of height at most 4; dimension of space of symmetric polynomials in 3 noncommuting variables.
%C Row sums of triangle in A056241. - _Philippe Deléham_, Oct 30 2006
%C Row sums of triangle in A147746. - _Philippe Deléham_, Dec 04 2008
%C Hankel transform is := [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, ...]. - _Philippe Deléham_, Dec 04 2008
%C Number of nonisomorphic graded posets with 0 and 1 and uniform Hasse graph of rank n with no 3-element antichain. (Uniform used in the sense of Retakh, Serconek and Wilson. Graded used in Stanley's sense that every maximal chain has the same length n.) - _David Nacin_, Feb 26 2012
%C Number of Dyck paths of length 2n and height at most 4. - _Ira M. Gessel_, Aug 06 2012
%D R. Stanley, Enumerative combinatorics, Vol. 1, Cambridge University Press, Cambridge, 1997, pp. 96-100.
%H Vincenzo Librandi, <a href="/A124302/b124302.txt">Table of n, a(n) for n = 0..1000</a>
%H Per Alexandersson and Frether Getachew, <a href="https://arxiv.org/abs/2105.08455">An involution on derangements</a>, arXiv:2105.08455 [math.CO], 2021.
%H 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 Giulio Cerbai, Anders Claesson, and Luca Ferrari, <a href="https://arxiv.org/abs/1907.08142">Stack sorting with restricted stacks</a>, arXiv:1907.08142 [cs.DS], 2019.
%H S. Felsner and D. Heldt, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Felsner/felsner2.html">Lattice Path Enumeration and Toeplitz Matrices</a>, J. Int. Seq. 18 (2015) # 15.1.3.
%H Daniel Heldt, <a href="https://depositonce.tu-berlin.de/bitstream/11303/5553/5/heldt_daniel.pdf">On the mixing time of the face flip-and up/down Markov chain for some families of graphs</a>, Dissertation, Mathematik und Naturwissenschaften der Technischen Universitat Berlin zur Erlangung des akademischen Grades Doktor der Naturwissenschaften, 2016.
%H M. Hyatt and J. Remmel, <a href="https://arxiv.org/abs/1208.1052">The classification of 231-avoiding permutations by descents and maximum drop</a>, arXiv preprint arXiv:1208.1052 [math.CO], 2012. - From _N. J. A. Sloane_, Dec 24 2012
%H V. Jelinek, T. Mansour, and M. Shattuck, <a href="http://dx.doi.org/10.1016/j.aam.2012.09.002">On multiple pattern avoiding set partitions</a>, Adv. Appl. Math. 50 (2) (2013) 292-326, - From _N. J. A. Sloane_, Jan 01 2013
%H Sergey Kitaev, Jeffrey Remmel and Mark Tiefenbruck, <a href="https://arxiv.org/abs/1201.6243">Marked mesh patterns in 132-avoiding permutations I,</a> arXiv:1201.6243 [math.CO], 2012-2014 (Corollary 3, case k=4, pages 10-11). - From _N. J. A. Sloane_, May 09 2012
%H Sergey Kitaev, Jeffrey Remmel, and Mark Tiefenbruck, <a href="http://www.emis.de/journals/INTEGERS/papers/p16/p16.Abstract.html">Quadrant Marked Mesh Patterns in 132-Avoiding Permutations II</a>, Electronic Journal of Combinatorial Number Theory, Volume 15 #A16. (<a href="http://arxiv.org/abs/1302.2274">arXiv:1302.2274</a>)
%H László Németh and László Szalay, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL24/Nemeth/nemeth8.html">Sequences Involving Square Zig-Zag Shapes</a>, J. Int. Seq., Vol. 24 (2021), Article 21.5.2.
%H V. Retakh, S. Serconek, and R. Wilson, <a href="https://arxiv.org/abs/1010.6295">Hilbert Series of Algebras Associated to Directed Graphs and Order Homology</a>, arXiv:1010.6295 [math.RA], 2010-2011.
%H Santiago Rojas-Rojas, Camila Muñoz, Edgar Barriga, Pablo Solano, Aldo Delgado, and Carla Hermann-Avigliano, <a href="https://arxiv.org/abs/2310.12366">Analytic Evolution for Complex Coupled Tight-Binding Models: Applications to Quantum Light Manipulation</a>, arXiv:2310.12366 [quant-ph], 2023. See p. 12.
%H 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 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (4,-3).
%F O.g.f.: (q^2 - 3*q + 1)/(3*q^2 - 4*q + 1) = Sum_{k=0..3} (q^k/Product_{i=1..k} (1-i*q)).
%F a(n) = 4*a(n-1) - 3*a(n-2); a(0) = 1, a(1) = 1, a(2) = 2, a(n) = Sum_{k=1..3} A008277(n,k).
%F Inverse binomial transform of A007581. - _Philippe Deléham_, Oct 30 2006
%F a(n) = Sum_{k=0..n} A056241(n,k), n >= 1. - _Philippe Deléham_, Oct 30 2006
%F a(0) = 1, a(n) = (3^(n-1) + 1)/2 for n >= 1, see A007051. - _Philippe Deléham_, Oct 30 2006
%F E.g.f.: (2 + 3*exp(x) + exp(3x))/6.
%F G.f.: 1 / (1 - x / (1 - x / (1 - x / (1 - x)))). - _Michael Somos_, May 03 2012
%F G.f.: 1 + x + 3*x^2*U(0)/2 where U(k) = 1 + 2/(3*3^k + 3*3^k/(1 - 18*x*3^k/ (9*x*3^k - 1/U(k+1)))); (continued fraction, 4-step). - _Sergei N. Gladkovskii_, Nov 01 2012
%F G.f.: 1+x*G(0) where G(k) = 1 + 2*x/( 1-2*x - x*(1-2*x)/(x + (1-2*x)*2/G(k+1) )); (recursively defined continued fraction). - _Sergei N. Gladkovskii_, Dec 10 2012
%F a(n) = Sum_{k=0..3} Stirling2(n,k). - _Robert A. Russell_, Mar 29 2018
%F G.f.: Sum_{j=0..k} A248925(k,j)*x^j / Product_{j=1..k} 1-j*x with k=3. - _Robert A. Russell_, Apr 25 2018
%e There are 15 set partitions of {1,2,3,4}, only {{1},{2},{3},{4}} has more than 3 blocks, so a(4) = 14.
%e G.f. = 1 + x + 2*x^2 + 5*x^3 + 14*x^4 + 41*x^5 + 122*x^6 + 365*x^7 + ...
%p a:= proc(n); if n<3 then [1,1,2][n+1]; else 4*a(n-1)-3*a(n-2); fi; end:
%p # _Mike Zabrocki_, Oct 25 2006
%p with(GraphTheory): G:=PathGraph(5): A:= AdjacencyMatrix(G): nmax:=27; for n from 0 to 2*nmax do B(n):=A^n; b(n):=B(n)[1,1]; od: for n from 0 to nmax do a(n):=b(2*n) od: seq(a(n),n=0..nmax);
%p # _Johannes W. Meijer_, May 29 2010
%t a=Exp[x]-1; Range[0, 20]! CoefficientList[Series[1+a+a^2/2+a^3/6, {x,0,20}],x]
%t Join[{1}, LinearRecurrence[{4, -3}, {1, 2}, 20]] (* _David Nacin_, Feb 26 2012 *)
%t CoefficientList[Series[1 / (1 - x / (1 - x / (1 - x / (1 - x)))), {x, 0, 30}], x] (* _Vincenzo Librandi_, Dec 25 2012 *)
%t Table[Sum[StirlingS2[n,k],{k,0,3}],{n,0,30}] (* _Robert A. Russell_, Mar 29 2018 *)
%o (Python)
%o def a(n, adict={0:1, 1:1, 2:2}):
%o if n in adict:
%o return adict[n]
%o adict[n]=4*a(n-1) - 3*a(n-2)
%o return adict[n] # _David Nacin_, Mar 04 2012
%o (Magma) I:=[1, 1, 2]; [n le 3 select I[n] else 4*Self(n-1) - 3*Self(n-2): n in [1..30]]; // _Vincenzo Librandi_, Dec 25 2012
%o (PARI) {a(n) = if( n<1, n==0, (3^(n-1) + 1) / 2)}; /* _Michael Somos_, Apr 03 2014 */
%Y Cf. A056272, A123183, A001519, A000110, A008277, A038754, A048328, A068911, A211216.
%Y Essentially the same as A007051.
%K nonn,easy
%O 0,3
%A _Mike Zabrocki_, Oct 25 2006