A123183 -id:A123183 - cp's OEIS frontend

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

Mike Zabrocki, Oct 25 2006

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

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

R. Stanley, Enumerative combinatorics, Vol. 1, Cambridge University Press, Cambridge, 1997, pp. 96-100.

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

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

Essentially the same as A007051.

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

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

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 *)

{a(n) = if( n<1, n==0, (3^(n-1) + 1) / 2)}; /* Michael Somos, Apr 03 2014 */

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

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

A080937 Number of Catalan paths (nonnegative, starting and ending at 0, step +/-1) of 2*n steps with all values <= 5.

Original entry on oeis.org

1, 1, 2, 5, 14, 42, 131, 417, 1341, 4334, 14041, 45542, 147798, 479779, 1557649, 5057369, 16420730, 53317085, 173118414, 562110290, 1825158051, 5926246929, 19242396629, 62479659622, 202870165265, 658715265222, 2138834994142, 6944753544643, 22549473023585

Offset: 0

Henry Bottomley, Feb 25 2003

With interpolated zeros (1,0,1,0,2,...), counts closed walks of length n at start or end node of P_6. The sequence (0,1,0,2,...) counts walks of length n between the start and second node. - Paul Barry, Jan 26 2005
HANKEL transform of sequence and the sequence omitting a(0) is the sequence A130716. This is the unique sequence with that property. - Michael Somos, May 04 2012
From Wolfdieter Lang, Mar 30 2020: (Start)
a(n) is also the upper left entry of the n-th power of the 3 X 3 tridiagonal matrix M_3 = Matrix([1,1,0], [1,2,1], [0,1,2]) from A332602: a(n) = ((M_3)^n)[1,1].
Proof: (M_3)^n = b(n-2)*(M_3)^2 - (6*b(n-3) - b(n-4))*M_3 + b(n-3)*1_3, for n >= 0, with b(n) = A005021(n), for n >= -4. For the proof of this see a comment in A005021. Hence (M_3)^n[1,1] = 2*b(n-2) - 5*b(n-3) + b(n-4), for n >= 0. This proves the 3 X 3 part of the conjecture in A332602 by Gary W. Adamson.
The formula for a(n) given below in terms of r = rho(7) = A160389 proves that a(n)/a(n-1) converges to rho(7)^2 = A116425 = 3.2469796..., because r - 2/r = 0.6920... < 1, and r^2 - 3 = 0.2469... < 1. This limit was conjectured in A332602 by Gary W. Adamson.
(End)

			G.f. = 1 + x + 2*x^2 + 5*x^3 + 14*x^4 + 42*x^5 + 131*x^6 + 417*x^7 + 1341*x^8 + ...

Alois P. Heinz, Table of n, a(n) for n = 0..600
Jean Luc Baril, Rigoberto Flórez, and José L. Ramirez, Generalized Narayana arrays, restricted Dyck paths, and related bijections, Univ. Bourgogne (France, 2025). See p. 27.
Jean-Luc Baril, Toufik Mansour, José L. Ramírez, and Mark Shattuck, Catalan words avoiding a pattern of length four, Univ. de Bourgogne (France, 2024). See p. 3.
Jean-Luc Baril and Helmut Prodinger, Enumeration of partial Lukasiewicz paths, arXiv:2205.01383 [math.CO], 2022.
Paul Barry, Centered polygon numbers, heptagons and nonagons, and the Robbins numbers, arXiv:2104.01644 [math.CO], 2021.
Giulio Cerbai, Anders Claesson, and Luca Ferrari, Stack sorting with restricted stacks, arXiv:1907.08142 [cs.DS], 2019.
Wei Chen, Enumeration of Set Partitions Refined by Crossing and Nesting Numbers, MS Thesis, Department of Mathematics. Simon Fraser University, Fall 2014. Table 4.1, line k=2.
Johann Cigler, Number of bounded Dyck paths with "negative length", MathOverflow question, Sep 26 2020.
Michael Dairyko, Lara Pudwell, Samantha Tyner, and Casey Wynn, Non-contiguous pattern avoidance in binary trees, Electron. J. Combin. 19 (2012), no. 3, Paper 22, 21 pp. MR2967227.
Nachum Dershowitz, Between Broadway and the Hudson: A Bijection of Corridor Paths, arXiv:2006.06516 [math.CO], 2020.
Paul Duncan and Einar Steingrimsson, Pattern avoidance in ascent sequences, arXiv preprint arXiv:1109.3641 [math.CO], 2011.
Sergi Elizalde, Symmetric peaks and symmetric valleys in Dyck paths, arXiv:2008.05669 [math.CO], 2020.
Stefan Felsner and Daniel 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.
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
Aleksandar Ilic and Andreja Ilic, On the number of restricted Dyck paths, Filomat 25:3 (2011), 191-201; DOI: 10.2298/FIL1103191I.
Sergey Kitaev, Jeffrey Remmel and Mark Tiefenbruck, Marked mesh patterns in 132-avoiding permutations I, arXiv:1201.6243v1 [math.CO], 2012 (Corollary 3, case k=5, pages 10-11). - From _N. J. A. Sloane_, May 09 2012
Erkko Lehtonen and Tamás Waldhauser, Associative spectra of graph algebras I. Foundations, undirected graphs, antiassociative graphs, arXiv:2011.07621 [math.CO], 2020. See also J. of Algebraic Combinatorics (2021) Vol. 53, 613-638.
Toufik Mansour and Mark Shattuck, Some enumerative results related to ascent sequences, arXiv preprint arXiv:1207.3755 [math.CO], 2012. - From _N. J. A. Sloane_, Dec 22 2012
Sophie Morier-Genoud, Valentin Ovsienko, and Serge Tabachnikov, 2-frieze patterns and the cluster structure of the space of polygons, arXiv:1008.3359 [math.AG], 2010-2011. - From _N. J. A. Sloane_, Dec 26 2012
Sophie Morier-Genoud, Valentin Ovsienko, and Serge Tabachnikov, 2-frieze patterns and the cluster structure of the space of polygons, Annales de l'institut Fourier, 62 no. 3 (2012), 937-987. - From _N. J. A. Sloane_, Dec 26 2012
David Nečas and Ivan Ohlídal, Consolidated series for efficient calculation of the reflection and transmission in rough multilayers, Optics Express, Vol. 22, 2014, No. 4; DOI:10.1364/OE.22.004499.
László Németh and László Szalay, Sequences Involving Square Zig-Zag Shapes, J. Int. Seq., Vol. 24 (2021), Article 21.5.2.
Lara Pudwell, Pattern avoidance in trees, slides from a talk, mentions many sequences, 2012. - From _N. J. A. Sloane_, Jan 03 2013
Lara Pudwell and Andrew Baxter, Ascent sequences avoiding pairs of patterns, 2014.
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.
Index entries for linear recurrences with constant coefficients, signature (5,-6,1).

Cf. A000007, A000012, A001519, A007051, A011782, A024175, A080937, A080938.
Cf. A033191 which essentially provide the same sequence for different limits and tend to A000108.
Cf. A005021, A094790, A094789.
Cf. A211216, A005021, A160389, A116425, A332602.

I:=[1,1,2]; [n le 3 select I[n] else 5*Self(n-1)-6*Self(n-2)+Self(n-3): n in [1..30]]; // Vincenzo Librandi, Jan 09 2016

a:= n-> (<<0|1|0>, <0|0|1>, <1|-6|5>>^n. <<1, 1, 2>>)[1, 1]:
seq(a(n), n=0..35);  # Alois P. Heinz, Nov 09 2012

nn=56;Select[CoefficientList[Series[(1-4x^2+3x^4)/(1-5x^2+6x^4-x^6), {x,0,nn}], x],#>0 &] (* Geoffrey Critzer, Jan 26 2014 *)
LinearRecurrence[{5,-6,1},{1,1,2},30] (* Jean-François Alcover, Jan 09 2016 *)

a=vector(99); a[1]=1; a[2]=2;a[3]=5; for(n=4,#a,a[n]=5*a[n-1]-6*a[n-2] +a[n-3]); a \\ Charles R Greathouse IV, Jun 10 2011

{a(n) = if( n<0, n = -n; polcoeff( (1 - 3*x + x^2) / (1 - 6*x + 5*x^2 - x^3) + x * O(x^n), n), polcoeff( (1 - 4*x + 3*x^2) / (1 - 5*x + 6*x^2 - x^3) + x * O(x^n), n))} /* Michael Somos, May 04 2012 */

a(n) = A080934(n,5).
G.f.: (1-4*x+3*x^2)/(1-5*x+6*x^2-x^3). - Ralf Stephan, May 13 2003
a(n) = 5*a(n-1) - 6*a(n-2) + a(n-3). - Herbert Kociemba, Jun 11 2004
a(n) = A096976(2*n). - Floor van Lamoen, Nov 02 2005
a(n) = (4/7-4/7*cos(1/7*Pi)^2)*(4*(cos(Pi/7))^2)^n + (1/7-2/7*cos(1/7*Pi) + 4/7*cos(1/7*Pi)^2)*(4*(cos(2*Pi/7))^2)^n + (2/7+2/7*cos(1/7*Pi))*(4*(cos(3*Pi/7))^2)^n for n>=0. - Richard Choulet, Apr 19 2010
G.f.: 1 / (1 - x / (1 - x / (1 - x / (1 - x / (1 - x))))). - Michael Somos, May 04 2012
a(-n) = A038213(n). a(n + 2) * a(n) - a(n + 1)^2 = a(1 - n). Convolution inverse is A123183 with A123183(0)=1. - Michael Somos, May 04 2012
From Wolfdieter Lang, Mar 30 2020: (Start)
In terms of the algebraic number r = rho(7) = A160389 of degree 3 the formula given by Richard Choulet becomes a(n) = (1/7)*(r)^(2*n)*(C1(r) + C2(r)*(r - 2/r)^(2*n) + C3(r)*(r^2 - 3)^(2*n)), with C1(r) = 4 - r^2, C2(r) = 1 - r + r^2, and C3 = 2 + r.
a(n) = ((M_3)^n)[1,1] = 2*b(n-2) - 5*b(n-3) + b(n-4), for n >= 0, with the 3 X 3 tridiagonal matrix M_3 = Matrix([1,1,0], [1,2,1], [0,1,2]) from A332602, and b(n) = A005021(n) (with offset n >= -4). (End)

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

A080937 Number of Catalan paths (nonnegative, starting and ending at 0, step +/-1) of 2*n steps with all values <= 5.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Formula