A224747 -id:A224747 - cp's OEIS frontend

A054391 Number of permutations with certain forbidden subsequences.

1, 1, 2, 5, 14, 41, 123, 374, 1147, 3538, 10958, 34042, 105997, 330632, 1032781, 3229714, 10109310, 31667245, 99260192, 311294876, 976709394, 3065676758, 9625674442, 30231524869, 94972205349, 298419158008, 937861780439, 2947969125284, 9267666915326

Offset: 0

N. J. A. Sloane, Elisa Pergola (elisa(AT)dsi.unifi.it), May 21 2000

nonn

Hankel transform is [1,1,1,...] = A000012. - Paul Barry, Jan 19 2009
The inverse Motzkin transform apparently yields 1 followed by A000930, which implies a generating function g(x)=1+z/(1-z-z^3) where z=x*A001006(x). - R. J. Mathar, Jul 07 2009
It appears that the infinite set of interpolated sequences between the Motzkin and the Catalan can be generated with a succession of INVERT transforms, given each sequence has two leading 1's. Also, the N-th sequence in the set starting with (N=1, A001006) can be generated from a production matrix of the form "M" in the formula section, such that the main diagonal is (N leading 1's, 0, 0, 0, ...). M with a diagonal of (1, 0, 0, 0, ...) generates A001006, while M with a main diagonal of all 1's is the production matrix for A000108. - Gary W. Adamson, Jul 29 2011
From Gus Wiseman, Jun 22 2019: (Start)
Conjecture: Also the number of non-capturing set partitions of {1..n}. A set partition is capturing if it has two blocks of the form {...x...y...} and {...z...t...} where x < z and y > t or x > z and y < t. This is a weaker condition than nesting, so for example {{1,3,5},{2,4}} is capturing but not nesting. The a(0) = 1 through a(4) = 14 non-capturing set partitions are:
  {}  {{1}}  {{1,2}}    {{1,2,3}}      {{1,2,3,4}}
             {{1},{2}}  {{1},{2,3}}    {{1},{2,3,4}}
                        {{1,2},{3}}    {{1,2},{3,4}}
                        {{1,3},{2}}    {{1,2,3},{4}}
                        {{1},{2},{3}}  {{1,2,4},{3}}
                                       {{1,3},{2,4}}
                                       {{1,3,4},{2}}
                                       {{1},{2},{3,4}}
                                       {{1},{2,3},{4}}
                                       {{1,2},{3},{4}}
                                       {{1},{2,4},{3}}
                                       {{1,3},{2},{4}}
                                       {{1,4},{2},{3}}
                                       {{1},{2},{3},{4}}
Cf. A000108, A000110, A058681, A326212, A326237, A326243, A326244, A326249, A326255.
(End)
The above conjecture is true: A partition is non-capturing iff its representation in canonical sequential form avoids the patterns 1221 and 2112. In the context of these partition representations, the pattern 2112 is equivalent to the pattern 12112. Partitions whose canonical sequence form avoid 1221 and 12112 are one of the classes that are handled in the Mansour/Shattuck "Pattern Avoiding Partitions,..." paper. It shows that they are counted by this sequence. - Christian Sievers, Oct 29 2024

			a(4) = 14, a(5) = 41 since the top row of M^4 = (14, 14, 9, 3, 1), with 41 = (14 + 14 + 9 + 3 + 1).

G. C. Greubel, Table of n, a(n) for n = 0..1000
E. Barcucci et al., From Motzkin to Catalan Permutations, Discr. Math., 217 (2000), 33-49.
Jean-Luc Baril and Sergey Kirgizov, Bijections from Dyck and Motzkin meanders with catastrophes to pattern avoiding Dyck paths, arXiv:2104.01186 [math.CO], 2021.
Paul Barry, On sequences with {-1, 0, 1} Hankel transforms, arXiv preprint arXiv:1205.2565 [math.CO], 2012. - From _N. J. A. Sloane_, Oct 18 2012
Petr Gregor, Torsten Mütze, and Namrata, Combinatorial generation via permutation languages. VI. Binary trees, arXiv:2306.08420 [cs.DM], 2023.
Nickolas Hein and Jia Huang, Variations of the Catalan numbers from some nonassociative binary operations, arXiv:1807.04623 [math.CO], 2018.
J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5
Toufik Mansour and Mark Shattuck, Pattern Avoiding Partitions, Sequence A054391 and the Kernel Method, Applications and Applied Mathematics, Vol. 6, Issue 2 (December 2011), pp. 397-411.
T. Mansour and M. Shattuck, Restricted partitions and generalized Catalan numbers, PU. M. A., Vol. (2011), No. 2, pp. 239-251. - From _N. J. A. Sloane_, Oct 13 2012
Eric Marberg, Crossings and nestings in colored set partitions, arXiv preprint arXiv:1203.5738 [math.CO], 2012.

Interpolates between Motzkin numbers (A001006) and Catalan numbers (A000108). Cf. A005773, A054392, ...

Binomial transform of A224747.

c := x->(1-sqrt(1-4*x))/(2*x); a := (x,j)->(x)/((1-4*x)*(c(x))^2*(1-c(x))^(j))*(-x^2*(c(x))^2*(1-c(x))*(x^2*(c(x))^4)^(j)-(1-3*x-2*x^2)*(c(x))^2*(x*(c(x))^2)^(j)+x);
b := (x,j)->1+(1)/((1-4*x)*c(x)*(1-c(x))^(j))*(-2*x^3*(c(x))^2*(x^2*(c(x))^4)^(j)+(1-3*x-2*x^2)*c(x)*(x*(c(x))^2)^(j)-2*x^2);
co := (x,j)->(1)/((1-4*x)*(1-c(x))^(j))*(x^2*(x^2*(c(x))^4)^(j)-(1-3*x-2*x^2)*(x*(c(x))^2)^(j)+x^2);
s := (x,j)->(1-b(x,j)+(-1)^j*sqrt((1-b(x,j))^2-4*a(x,j)*co(x,j)))/(2*a(x,j)); j := 3; series(s(x,j),x=0..60); od; # j=1,2,3,... inf gives A001006, A005773, A054391, A054392, ..., A000108

CoefficientList[Series[1 - 2*x^2/(2*x^2 - 3*x + 1 - Sqrt[1 - 2*x - 3*x^2]), {x, 0, 50}], x] (* G. C. Greubel, Apr 27 2017 *)

a(n):=sum((sum((binomial(k,l)*l*sum(binomial(j,1-n-2*l+k+2*j)*binomial(n-1+l-k,j),j,0,n+l-k-1))/(n+l-k-1),l,1,k)),k,1,n-1)+1; /* Vladimir Kruchinin, Oct 31 2011 */

x='x+O('x^66); gf=1-2*x^2/(2*x^2-3*x+1-sqrt(1-2*x-3*x^2)); Vec(gf) \\ Joerg Arndt, Jun 29 2013

