# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a049774
Showing 1-1 of 1

%I A049774 #146 Jun 12 2022 06:42:27
%S A049774 1,1,2,5,17,70,349,2017,13358,99377,822041,7477162,74207209,797771521,
%T A049774 9236662346,114579019469,1516103040833,21314681315998,317288088082405,
%U A049774 4985505271920097,82459612672301846,1432064398910663705,26054771465540507273,495583804405888997218
%N A049774 Number of permutations of n elements not containing the consecutive pattern 123.
%C A049774 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 A049774 Hankel transform is A055209. - _Paul Barry_, Jan 12 2009
%C A049774 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 A049774 F. N. David and D. E. Barton, Combinatorial Chance, Hafner, New York, 1962, pp. 156-157.
%D A049774 I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983, (5.2.17).
%H A049774 Alois P. Heinz, <a href="/load/view.php?a=aHR0cDovL29laXMub3JnL0EwNDk3NzQvYjA0OTc3NC50eHQ">Table of n, a(n) for n = 0..464</a> (first 201 terms from Ray Chandler)
%H A049774 Martin Aigner, <a href="/load/view.php?a=aHR0cDovL2R4LmRvaS5vcmcvMTAuMTAwNy85NzgtODgtNDcwLTIxMDctNV8xNQ">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 A049774 Juan S. Auli, <a href="/load/view.php?a=aHR0cHM6Ly9zZWFyY2gucHJvcXVlc3QuY29tL29wZW52aWV3LzNmMGNlZjFmYmRiMDE2ZDYxZTE2NDEyZTRiODU1OTY5LzE">Pattern Avoidance in Inversion Sequences</a>, Ph. D. thesis, Dartmouth College, ProQuest Dissertations Publishing (2020), 27964164.
%H A049774 Juan S. Auli, Sergi Elizalde, <a href="/load/view.php?a=aHR0cHM6Ly9hcnhpdi5vcmcvYWJzLzE5MDQuMDI2OTQ">Consecutive Patterns in Inversion Sequences</a>, arXiv:1904.02694 [math.CO], 2019. See Table 1.
%H A049774 Paul Barry, <a href="/load/view.php?a=aHR0cHM6Ly9jcy51d2F0ZXJsb28uY2Evam91cm5hbHMvSklTL1ZPTDE3L0JhcnJ5Mi9iYXJyeTI4MS5odG1s">Constructing Exponential Riordan Arrays from Their A and Z Sequences</a>, Journal of Integer Sequences, 17 (2014), #14.2.6.
%H A049774 Paul Barry, <a href="/load/view.php?a=aHR0cHM6Ly9hcnhpdi5vcmcvYWJzLzE4MDIuMDM0NDM">On a transformation of Riordan moment sequences</a>, arXiv:1802.03443 [math.CO], 2018.
%H A049774 Nicolas Basset, <a href="/load/view.php?a=aHR0cDovL2hhbC11cGVjLXVwZW0uYXJjaGl2ZXMtb3V2ZXJ0ZXMuZnIvZG9jcy8wMC84Ni84OS8xOC9QREYvYXV0cmV2ZXJzaW9ubG9uZ3VlLnBkZg">Counting and generating permutations using timed languages</a>, HAL Id: hal-00820373, 2013.
%H A049774 A. Baxter, B. Nakamura, and D. Zeilberger. <a href="/load/view.php?a=aHR0cDovL3d3dy5tYXRoLnJ1dGdlcnMuZWR1L356ZWlsYmVyZy9tYW1hcmltL21hbWFyaW1odG1sL2F1dG8uaHRtbA">Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes</a>; <a href="/load/view.php?a=aHR0cDovL29laXMub3JnL0EwNDk3NzQvYTA0OTc3NC5wZGY">Local copy</a> [Pdf file only, no active links].
%H A049774 S. Elizalde, <a href="/load/view.php?a=aHR0cHM6Ly9hcnhpdi5vcmcvYWJzL21hdGgvMDUwNTI1NA">Asymptotic enumeration of permutations avoiding generalized patterns</a> arXiv:math/0505254 [math.CO], 2015.
%H A049774 S. Elizalde and M. Noy, <a href="/load/view.php?a=aHR0cDovL2R4LmRvaS5vcmcvMTAuMTAxNi9TMDE5Ni04ODU4KDAyKTAwNTI3LTQ">Consecutive patterns in permutations</a>, Adv. Appl. Math. 30 (2003), 110-123.
%H A049774 Steven Finch, <a href="/load/view.php?a=aHR0cHM6Ly93ZWIuYXJjaGl2ZS5vcmcvd2ViLzIwMTUwNDA1MDYwNjM0L2h0dHA6Ly93d3cucGVvcGxlLmZhcy5oYXJ2YXJkLmVkdS9+c2ZpbmNoL2Nzb2x2ZS9hdi5wZGY">Pattern-Avoiding Permutations</a> [Archived version]
%H A049774 Steven Finch, <a href="/load/view.php?a=aHR0cDovL29laXMub3JnL0EyNDA4ODUvYTI0MDg4NS5wZGY">Pattern-Avoiding Permutations</a> [Cached copy, with permission]
%H A049774 Ira M. Gessel and Yan Zhuang, <a href="/load/view.php?a=aHR0cDovL2FyeGl2Lm9yZy9hYnMvMTQwOC4xODg2">Counting permutations by alternating descents </a>, arXiv:1408.1886 [math.CO], 2014. See Eq. (3). - _N. J. A. Sloane_, Aug 11 2014
%H A049774 Kaarel Hänni, <a href="/load/view.php?a=aHR0cHM6Ly9hcnhpdi5vcmcvYWJzLzIwMTEuMTQzNjA">Asymptotics of descent functions</a>, arXiv:2011.14360 [math.CO], Nov 29 2020, p. 14.
%H A049774 Mingjia Yang and Doron Zeilberger, <a href="/load/view.php?a=aHR0cHM6Ly9hcnhpdi5vcmcvYWJzLzE4MDUuMDYwNzc">Increasing Consecutive Patterns in Words</a>, arXiv:1805.06077 [math.CO], 2018.
%H A049774 Christopher Zhu, <a href="/load/view.php?a=aHR0cHM6Ly9hcnhpdi5vcmcvYWJzLzE5MTAuMTI4MTg">Enumerating Permutations and Rim Hooks Characterized by Double Descent Sets</a>, arXiv:1910.12818 [math.CO], 2019.
%F A049774 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 A049774 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 A049774 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 A049774 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 A049774 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 A049774 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 A049774 a(n) ~ n! * exp(Pi/(3*sqrt(3))) * (3*sqrt(3)/(2*Pi))^(n+1). - _Vaclav Kotesovec_, Jul 28 2013
%F A049774 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 A049774 Permutations without double increase and without pattern 123:
%e A049774 a(3) = 5: 132, 213, 231, 312, 321.
%e A049774 a(4) = 17: 1324, 1423, 1432, 2143, 2314, 2413, 2431, 3142, 3214, 3241, 3412, 3421, 4132, 4213, 4231, 4312, 4321.
%p A049774 b:= proc(u, o, t) option remember;
%p A049774      `if`(u+o=0, 1, add(b(u-j, o+j-1, 0), j=1..u)+
%p A049774      `if`(t=1, 0,   add(b(u+j-1, o-j, 1), j=1..o)))
%p A049774     end:
%p A049774 a:= n-> b(n, 0$2):
%p A049774 seq(a(n), n=0..23);  # _Alois P. Heinz_, Nov 04 2021
%t A049774 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 A049774 (* Second program: *)
%t A049774 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 A049774 a[n_] := b[0, n, 0, 2] - b[0, n, 0, 3] + 1;
%t A049774 a /@ Range[0, 40] (* _Jean-François Alcover_, Nov 09 2020, after _Alois P. Heinz_ in A000303 *)
%Y A049774 Cf. A065429, A080635, A111004, A117158, A177523, A177533.
%Y A049774 Column k=0 of A162975.
%Y A049774 Column k=3 of A242784.
%Y A049774 Equals 1 + A000303. - _Greg Dresden_, Feb 22 2020
%K A049774 nonn,nice,easy
%O A049774 0,3
%A A049774 Tuwani A. Tshifhumulo (tat(AT)caddy.univen.ac.za)
%E A049774 Corrected and extended by _Vladeta Jovovic_, Apr 14 2001

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE