login
This site is supported by donations to The OEIS Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A033321 Binomial transform of Fine's sequence A000957: 1, 0, 1, 2, 6, 18, 57, 186, ... 21
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

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)

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.

Christian Bean, Finding structure in permutation sets, Ph.D. Dissertation, Reykjavík University, School of Computer Science, 2018.

David Bevan, The permutation class Av(4213,2143), arXiv:1510.06328 [math.CO], 2014.

J. Bloom, A. Burstein, Egge triples and unbalanced Wilf-equivalence, arXiv:1410.0230 [math.CO], 2014.

R. Brignall, S. Huczynska and V. Vatter, Simple permutations and algebraic generating functions, arXiv:math/0608391 [math.CO], 2006.

Robert Brignall, Jakub Sliacan, Juxtaposing Catalan permutation classes with monotone ones, arXiv:1611.05370 [math.CO], 2016.

E. Deutsch, E. Munarini, S. Rinaldi, Skew Dyck paths, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203.

Alice L. L. Gao, Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.

Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze, Aaron Williams, Combinatorial generation via permutation languages. I. Fundamentals, arXiv:1906.06069 [cs.DM], 2019.

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

Sam Miner, Enumeration of several two-by-four classes, arXiv preprint arXiv:1610.01908 [math.CO], 2016.

N. J. A. Sloane, Transforms

R. Smith and V. Vatter, A stack and a pop stack in series, arXiv:1303.1395 [math.CO], 2013.

Index entries for reversions of series

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

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) = 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) ) ) + 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

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

PROG

(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

CROSSREFS

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

Sequence in context: A150197 A150198 A257562 * A050203 A112806 A150199

Adjacent sequences:  A033318 A033319 A033320 * A033322 A033323 A033324

KEYWORD

nonn,changed

AUTHOR

Emeric Deutsch

EXTENSIONS

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

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 9 00:32 EST 2019. Contains 329871 sequences. (Running on oeis4.)