A128714 -id:A128714 - cp's OEIS frontend

A033321 Binomial transform of Fine's sequence A000957: 1, 0, 1, 2, 6, 18, 57, 186, ...

1, 1, 2, 6, 21, 79, 311, 1265, 5275, 22431, 96900, 424068, 1876143, 8377299, 37704042, 170870106, 779058843, 3571051579, 16447100702, 76073821946, 353224531663, 1645807790529, 7692793487307, 36061795278341, 169498231169821

Offset: 0

Emeric Deutsch

nonn

Number of permutations avoiding the patterns {2431,4231,4321}; number of weak sorting class based on 2431. - Len Smiley, Nov 01 2005
Number of permutations avoiding the patterns {2413, 3142, 2143}. - Vincent Vatter, Aug 16 2006
Number of permutations avoiding the patterns {2143, 3142, 4132}. - Alexander Burstein and Jonathan Bloom, Aug 03 2013
Number of unimodal Lehmer codes. Those are exactly the inversion sequences for permutations avoiding the patterns {2143, 3142, 4132}. - Alexander Burstein, Jun 16 2015
Number of skew Dyck paths of semilength n ending with a down step (1,-1). A skew Dyck path is a path in the first quadrant which begins at the origin, ends on the x-axis, consists of steps U=(1,1)(up), D=(1,-1)(down) and L=(-1,-1)(left) so that up and left steps do not overlap. The length of the path is defined to be the number of its steps. Number of skew Dyck paths of semilength n and ending with a left step is A128714(n). - Emeric Deutsch, May 11 2007
Number of permutations sortable by a pop stack followed directly by a stack. Equivalently, the number of permutations avoiding {2431, 3142, 3241}. - Vincent Vatter, Mar 06 2013
Hankel transform of this sequence gives A000012 = [1,1,1,1,1,1,...]. - Philippe Deléham, Oct 24 2007
Starting with offset 1, Hankel transform = odd-indexed Fibonacci numbers. - Gary W. Adamson, Dec 27 2008
Starting with offset 1 = INVERT transform of A002212: (1, 1, 3, 10, 36, 137, ...). - Gary W. Adamson, May 19 2009
Equals INVERTi transform of A007317: (1, 2, 5, 15, 51, 188, ...). - Gary W. Adamson, May 17 2009
Number of sequences (e(1), ..., e(n)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) > e(j) < e(k). [Martinez and Savage, 2.20] - Eric M. Schmidt, Jul 17 2017
From David Callan, Jul 21 2017: (Start)
a(n) is the number of permutations of [n] in which the excedances and subcedances are both increasing. (For example, the 3 permutations of [4] NOT counted by a(4)=21 are 3421, 4312, 4321 with excedances/subcedances 34/21, 43/12, 43/21 respectively.)
Proof. It suffices to show that (*) the number of such permutations of [n] containing k fixed points is binomial(n,k)*F(n-k), where F is the Fine number A000957. Since F(n) is the number of 321-avoiding derangements of [n] and because inserting or deleting a fixed point in a permutation does not change the excedance/fixed point/subcedance status of any other entry, (*) is an immediate consequence of the following claim: The excedances and subcedances of a permutation p are both increasing if and only if p avoids 321. The claim is a nice exercise utilizing the cycles of p for the "if" direction and the pigeonhole principle for the "only if" direction. (End)
Conjectured to be the number of permutations of length n that are sorted to the identity by a consecutive-231-avoiding stack followed by a classical-21-avoiding stack. - Colin Defant, Aug 30 2020
a(n) is the number of permutations of length n avoiding the partially ordered pattern (POP) {3>1, 3>4, 1>2} of length 4. That is, the number of length n permutations having no subsequences of length 4 in which the third element is the largest and the first element is larger than the second element. - Sergey Kitaev, Dec 10 2020