G.f.: 1 - 2*x^2 / (2*x^2 - 3*x + 1 - sqrt(1 - 2*x - 3*x^2)). - Mansour and Shattuck
G.f.: 1/(1-x-x^2/(1-2x-x^2/(1-x-x^2/(1-x-x^2/(1-x-x^2/(1-x-x^2/(1-... (continued fraction) (conjecture). - Paul Barry, Jan 19 2009
From Gary W. Adamson, Jul 29 2011: (Start)
a(n) = upper left term of M^n, a(n+1) = sum of top row terms of M^n; M = an infinite square production matrix as follows with a main diagonal of (1, 1, 1, 0, 0, 0, ...):
  1, 1, 0, 0, 0, 0, ...
  1, 1, 1, 0, 0, 0, ...
  1, 1, 1, 1, 0, 0, ...
  1, 1, 1, 0, 1, 0, ...
  1, 1, 1, 1, 0, 1, ...
  1, 1, 1, 1, 1, 0, ...
  ... (End)
a(n) = Sum_{k=1..n-1} (sum(l=1..k, (binomial(k,l)*l*sum(j=0..n+l-k-1, binomial(j,1-n-2*l+k+2*j)*binomial(n-1+l-k,j)))/(n+l-k-1))) + 1. - Vladimir Kruchinin, Oct 31 2011
D-finite with recurrence (-n+1)*a(n) + 3*(2*n-3)*a(n-1) + (-8*n+11)*a(n-2) + (-5*n+32)*a(n-3) + (7*n-31)*a(n-4) + 3*(-n+4)*a(n-5)= 0. - R. J. Mathar, Nov 26 2012
G.f.:  1 - x*(2*x^2-3*x+1 + 1/G(0))/(2*(x^3-3*x^2+4*x-1)), where G(k)= 1 + x*(2+3*x)*(4*k+1)/( 4*k+2 - x*(2+3*x)*(4*k+2)*(4*k+3)/(x*(2+3*x)*(4*k+3) + 4*(k+1)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jun 29 2013

A125187 Number of Dumont permutations of the first kind of length 2n avoiding the patterns 1423 and 4132.

Original entry on oeis.org

1, 1, 3, 12, 52, 232, 1049, 4777, 21845, 100159, 460023, 2115350, 9735205, 44829766, 206526972, 951759621, 4387156587, 20226421380, 93264500832, 430091815527, 1983549213861, 9148582037193, 42197572190160, 194643215702835

Offset: 0

Emeric Deutsch, Dec 19 2006

nonn

[1, 3, 12, 52, 232, ...] is INVERT transform of [1, 2, 27, 108, 440, ...] A026726. - Michael Somos, Apr 15 2012
HANKEL transform of sequence and the sequence omitting a(0) is the odd and even bisections of Fibonacci numbers respectively. This is the unique sequence with that property. - Michael Somos, Apr 15 2012
Bisection (even part) of A224747. - Alois P. Heinz, Jul 29 2013

			G.f. = 1 + x + 3*x^2 + 12*x^3 + 52*x^4 + 232*x^5 + 1049*x^6 + 4777*x^7 + 21845*x^8 + ...

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Cyril Banderier, Michael Wallner, Lattice paths with catastrophes, arXiv:1707.01931 [math.CO], 2017.
Paul Barry, A Note on Riordan Arrays with Catalan Halves, arXiv:1912.01124 [math.CO], 2019.
A. Burstein, Restricted Dumont permutations, arXiv:math/0402378 [math.CO], 2004
A. Burstein, Restricted Dumont permutations, Annals of Combinatorics, 9, 2005, 269-280 (Theorem 3.12).

Cf. A125188, A224747.

C:=(1-sqrt(1-4*x))/2/x: G:=(2-(1+x)*C)/(2-x-(1+x)*C): Gser:=series(G,x=0,30): seq(coeff(Gser,x,n),n=0..26);

a[ n_] := SeriesCoefficient[ (2 - 9 x + x^2 + (x + x^2) Sqrt[1 - 4 x]) / (2 (1 - 5 x + 2 x^2 - x^3)), {x, 0, n}]; (* Michael Somos, Jan 14 2014 *)

{a(n) = if( n<0, 0, polcoeff( (2 - 9*x + x^2 + (x + x^2) * sqrt(1 - 4*x + x * O(x^n)) ) / (2 * (1 - 5*x + 2*x^2 - x^3)), n))}; /* Michael Somos, Jan 14 2014 */

G.f.: [2-(1+x)C(x)]/[2-x-(1+x)C(x)], where C(x)=(1-sqrt(1-4x))/(2x) is the Catalan function.
From Gary W. Adamson, Jul 11 2011: (Start)
a(n) = upper left term in M^n, where M is an infinite square production matrix in which two columns of (1,2,3,...) are prepended to an infinite lower triangular matrix of all 1's and the rest zeros, as follows:
  1, 1, 0, 0, 0, 0, ...
  2, 2, 1, 0, 0, 0, ...
  3, 3, 1, 1, 0, 0, ...
  4, 4, 1, 1, 1, 0, ...
  5, 5, 1, 1, 1, 1, ...
  ... (End)
Given g.f. A(x), then 0 = A(x)^2 * (x^3 - 2*x^2 + 5*x - 1) + A(x) *(x^2 - 9*x + 2) + (x^2 + 4*x -1). - Michael Somos, Jan 14 2014
0 = a(n)*(16*a(n+1) +6*a(n+2) -14*a(n+3) +210*a(n+4) -128*a(n+5) +18*a(n+6)) +a(n+1)*(-46*a(n+1) +143*a(n+2) -173*a(n+3) -283*a(n+4) +202*a(n+5) -29*a(n+6)) +a(n+2)*(-63*a(n+2) +386*a(n+3) +765*a(n+4) -529*a(n+5) +75*a(n+6)) +a(n+3)*(-559*a(n+3) +509*a(n+4) -149*a(n+5) +19*a(n+6)) +a(n+4)*(-108*a(n+4) +71*a(n+5) -12*a(n+6)) +a(n+5)*(-4*a(n+5) +a(n+6)). - Michael Somos, Jan 14 2014
G.f.: ( 2 - 9*x + x^2 + (x + x^2) * sqrt(1 - 4*x) ) / (2 - 10*x + 4*x^2 - 2*x^3). - Michael Somos, Apr 15 2012
G.f. = (1 - 3*y + y^2) / (1 - 4*y + 3*y^2 - y^3) = 1 / (1 - y / (1 - y / (1 - 2*y / (1 + y / (2 - y))))) where y = (1 - sqrt(1 - 4*x)) / 2. - Michael Somos, Apr 12 2012
D-finite with recurrence (-n+1)*a(n) +4*(2*n-3)*a(n-1) +(-13*n+19)*a(n-2) +(-13*n+75)*a(n-3) +(5*n-29)*a(n-4) +2*(-2*n+9)*a(n-5)=0. - R. J. Mathar, Jul 27 2013

A369316 Number of Dyck bridges with resets to zero from (0,0) to (n,0).

Original entry on oeis.org

1, 0, 2, 2, 8, 14, 40, 84, 216, 486, 1200, 2780, 6744, 15836, 38096, 90056, 215728, 511750, 1223136, 2907052, 6939544, 16511028, 39386384, 93768696, 223589648, 532502748, 1269433376, 3023953560, 7207744496, 17172061944, 40926792224, 97513876880, 232395416672

Offset: 0

Florian Schager, Jan 19 2024

A Dyck bridge is a lattice path with steps U = (1,1) and D = (1,-1) that is allowed to go below the x-axis and ends at altitude 0.

A reset to zero is a step R = (1,-h) at altitude h for |h| > 1.

			For n = 4 the a(4) = 8 paths are UUUR, UUDD, UDUD, UDDU, DUUD, DUDU, DDUU, DDDR.

Florian Schager, Table of n, a(n) for n = 0..999

Cf. A224747 (Dyck excursions).

K := 1 - z*(u + 1/u);
v1, u1 := solve(K, u);
B := -z*diff(v1, z)/v1;
W := 1/(1 - 2*z);
W1 := -z*diff(v1, z)/v1^2;
Wminus1 := z*diff(u1, z);
Q := z*(W - B - W1 - Wminus1);
series(B/(1 - Q), z, 40);
# second Maple program:
b:= proc(x, y) option remember; `if`(x=0, `if`(y=0, 1, 0),
      `if`(y>1, b(x-1, 0), 0)+b(x-1, abs(y-1))+b(x-1, y+1))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..32);  # Alois P. Heinz, Jan 19 2024

b[x_, y_] := b[x, y] = If[x == 0, If[y == 0, 1, 0],
   If[y > 1, b[x - 1, 0], 0] + b[x - 1, Abs[y - 1]] + b[x - 1, y + 1]];
a[n_] := b[n, 0];
Table[a[n], {n, 0, 32}] (* Jean-François Alcover, Feb 23 2025, after Alois P. Heinz *)

seq(n) = my(r=sqrt(1 - 4*x^2 + O(x*x^n))); Vec((1 - 2*x)*(1 + r)^2/(2*(1 - 2*x - 2*x^2 + 2*x^3)*r + 2 - 4*x - 8*x^2 + 12*x^3 + 8*x^4)) \\ Andrew Howroyd, Jan 19 2024

G.f.: -(2*z - 1)*(1 + sqrt(-4*z^2 + 1))^2/((4*z^3 - 4*z^2 - 4*z + 2)*sqrt(-4*z^2 + 1) + 8*z^4 + 12*z^3 - 8*z^2 - 4*z + 2).

a(n) = (4*(2*n-5)*a(n-2) +4*(n-1)*a(n-3) -16*(n-4)*a(n-4) -16*(n-4)*a(n-5))/(n-1) for n>=5. - Alois P. Heinz, Jan 20 2024

A369432 Number of Dyck excursions with catastrophes from (0,0) to (n,0).

Original entry on oeis.org

1, 1, 3, 6, 16, 37, 95, 230, 582, 1434, 3606, 8952, 22446, 55917, 140007, 349374, 874150, 2183230, 5460506, 13643972, 34118328, 85270626, 213205958, 532926716, 1332420796, 3330739972, 8327221380, 20816939100, 52043684970, 130105200765, 325267849335, 813155081070

Offset: 0

Florian Schager, Jan 23 2024

A Dyck excursion is a lattice path with steps U = (1,1) and D = (1,-1) that does not go below the x-axis and ends at the x-axis.

A catastrophe is a step C = (1,-k) from altitude k to altitude 0 for k >= 0.

			For n = 3 the a(3) = 6 solutions are UUC, UDC, UCC, CUD, CUC, CCC.
For n = 4 the a(4) = 16 solutions are UUUC, UUDD, UUDC, UUCC, UDUD, UDUC, UDCC, UCUD, UCUC, UCCC, CUUC, CUDC, CUCC, CCUD, CCUC, CCCC.

Alois P. Heinz, Table of n, a(n) for n = 0..2514
Cyril Banderier and Michael Wallner, Lattice paths with catastrophes, arXiv:1707.01931 [math.CO], 2017, p.7.

Cf. A054341 (Dyck meanders with catastrophes).

Cf. A224747 (different model of catastrophes).

u1 := solve(1 - z*(1/u + u), u)[2];
M := (1 - u1)/(1 - 2*z);
E := u1/z;
F := E/(-M*z + 1);
series(F, z, 33);
# second Maple program:
b:= proc(x, y) option remember; `if`(x=0, `if`(y=0, 1, 0),
      b(x-1, 0)+`if`(y>0, b(x-1, y-1), 0)+b(x-1, y+1))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..31);  # Alois P. Heinz, Jan 23 2024

b[x_, y_] := b[x, y] = If[x == 0, If[y == 0, 1, 0], b[x-1, 0] + If[y > 0, b[x-1, y-1], 0] + b[x-1, y+1]];
a[n_] := b[n, 0];
Table[a[n], {n, 0, 31}] (* Jean-François Alcover, Jul 24 2025, after Alois P. Heinz *)

my(N=44,z='z+O('z^N)); Vec((1 - sqrt(1 -4*z^2))*(2*z - 1)/(z^2*(6*z - 3 + sqrt(1 - 4*z^2))))

G.f.: (1 - sqrt(1 - 4*z^2))*(2*z - 1)/(z^2*(6*z - 3 + sqrt(1 - 4*z^2))).

a(n) ~ 3/8*(5/2)^n.

cp's OEIS Frontend

A054391 Number of permutations with certain forbidden subsequences.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Formula

A125187 Number of Dumont permutations of the first kind of length 2n avoiding the patterns 1423 and 4132.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A369316 Number of Dyck bridges with resets to zero from (0,0) to (n,0).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A369432 Number of Dyck excursions with catastrophes from (0,0) to (n,0).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula