OFFSET
0,3
COMMENTS
Row sums of triangle in A056241. - Philippe Deléham, Oct 30 2006
Row sums of triangle in A147746. - Philippe Deléham, Dec 04 2008
Hankel transform is := [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, ...]. - Philippe Deléham, Dec 04 2008
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
Number of Dyck paths of length 2n and height at most 4. - Ira M. Gessel, Aug 06 2012
REFERENCES
R. Stanley, Enumerative combinatorics, Vol. 1, Cambridge University Press, Cambridge, 1997, pp. 96-100.
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Per Alexandersson and Frether Getachew, An involution on derangements, arXiv:2105.08455 [math.CO], 2021.
Nantel Bergeron, Christophe Reutenauer, Mercedes Rosas, and Mike Zabrocki, Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables, arXiv:math/0502082 [math.CO], 2005. See also Canad. J. Math. 60(2) (2008), 266-296.
Giulio Cerbai, Anders Claesson, and Luca Ferrari, Stack sorting with restricted stacks, arXiv:1907.08142 [cs.DS], 2019.
Paul Drube, Raised k-Dyck paths, arXiv:2206.01194 [math.CO], 2022. See Appendix pp. 14-15.
Stefan Felsner and Daniel Heldt, Lattice Path Enumeration and Toeplitz Matrices, J. Int. Seq. 18 (2015), Art. 15.1.3.
Daniel Heldt, On the mixing time of the face flip-and up/down Markov chain for some families of graphs, Dissertation, Mathematik und Naturwissenschaften der Technischen Universitat Berlin zur Erlangung des akademischen Grades Doktor der Naturwissenschaften, 2016.
Matthew Hyatt and Jeffrey Remmel, The classification of 231-avoiding permutations by descents and maximum drop, arXiv preprint arXiv:1208.1052 [math.CO], 2012. - From N. J. A. Sloane, Dec 24 2012
Vít Jelínek, Toufik Mansour, and Mark Shattuck, On multiple pattern avoiding set partitions, Adv. Appl. Math. 50(2) (2013), 292-326, - From N. J. A. Sloane, Jan 01 2013
Sergey Kitaev, Jeffrey Remmel, and Mark Tiefenbruck, Marked mesh patterns in 132-avoiding permutations I, arXiv:1201.6243 [math.CO], 2012-2014. See Corollary 3, case k=4, pp. 10-11. - From N. J. A. Sloane, May 09 2012
Sergey Kitaev, Jeffrey Remmel, and Mark Tiefenbruck, Quadrant Marked Mesh Patterns in 132-Avoiding Permutations II, Integers 15 (2015), Art. A16. See also DOI link, arXiv:1302.2274.
László Németh and László Szalay, Sequences Involving Square Zig-Zag Shapes, J. Int. Seq. 24 (2021), Art. 21.5.2.
Vladimir Retakh, Shirlei Serconek, and Robert Wilson, Hilbert Series of Algebras Associated to Directed Graphs and Order Homology, arXiv:1010.6295 [math.RA], 2010-2011.
Santiago Rojas-Rojas, Camila Muñoz, Edgar Barriga, Pablo Solano, Aldo Delgado, and Carla Hermann-Avigliano, Analytic Evolution for Complex Coupled Tight-Binding Models: Applications to Quantum Light Manipulation, arXiv:2310.12366 [quant-ph], 2023. See p. 12.
Mercedes H. Rosas and Bruce E. Sagan, Symmetric Functions in Noncommuting Variables, Trans. Amer. Math. Soc. 358(1) (2006), 215-232.
Yi-Zhong Wang, Thermal Recurrence Orders of the Potts Model Partition Function in Grid Graphs, arXiv:2608.21789 [cs.DM], 2026. See p. 21. [The paper is likely incorrect. - Andrei Zabolotskii, Aug 30 2026]
Index entries for linear recurrences with constant coefficients, signature (4,-3).
FORMULA
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)).
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).
Inverse binomial transform of A007581. - Philippe Deléham, Oct 30 2006
a(n) = Sum_{k=0..n} A056241(n,k), n >= 1. - Philippe Deléham, Oct 30 2006
a(0) = 1, a(n) = (3^(n-1) + 1)/2 for n >= 1, see A007051. - Philippe Deléham, Oct 30 2006
E.g.f.: (2 + 3*exp(x) + exp(3x))/6.
G.f.: 1 / (1 - x / (1 - x / (1 - x / (1 - x)))). - Michael Somos, May 03 2012
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
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
a(n) = Sum_{k=0..3} 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=3. - Robert A. Russell, Apr 25 2018
EXAMPLE
There are 15 set partitions of {1,2,3,4}, only {{1},{2},{3},{4}} has more than 3 blocks, so a(4) = 14.
G.f. = 1 + x + 2*x^2 + 5*x^3 + 14*x^4 + 41*x^5 + 122*x^6 + 365*x^7 + ...
MAPLE
a:= proc(n); if n<3 then [1, 1, 2][n+1]; else 4*a(n-1)-3*a(n-2); fi; end:
# Mike Zabrocki, Oct 25 2006
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);
# Johannes W. Meijer, May 29 2010
MATHEMATICA
a=Exp[x]-1; Range[0, 20]! CoefficientList[Series[1+a+a^2/2+a^3/6, {x, 0, 20}], x]
(* Alternative: *)
Join[{1}, LinearRecurrence[{4, -3}, {1, 2}, 20]] (* David Nacin, Feb 26 2012 *)
(* Alternative: *)
CoefficientList[Series[1 / (1 - x / (1 - x / (1 - x / (1 - x)))), {x, 0, 30}], x] (* Vincenzo Librandi, Dec 25 2012 *)
(* Alternative: *)
Table[Sum[StirlingS2[n, k], {k, 0, 3}], {n, 0, 30}] (* Robert A. Russell, Mar 29 2018 *)
PROG
(Python)
def a(n, adict={0:1, 1:1, 2:2}):
if n in adict:
return adict[n]
adict[n]=4*a(n-1) - 3*a(n-2)
return adict[n] # David Nacin, Mar 04 2012
(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
(PARI) {a(n) = if( n<1, n==0, (3^(n-1) + 1) / 2)}; /* Michael Somos, Apr 03 2014 */
CROSSREFS
KEYWORD
nonn,easy,changed
AUTHOR
Mike Zabrocki, Oct 25 2006
STATUS
approved