G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms 0 to 200 by T. D. Noe)
M. Albert, R. Aldred, M. Atkinson, C Handley, D. Holton, D. McCaughan, and H. van Ditmarsch, Sorting Classes, Elec. J. of Comb. 12 (2005) R31.
Andrei Asinowski and Cyril Banderier, From geometry to generating functions: rectangulations and permutations, arXiv:2401.05558 [cs.DM], 2024. See page 2.
Jean-Luc Baril, José L. Ramírez, and Lina M. Simbaqueba, Counting prefixes of skew Dyck paths, J. Int. Seq., Vol. 24 (2021), Article 21.8.2.
Paul Barry, Series reversion with Jacobi and Thron continued fractions, arXiv:2107.14278 [math.NT], 2021.
Christian Bean, Finding structure in permutation sets, Ph.D. Dissertation, Reykjavík University, School of Computer Science, 2018.
Christian Bean, Émile Nadeau, and Henning Ulfarsson, Enumeration of Permutation Classes and Weighted Labelled Independent Sets, arXiv:1912.07503 [math.CO], 2019.
David Bevan, The permutation class Av(4213,2143), arXiv:1510.06328 [math.CO], 2014.
Jonathan Bloom and Alex Burstein, Egge triples and unbalanced Wilf-equivalence, arXiv:1410.0230 [math.CO], 2014.
Miklos Bona, Long increasing subsequences and non-algebraicity, arXiv:2310.13649 [math.CO], 2023.
Robert Brignall, Sophie Huczynska, and Vincent Vatter, Simple permutations and algebraic generating functions, arXiv:math/0608391 [math.CO], 2006.
Robert Brignall and Jakub Sliacan, Juxtaposing Catalan permutation classes with monotone ones, arXiv:1611.05370 [math.CO], 2016.
Colin Defant and Kai Zheng, Stack-Sorting with Consecutive-Pattern-Avoiding Stacks, arXiv:2008.12297 [math.CO], 2020.
Isaac DeJager, Madeleine Naquin, and Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.
Emeric Deutsch, Emanuele Munarini, and Simone Rinaldi, Skew Dyck paths, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203.
Rigoberto Flórez, Leandro Junes, Luisa M. Montoya, and José L. Ramírez, Counting Subwords in Non-Decreasing Dyck Paths, J. Int. Seq. (2025) Vol. 28, Art. No. 25.1.6. See p. 19.
Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.
Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze, and Aaron Williams, Combinatorial generation via permutation languages. I. Fundamentals, arXiv:1906.06069 [cs.DM], 2019.
John W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.
Toufik Mansour and Mark Shattuck, Nine classes of permutations enumerated by binomial transform of Fine's sequence, Discrete Applied Mathematics, Vol. 226, 31 July 2017, p. 94-105.
Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.
Arturo Merino and Torsten Mütze, Combinatorial generation via permutation languages. III. Rectangulations, arXiv:2103.09333 [math.CO], 2021.
Sam Miner, Enumeration of several two-by-four classes, arXiv preprint arXiv:1610.01908 [math.CO], 2016.
N. J. A. Sloane, Transforms
Rebecca Smith and Vincent Vatter, A stack and a pop stack in series, arXiv:1303.1395 [math.CO], 2013.
Index entries for reversions of series

Cf. A000957, A002212, A007317, A128714, A214611.

a[0] := 1: a[1] := 1: a[2] := 2: for n from 3 to 23 do a[n] := ((13*n-5)*a[n-1]-(16*n-23)*a[n-2]+5*(n-2)*a[n-3])/2/(n+1) od;

f[n_] := Sum[Binomial[n, k]*g[n - k], {k, 0, n}]; g[n_] := Sum[(-1)^(m + n)(n + m)!/n!/m!(n - m + 1)/(n + 1), {m, 0, n}]; Table[ f[n], {n, 24}] (* Robert G. Wilson v, Nov 04 2005 *)

a(n):=sum(sum(binomial(n-m-1,k-1)*m/(k+m)*binomial(2*k+m-1,k+m-1),k,1,n-m),m,1,n-1)+1; /* Vladimir Kruchinin, May 12 2011 */

a(n)=1+sum(m=1,n-1,sum(k=1,n-m,binomial(n-m-1,k-1)/(k+m)* binomial(2*k+m-1,k+m-1)*m)) \\ Charles R Greathouse IV, Mar 06 2013

x='x+O('x^50); Vec(2/(1+x+sqrt(1-6*x+5*x^2))) \\ Altug Alkan, Oct 22 2015

