A124302 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.

1, 1, 2, 5, 14, 41, 122, 365, 1094, 3281, 9842, 29525, 88574, 265721, 797162, 2391485, 7174454, 21523361, 64570082, 193710245, 581130734, 1743392201, 5230176602, 15690529805, 47071589414, 141214768241, 423644304722, 1270932914165, 3812798742494, 11438396227481

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.

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.

Giulio Cerbai, Anders Claesson, and Luca Ferrari, Stack sorting with restricted stacks, arXiv:1907.08142 [cs.DS], 2019.

S. Felsner and D. Heldt, Lattice Path Enumeration and Toeplitz Matrices, J. Int. Seq. 18 (2015) # 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.

M. Hyatt and J. 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. Jelinek, T. Mansour, and M. 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 (Corollary 3, case k=4, pages 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, Electronic Journal of Combinatorial Number Theory, Volume 15 #A16. (arXiv:1302.2274)

László Németh and László Szalay, Sequences Involving Square Zig-Zag Shapes, J. Int. Seq., Vol. 24 (2021), Article 21.5.2.

V. Retakh, S. Serconek, and R. 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.

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 (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]
Join[{1}, LinearRecurrence[{4, -3}, {1, 2}, 20]] (* David Nacin, Feb 26 2012 *)
CoefficientList[Series[1 / (1 - x / (1 - x / (1 - x / (1 - x)))), {x, 0, 30}], x] (* Vincenzo Librandi, Dec 25 2012 *)
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

Cf. A056272, A123183, A001519, A000110, A008277, A038754, A048328, A068911, A211216.

Essentially the same as A007051.

Sequence in context: A371427 A123183 A007051 * A341463 A088355 A113485

Adjacent sequences: A124299 A124300 A124301 * A124303 A124304 A124305

Keyword

nonn,easy

Author

Mike Zabrocki, Oct 25 2006

Status

approved