login
Number of permutations which are the union of an increasing and a decreasing subsequence.
6

%I #65 Mar 23 2024 04:30:54

%S 1,1,2,6,22,86,340,1340,5254,20518,79932,311028,1209916,4707964,

%T 18330728,71429176,278586182,1087537414,4249391468,16618640836,

%U 65048019092,254814326164,998953992728,3919041821896,15385395144092,60438585676636

%N Number of permutations which are the union of an increasing and a decreasing subsequence.

%H Vincenzo Librandi, <a href="/A029759/b029759.txt">Table of n, a(n) for n = 0..1000</a>

%H Michael H. Albert, M. D. Atkinson, Mathilde Bouvel, Nik Ruškuc and Vincent Vatter, <a href="https://arxiv.org/abs/1108.6319">Geometric grid classes of permutations</a>, arXiv:1108.6319 [math.CO], 2011-2012.

%H M. H. Albert and V. Vatter, <a href="http://arxiv.org/abs/1301.3122">Generating and enumerating 321-avoiding and skew-merged simple permutations</a>, arXiv preprint arXiv:1301.3122 [math.CO], 2013. - _N. J. A. Sloane_, Feb 11 2013

%H M. D. Atkinson, <a href="https://doi.org/10.37236/1344">Permutations which are the union of an increasing and a decreasing subsequence</a>, Electronic Journal of Combinatorics, R6 of Volume 5(1), 1998.

%H CombOS - Combinatorial Object Server, <a href="http://combos.org/jump">Generate pattern-avoiding permutations</a>

%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 E. Rowland and R. Yassawi, <a href="http://arxiv.org/abs/1310.8635">Automatic congruences for diagonals of rational functions</a>, arXiv preprint arXiv:1310.8635 [math.NT], 2013.

%H Darla Kremer and Wai Chee Shiu, <a href="http://dx.doi.org/10.1016/S0012-365X(03)00042-6">Finite transition matrices for permutations avoiding pairs of length four patterns</a>, Discrete Math. 268 (2003), 171-183. MR1983276 (2004b:05006). See Table 1.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Enumerations_of_specific_permutation_classes#Classes_avoiding_two_patterns_of_length_4">Permutation classes avoiding two patterns of length 4</a>.

%F G.f.: (1-3*x)/((1-2*x)*sqrt(1-4*x)). - _Vincent Vatter_, Jun 21 2011

%F D-finite with recurrence: n*a(n) +(-9*n+8)*a(n-1) +2*(13*n-23)*a(n-2) +12*(-2*n+5)*a(n-3)=0. - _R. J. Mathar_, Aug 24 2013

%F a(n) ~ 2^(2*n-1)/sqrt(Pi*n). - _Vaclav Kotesovec_, Mar 18 2014

%F a(n) = (binomial(2*n, n)*(hypergeom([1, n+1/2], [n+1], 2) + 2) + i*2^n)/2, where i is the imaginary unit. - _Peter Luschny_, Oct 25 2018

%F a(n) = Sum_{k=0..n} (-1)^k*A000984(floor(k/2))*A038207(n,k). - _Mélika Tebni_, Mar 22 2024

%p a := n -> binomial(2*n, n) - add(2^(n-m-1)*binomial(2*m, m), m = 0.. n-1);

%p # second program:

%p A029759 := n -> add((-1)^k*binomial(2*iquo(k, 2), iquo(k, 2))*binomial(n, k)*2^(n-k), k = 0 .. n): seq(A029759(n), n = 0 .. 25); # _Mélika Tebni_, Mar 22 2024

%t CoefficientList[Series[(1 - 3 x) / ((1 - 2 x) Sqrt[1 - 4 x]), {x, 0, 60}], x] (* _Vincenzo Librandi_, Aug 25 2013 *)

%Y Cf. A000984, A038207, A220589.

%K nonn,easy

%O 0,3

%A _N. J. A. Sloane_.