Also REVERT transform of x*(2*x-1)/(x^2+x-1). - Olivier Gérard
G.f.: 2/(1 + x + sqrt(1 - 6*x + 5*x^2)).
D-finite with recurrence a(n) = ((13*n-5)*a(n-1) - (16*n-23)*a(n-2) + 5*(n-2)*a(n-3))/(2*(n+1)) (n>=3); a(0)=a(1)=1, a(2)=2. - Emeric Deutsch, Mar 21 2004
Binomial transform of Fine's sequence: a(n) = Sum_{k=0..n} binomial(n, k)*A000957(n-k).
G.f.: 1/(1-x-x^2/(1-3x-x^2/(1-3x-x^2/(1-3x-x^2/(1-... (continued fraction). - Paul Barry, Jun 15 2009
a(n) = Sum_{k=0..n} A091965(n,k)*(-2)^k. - Philippe Deléham, Nov 28 2009
a(n) = 1 + Sum_{m=1..n-1} Sum_{k=1..n-m} binomial(n-m-1, k-1)*(m/(k+m))*binomial(2*k+m-1, k+m-1). - Vladimir Kruchinin, May 12 2011
a(n) = upper left term in M^n, M = the production matrix:
  1, 1, 0, 0, 0, 0, 0, ...
  1, 2, 1, 0, 0, 0, 0, ...
  1, 2, 1, 1, 0, 0, 0, ...
  1, 2, 1, 2, 1, 0, 0, ...
  1, 2, 1, 2, 1, 1, 0, ...
  1, 2, 1, 2, 1, 2, 1, ...
  ...
- Gary W. Adamson, Jul 08 2011
a(n) ~ 5^(n+3/2)/(18*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Aug 09 2013
G.f.: 1/(1-x*C(x/(1-x))), where C(x) = g.f. for A000108(n). - Alexander Burstein, Oct 05 2014

More terms from Robert G. Wilson v, Nov 04 2005

Entry revised by N. J. A. Sloane, Aug 07 2006

A230823 Number of modified skew Dyck paths of semilength n.

Original entry on oeis.org

1, 1, 2, 6, 20, 73, 281, 1124, 4627, 19474, 83421, 362528, 1594389, 7083078, 31738724, 143281473, 651048571, 2975243348, 13665866849, 63055369522, 292130900461, 1358415528683, 6337824891559, 29660089051015, 139193062791189, 654903798282528, 3088627236146085

Offset: 0

David Scambler and Alois P. Heinz, Oct 31 2013

nonn

A modified skew Dyck path is a path in the first quadrant which begins at the origin, ends on the x-axis, consists of steps U=(1,1) (up), D=(1,-1) (down) and A=(-1,1) (anti-down) so that A and D steps do not overlap.

			a(0) = 1: the empty path.
a(1) = 1: UD.
a(2) = 2: UUDD, UDUD.
a(3) = 6: UUUDDD, UUDUDD, UUDDUD, UAUDDD, UDUUDD, UDUDUD.
a(4) = 20: UUUUDDDD, UUUDUDDD, UUUDDUDD, UUUDDDUD, UUAUDDDD, UUDUUDDD, UUDUDUDD, UUDUDDUD, UUDDUUDD, UUDDUDUD, UAUUDDDD, UAUDUDDD, UAUDDUDD, UAUDDDUD, UDUUUDDD, UDUUDUDD, UDUUDDUD, UDUAUDDD, UDUDUUDD, UDUDUDUD.
a(5) = 73: UUUUUDDDDD, UUUUDUDDDD, UUUUDDUDDD, ..., UDUDUAUDDD, UDUDUDUUDD, UDUDUDUDUD.

Alois P. Heinz, Table of n, a(n) for n = 0..600

Cf. A000108, A128714.

Row sums of A274372 and of A274404.

b:= proc(x, y, t, n) option remember; `if`(y>n, 0,
      `if`(n=y, `if`(t=2, 0, 1), b(x+1, y+1, 0, n-1)+
      `if`(t<>1 and x>0, b(x-1, y+1, 2, n-1), 0)+
      `if`(t<>2 and y>0, b(x+1, y-1, 1, n-1), 0)))
    end:
a:= n-> b(0$3, 2*n):
seq(a(n), n=0..30);

b[x_, y_, t_, n_] := b[x, y, t, n] = If[y > n, 0, If[n == y, If[t == 2, 0, 1], b[x+1, y+1, 0, n-1] + If[t != 1 && x > 0, b[x-1, y+1, 2, n-1], 0] + If[t != 2 && y > 0, b[x+1, y-1, 1, n-1], 0]] ]; a[n_] := b[0, 0, 0, 2*n]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Dec 16 2013, translated from Maple *)

a(n) ~ c * 5^n / n^(3/2), where c = 0.27726256768213709977373928535... . - Vaclav Kotesovec, Jul 16 2014

G.f.: 1/(1 - x/(1 - (x + x^2)/(1 - (x + x^2 + x^3)/(1 - (x + x^2 + x^3 + x^4)/(1 - ...))))), a continued fraction (conjecture). - Ilya Gutkovskiy, Jun 08 2017

cp's OEIS Frontend

A033321 Binomial transform of Fine's sequence A000957: 1, 0, 1, 2, 6, 18, 57, 186, ...

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

PARI

Formula

Extensions

A230823 Number of modified skew Dyck paths of semilength n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A188463 Coefficient array of the second column of the inverse of the Riordan array ((1+(r+1)x)/(1+(r+2)x+rx^2), x/(1+(r+2)x+rx^2)).

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula