|
%I #146 Jun 12 2022 06:42:27
%S 1,1,2,5,17,70,349,2017,13358,99377,822041,7477162,74207209,797771521,
%T 9236662346,114579019469,1516103040833,21314681315998,317288088082405,
%U 4985505271920097,82459612672301846,1432064398910663705,26054771465540507273,495583804405888997218
%N Number of permutations of n elements not containing the consecutive pattern 123.
%C Permutations on n letters without double falls. A permutation w has a double fall at k if w(k) > w(k+1) > w(k+2) and has an initial fall if w(1) > w(2).
%C Hankel transform is A055209. - _Paul Barry_, Jan 12 2009
%C Increasing colored 1-2 trees of order n with choice of two colors for the right branches of the vertices of outdegree 2 except those vertices on the path from the root to the leftmost leaf. - _Wenjin Woan_, May 21 2011
%D F. N. David and D. E. Barton, Combinatorial Chance, Hafner, New York, 1962, pp. 156-157.
%D I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983, (5.2.17).
%H Alois P. Heinz, <a href="/A049774/b049774.txt">Table of n, a(n) for n = 0..464</a> (first 201 terms from Ray Chandler)
%H Martin Aigner, <a href="http://dx.doi.org/10.1007/978-88-470-2107-5_15">Catalan and other numbers: a recurrent theme</a>, in Algebraic Combinatorics and Computer Science, a Tribute to Gian-Carlo Rota, pp.347-390, Springer, 2001.
%H Juan S. Auli, <a href="https://search.proquest.com/openview/3f0cef1fbdb016d61e16412e4b855969/1">Pattern Avoidance in Inversion Sequences</a>, Ph. D. thesis, Dartmouth College, ProQuest Dissertations Publishing (2020), 27964164.
%H Juan S. Auli, Sergi Elizalde, <a href="https://arxiv.org/abs/1904.02694">Consecutive Patterns in Inversion Sequences</a>, arXiv:1904.02694 [math.CO], 2019. See Table 1.
%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Barry2/barry281.html">Constructing Exponential Riordan Arrays from Their A and Z Sequences</a>, Journal of Integer Sequences, 17 (2014), #14.2.6.
%H Paul Barry, <a href="https://arxiv.org/abs/1802.03443">On a transformation of Riordan moment sequences</a>, arXiv:1802.03443 [math.CO], 2018.
%H Nicolas Basset, <a href="http://hal-upec-upem.archives-ouvertes.fr/docs/00/86/89/18/PDF/autreversionlongue.pdf">Counting and generating permutations using timed languages</a>, HAL Id: hal-00820373, 2013.
%H A. Baxter, B. Nakamura, and D. Zeilberger. <a href="http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/auto.html">Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes</a>; <a href="/A049774/a049774.pdf">Local copy</a> [Pdf file only, no active links].
%H S. Elizalde, <a href="https://arxiv.org/abs/math/0505254">Asymptotic enumeration of permutations avoiding generalized patterns</a> arXiv:math/0505254 [math.CO], 2015.
%H S. Elizalde and M. Noy, <a href="http://dx.doi.org/10.1016/S0196-8858(02)00527-4">Consecutive patterns in permutations</a>, Adv. Appl. Math. 30 (2003), 110-123.
%H Steven Finch, <a href="https://web.archive.org/web/20150405060634/http://www.people.fas.harvard.edu/~sfinch/csolve/av.pdf">Pattern-Avoiding Permutations</a> [Archived version]
%H Steven Finch, <a href="/A240885/a240885.pdf">Pattern-Avoiding Permutations</a> [Cached copy, with permission]
%H Ira M. Gessel and Yan Zhuang, <a href="http://arxiv.org/abs/1408.1886">Counting permutations by alternating descents </a>, arXiv:1408.1886 [math.CO], 2014. See Eq. (3). - _N. J. A. Sloane_, Aug 11 2014
%H Kaarel Hänni, <a href="https://arxiv.org/abs/2011.14360">Asymptotics of descent functions</a>, arXiv:2011.14360 [math.CO], Nov 29 2020, p. 14.
%H Mingjia Yang and Doron Zeilberger, <a href="https://arxiv.org/abs/1805.06077">Increasing Consecutive Patterns in Words</a>, arXiv:1805.06077 [math.CO], 2018.
%H Christopher Zhu, <a href="https://arxiv.org/abs/1910.12818">Enumerating Permutations and Rim Hooks Characterized by Double Descent Sets</a>, arXiv:1910.12818 [math.CO], 2019.
%F E.g.f.: 1/Sum_{i>=0} (x^(3*i)/(3*i)! - x^(3*i+1)/(3*i+1)!). [Corrected g.f. --> e.g.f. by _Vaclav Kotesovec_, Feb 15 2015]
%F Equivalently, e.g.f.: exp(x/2) * r / sin(r*x + (2/3)*Pi) where r = sqrt(3)/2. This has simple poles at (3*m+1)*x0 where x0 = Pi/sqrt(6.75) = 1.2092 approximately and m is an arbitrary integer. This yields the asymptotic expansion a(n)/n! ~ x0^(-n-1) * Sum((-1)^m * E^(3*m+1) / (3*m+1)^(n+1)) where E = exp(x0/2) = 1.8305+ and m ranges over all integers. - _Noam D. Elkies_, Nov 15 2001
%F E.g.f.: sqrt(3)*exp(x/2)/(sqrt(3)*cos(x*sqrt(3)/2) - sin(x*sqrt(3)/2) ); a(n+1) = Sum_{k=0..n} binomial(n, k)*a(k)*b(n-k) where b(n) = number of n-permutations without double falls and without initial falls. - _Emanuele Munarini_, Feb 28 2003
%F O.g.f.: A(x) = 1/(1 - x - x^2/(1 - 2*x - 4*x^2/(1 - 3*x - 9*x^2/(1 - ... - n*x - n^2*x^2/(1 - ...))))) (continued fraction). - _Paul D. Hanna_, Jan 17 2006
%F a(n) = leftmost column term of M^n*V, where M = an infinite tridiagonal matrix with (1,2,3,...) in the super, sub, and main diagonals and the rest zeros. V = the vector [1,0,0,0,...]. - _Gary W. Adamson_, Jun 16 2011
%F E.g.f.: A(x)=1/Q(0); Q(k)=1-x/((3*k+1)-(x^2)*(3*k+1)/((x^2)-3*(3*k+2)*(k+1)/Q(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, Nov 25 2011
%F a(n) ~ n! * exp(Pi/(3*sqrt(3))) * (3*sqrt(3)/(2*Pi))^(n+1). - _Vaclav Kotesovec_, Jul 28 2013
%F E.g.f.: T(0)/(1-x), where T(k) = 1 - x^2*(k+1)^2/( x^2*(k+1)^2 - (1-x-x*k)*(1-2*x-x*k)/T(k+1) ); (continued fraction). - _Sergei N. Gladkovskii_, Oct 17 2013
%e Permutations without double increase and without pattern 123:
%e a(3) = 5: 132, 213, 231, 312, 321.
%e a(4) = 17: 1324, 1423, 1432, 2143, 2314, 2413, 2431, 3142, 3214, 3241, 3412, 3421, 4132, 4213, 4231, 4312, 4321.
%p b:= proc(u, o, t) option remember;
%p `if`(u+o=0, 1, add(b(u-j, o+j-1, 0), j=1..u)+
%p `if`(t=1, 0, add(b(u+j-1, o-j, 1), j=1..o)))
%p end:
%p a:= n-> b(n, 0$2):
%p seq(a(n), n=0..23); # _Alois P. Heinz_, Nov 04 2021
%t Table[Simplify[ n! SeriesCoefficient[ Series[ Sqrt[3] Exp[x/2]/(Sqrt[3] Cos[Sqrt[3]/2 x] - Sin[Sqrt[3]/2 x]), {x, 0, n}], n] ], {n, 0, 40}]
%t (* Second program: *)
%t b[u_, o_, t_, k_] := b[u, o, t, k] = If[t == k, (u + o)!, If[Max[t, u] + o < k, 0, Sum[b[u + j - 1, o - j, t + 1, k], {j, 1, o}] + Sum[b[u - j, o + j - 1, 1, k], {j, 1, u}]]];
%t a[n_] := b[0, n, 0, 2] - b[0, n, 0, 3] + 1;
%t a /@ Range[0, 40] (* _Jean-François Alcover_, Nov 09 2020, after _Alois P. Heinz_ in A000303 *)
%Y Cf. A065429, A080635, A111004, A117158, A177523, A177533.
%Y Column k=0 of A162975.
%Y Column k=3 of A242784.
%Y Equals 1 + A000303. - _Greg Dresden_, Feb 22 2020
%K nonn,nice,easy
%O 0,3
%A Tuwani A. Tshifhumulo (tat(AT)caddy.univen.ac.za)
%E Corrected and extended by _Vladeta Jovovic_, Apr 14 2001
|
