|
%I #171 Jan 17 2024 01:23:52
%S 1,1,2,6,21,79,311,1265,5275,22431,96900,424068,1876143,8377299,
%T 37704042,170870106,779058843,3571051579,16447100702,76073821946,
%U 353224531663,1645807790529,7692793487307,36061795278341,169498231169821
%N Binomial transform of Fine's sequence A000957: 1, 0, 1, 2, 6, 18, 57, 186, ...
%C Number of permutations avoiding the patterns {2431,4231,4321}; number of weak sorting class based on 2431. - _Len Smiley_, Nov 01 2005
%C Number of permutations avoiding the patterns {2413, 3142, 2143}. - _Vincent Vatter_, Aug 16 2006
%C Number of permutations avoiding the patterns {2143, 3142, 4132}. - _Alexander Burstein_ and Jonathan Bloom, Aug 03 2013
%C Number of unimodal Lehmer codes. Those are exactly the inversion sequences for permutations avoiding the patterns {2143, 3142, 4132}. - _Alexander Burstein_, Jun 16 2015
%C 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
%C 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
%C Hankel transform of this sequence gives A000012 = [1,1,1,1,1,1,...]. - _Philippe Deléham_, Oct 24 2007
%C Starting with offset 1, Hankel transform = odd-indexed Fibonacci numbers. - _Gary W. Adamson_, Dec 27 2008
%C Starting with offset 1 = INVERT transform of A002212: (1, 1, 3, 10, 36, 137, ...). - _Gary W. Adamson_, May 19 2009
%C Equals INVERTi transform of A007317: (1, 2, 5, 15, 51, 188, ...). - _Gary W. Adamson_, May 17 2009
%C 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
%C From _David Callan_, Jul 21 2017: (Start)
%C 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.)
%C 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)
%C 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
%C 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
%H G. C. Greubel, <a href="/A033321/b033321.txt">Table of n, a(n) for n = 0..1000</a> (terms 0 to 200 by T. D. Noe)
%H M. Albert, R. Aldred, M. Atkinson, C Handley, D. Holton, D. McCaughan, and H. van Ditmarsch, <a href="https://doi.org/10.37236/1928">Sorting Classes</a>, Elec. J. of Comb. 12 (2005) R31.
%H Andrei Asinowski and Cyril Banderier, <a href="https://arxiv.org/abs/2401.05558">From geometry to generating functions: rectangulations and permutations</a>, arXiv:2401.05558 [cs.DM], 2024. See page 2.
%H Jean-Luc Baril, José L. Ramírez, and Lina M. Simbaqueba, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL24/Ramirez/ramirez10.html">Counting prefixes of skew Dyck paths</a>, J. Int. Seq., Vol. 24 (2021), Article 21.8.2.
%H Paul Barry, <a href="https://arxiv.org/abs/2107.14278">Series reversion with Jacobi and Thron continued fractions</a>, arXiv:2107.14278 [math.NT], 2021.
%H Christian Bean, <a href="https://hdl.handle.net/20.500.11815/1184">Finding structure in permutation sets</a>, Ph.D. Dissertation, Reykjavík University, School of Computer Science, 2018.
%H Christian Bean, Émile Nadeau, and Henning Ulfarsson, <a href="https://arxiv.org/abs/1912.07503">Enumeration of Permutation Classes and Weighted Labelled Independent Sets</a>, arXiv:1912.07503 [math.CO], 2019.
%H David Bevan, <a href="http://arxiv.org/abs//1510.06328">The permutation class Av(4213,2143)</a>, arXiv:1510.06328 [math.CO], 2014.
%H J. Bloom and A. Burstein, <a href="http://arxiv.org/abs/1410.0230">Egge triples and unbalanced Wilf-equivalence</a>, arXiv:1410.0230 [math.CO], 2014.
%H Miklos Bona, <a href="https://arxiv.org/abs/2310.13649">Long increasing subsequences and non-algebraicity</a>, arXiv:2310.13649 [math.CO], 2023.
%H R. Brignall, S. Huczynska, and V. Vatter, <a href="http://arXiv.org/abs/math.CO/0608391">Simple permutations and algebraic generating functions</a>, arXiv:math/0608391 [math.CO], 2006.
%H Robert Brignall and Jakub Sliacan, <a href="https://arxiv.org/abs/1611.05370">Juxtaposing Catalan permutation classes with monotone ones</a>, arXiv:1611.05370 [math.CO], 2016.
%H C. Defant and K. Zheng, <a href="https://arxiv.org/abs/2008.12297">Stack-Sorting with Consecutive-Pattern-Avoiding Stacks</a>, arXiv:2008.12297 [math.CO], 2020.
%H Isaac DeJager, Madeleine Naquin, and Frank Seidl, <a href="https://www.valpo.edu/mathematics-statistics/files/2019/08/Drube2019.pdf">Colored Motzkin Paths of Higher Order</a>, VERUM 2019.
%H E. Deutsch, E. Munarini, and S. Rinaldi, <a href="http://dx.doi.org/10.1016/j.jspi.2010.01.015">Skew Dyck paths</a>, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203.
%H Alice L. L. Gao and Sergey Kitaev, <a href="https://arxiv.org/abs/1903.08946">On partially ordered patterns of length 4 and 5 in permutations</a>, arXiv:1903.08946 [math.CO], 2019.
%H Alice L. L. Gao and Sergey Kitaev, <a href="https://doi.org/10.37236/8605">On partially ordered patterns of length 4 and 5 in permutations</a>, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
%H Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze, and Aaron Williams, <a href="https://arxiv.org/abs/1906.06069">Combinatorial generation via permutation languages. I. Fundamentals</a>, arXiv:1906.06069 [cs.DM], 2019.
%H J. W. Layman, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/LAYMAN/hankel.html">The Hankel Transform and Some of its Properties</a>, J. Integer Sequences, 4 (2001), #01.1.5.
%H Toufik Mansour and Mark Shattuck, <a href="https://dx.doi.org/10.1016/j.dam.2017.04.015">Nine classes of permutations enumerated by binomial transform of Fine's sequence</a>, Discrete Applied Mathematics, Vol. 226, 31 July 2017, p. 94-105.
%H Megan A. Martinez and Carla D. Savage, <a href="https://arxiv.org/abs/1609.08106">Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations</a>, arXiv:1609.08106 [math.CO], 2016.
%H Arturo Merino and Torsten Mütze, <a href="https://arxiv.org/abs/2103.09333">Combinatorial generation via permutation languages. III. Rectangulations</a>, arXiv:2103.09333 [math.CO], 2021.
%H Sam Miner, <a href="https://arxiv.org/abs/1610.01908">Enumeration of several two-by-four classes</a>, arXiv preprint arXiv:1610.01908 [math.CO], 2016.
%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>
%H R. Smith and V. Vatter, <a href="https://arxiv.org/abs/1303.1395">A stack and a pop stack in series</a>, arXiv:1303.1395 [math.CO], 2013.
%H <a href="/index/Res#revert">Index entries for reversions of series</a>
%F Also REVERT transform of x*(2*x-1)/(x^2+x-1). - _Olivier Gérard_
%F G.f.: 2/(1 + x + sqrt(1 - 6*x + 5*x^2)).
%F 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
%F Binomial transform of Fine's sequence: a(n) = Sum_{k=0..n} binomial(n, k)*A000957(n-k).
%F 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
%F a(n) = Sum_{k=0..n} A091965(n,k)*(-2)^k. - _Philippe Deléham_, Nov 28 2009
%F 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
%F a(n) = upper left term in M^n, M = the production matrix:
%F 1, 1, 0, 0, 0, 0, 0, ...
%F 1, 2, 1, 0, 0, 0, 0, ...
%F 1, 2, 1, 1, 0, 0, 0, ...
%F 1, 2, 1, 2, 1, 0, 0, ...
%F 1, 2, 1, 2, 1, 1, 0, ...
%F 1, 2, 1, 2, 1, 2, 1, ...
%F ...
%F - _Gary W. Adamson_, Jul 08 2011
%F a(n) ~ 5^(n+3/2)/(18*sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Aug 09 2013
%F G.f.: 1/(1-x*C(x/(1-x))), where C(x) = g.f. for A000108(n). - _Alexander Burstein_, Oct 05 2014
%p 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;
%t 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 *)
%o (Maxima)
%o 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 */
%o (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
%o (PARI) x='x+O('x^50); Vec(2/(1+x+sqrt(1-6*x+5*x^2))) \\ _Altug Alkan_, Oct 22 2015
%Y Cf. A000957, A002212, A007317, A128714, A214611.
%K nonn
%O 0,3
%A _Emeric Deutsch_
%E More terms from _Robert G. Wilson v_, Nov 04 2005
%E Entry revised by _N. J. A. Sloane_, Aug 07 2006
|
