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

Author

Emeric Deutsch

Keywords

• nonn

Comments

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

Links

• 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

Crossrefs

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

Programs

Maple

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;

Mathematica

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

Maxima

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

PARI

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

PARI

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

Formula

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

Extensions

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

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