A080635 - OEIS

%I #194 Jan 11 2025 03:35:31

%S 1,1,1,3,9,39,189,1107,7281,54351,448821,4085883,40533129,435847959,

%T 5045745069,62594829027,828229153761,11644113200031,173331882039141,

%U 2723549731505163,45047085512477049,782326996336904679,14233537708408467549,270733989894887810547

%N Number of permutations on n letters without double falls and without initial falls.

%C 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 exp(x*(1-y+y^2)*D_y)*f(y)|_{y=0} = f(1-E(-x)) for any function f with a Taylor series. D_y means differentiation with respect to y and E(x) is the e.g.f. given below. For a proof of exp(x*g(y)*D_y)*f(y) = f(F^{-1}(x+F(y))) with the compositional inverse F^{-1} of F(y)=int(1/g(y),y) with F(0)=0 see, e.g., the Datolli et al. reference.

%C Number of increasing ordered trees on vertex set {1,2,...,n}, rooted at 1, in which all outdegrees are <= 2. - _David Callan_, Mar 30 2007

%C Number of increasing colored 1-2 trees of order n with choice of two colors for the right branches of the vertices of outdegree 2. - _Wenjin Woan_, May 21 2011

%H Alois P. Heinz, <a href="/A080635/b080635.txt">Table of n, a(n) for n = 0..464</a>

%H M. Aigner, <a href="http://dx.doi.org/10.1007/978-88-470-2107-5_15">Catalan and other numbers: a recurrent theme</a>, Algebraic combinatorics and computer science, 347-390, Springer Italia, Milan, 2001.

%H Cyril Banderier et al., <a href="https://arxiv.org/abs/1609.06473">Explicit formulas for enumeration of lattice paths: basketball and the kernel method</a>, arXiv:1609.06473 [math.CO], 2016. See series expansion p. 35.

%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Barry/barry321.html">Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices</a>, Journal of Integer Sequences, 19, 2016, #16.3.5.

%H F. Bergeron, Ph. Flajolet and B. Salvy, <a href="http://algo.inria.fr/flajolet/Publications/BeFlSa92.pdf">Varieties of increasing trees</a>, preprint.

%H F. Bergeron, Ph. Flajolet and B. Salvy, <a href="http://dx.doi.org/10.1007/3-540-55251-0_2">Varieties of Increasing Trees</a>, in Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.

%H Miklós Bóna and István Mező, <a href="https://arxiv.org/abs/1803.05033">Limiting probabilities for vertices of a given rank in rooted trees</a>, arXiv:1803.05033 [math.CO], 2018.

%H Miklós Bóna and István Mező, <a href="https://doi.org/10.37236/7731">Limiting Probabilities for Vertices of a Given Rank in 1-2 Trees</a>, The Electronic Journal of Combinatorics (2019) Vol. 26, No. 3, P#3.41.

%H Daniel Chen, <a href="https://arxiv.org/abs/2308.14635">Expected Number of Dice Rolls Until an Increasing Run of Three</a>, arXiv:2308.14635 [math.CO], 2023. See p. 17.

%H G. Datolli, P. L. Ottaviani, A. Torre and L. Vazquez, <a href="http://dx.doi.org/10.1007/BF02907529">Evolution operator equations: integration with algebraic and finite differences methods.[...]</a>, La Rivista del Nuovo Cimento 20,2 (1997) 1-133. eq. (I.2.18).

%H Colin Defant, <a href="https://arxiv.org/abs/2004.11367">Troupes, Cumulants, and Stack-Sorting</a>, arXiv:2004.11367 [math.CO], 2020.

%H R. Ehrenborg, <a href="https://arxiv.org/abs/1312.2051">Cyclically consecutive permutation avoidance</a>, arXiv:1312.2051 [math.CO], 2013.

%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-125.

%H M. E. Jones and J. B. Remmel, <a href="http://puma.dimai.unifi.it/22_2/jones_remmel.pdf">Pattern matching in the cycle structures of permutations</a>, Pure Math. Appl. (PU.M.A.), 22 (2011) 173-208.

%H Kaarel Hänni, <a href="https://math.mit.edu/research/undergraduate/urop-plus/documents/2020/Haenni.pdf">Asymptotics of descent functions</a>, MIT Mathematics UROP+ Papers (2020).

%H Aoife Hennessy, <a href="http://repository.wit.ie/1693/1/AoifeThesis.pdf">A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths</a>, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.

%H Markus Kuba and Alois Panholzer, <a href="http://arxiv.org/abs/1411.4587">Combinatorial families of multilabelled increasing trees and hook-length formulas</a>, arXiv:1411.4587 [math.CO], 2014.

%H Rupert Li, <a href="https://arxiv.org/abs/2107.12353">Vincular Pattern Avoidance on Cyclic Permutations</a>, arXiv:2107.12353 [math.CO], 2021, p. 6.

%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 + 1/sqrt(3) * tan(sqrt(3)/2 * x)) / (1 - 1/sqrt(3) * tan( sqrt(3)/2 * x)).

%F Recurrence: a(n+1) = (Sum_{k=0..n} binomial(n, k) * a(k) * a(n-k)) - a(n) + 0^n.

%F E.g.f.: A(x) satisfies A' = 1 - A + A^2. - _Michael Somos_, Oct 04 2003

%F E.g.f.: E(x) = (3*cos((1/2)*3^(1/2)*x) + (3^(1/2))*sin((1/2)*3^(1/2)*x))/(3*cos((1/2)*3^(1/2)*x) - (3^(1/2))* sin((1/2)*3^(1/2)*x)). See the Michael Somos comment. - _Wolfdieter Lang_, Sep 12 2005

%F O.g.f.: A(x) = 1+x/(1-x-2*x^2/(1-2*x-2*3*x^2/(1-3*x-3*4*x^2/(1-... -n*x-n*(n+1)*x^2/(1- ...))))) (continued fraction). - _Paul D. Hanna_, Jan 17 2006

%F From _Peter Bala_: (Start)

%F An alternative form of the e.g.f. for this sequence taken from [Bergeron et al.] is

%F (1)... (sqrt(3)/2)*tan((sqrt(3)/2)*x+Pi/6) [with constant term 1/2].

%F By comparing the egf for this sequence with the egf for the Eulerian numbers A008292 we can show that

%F (2)... a(n) = A(n,w)/(1+w)^(n-1) for n >= 1,

%F where w = exp(2*Pi*i/3) and {A(n,x),n>=1} = [1, 1+x, 1+4*x+x^2, 1+11*x+11*x^2+x^3,...] denotes the sequence of Eulerian polynomials. Equivalently,

%F (3)... a(n) = (-i*sqrt(3))^(n-1)*Sum_{k=1..n} k!*Stirling2(n,k)*(-1/2 + sqrt(3)*i/6)^(k-1) for n >= 1, and

%F (4)... a(n) = (-i*sqrt(3))^(n-1)*Sum_{k=1..n} (-1/2 + sqrt(3)*i/6)^(k-1)* Sum_{j=0..k} (-1)^(k-j)*binomial(k,j)*j^n for n >= 1.

%F This explicit formula for a(n) may be used to obtain various congruence results. For example,

%F (5a)... a(p) == 1 (mod p) for prime p = 6*n+1,

%F (5b)... a(p) == -1 (mod p) for prime p = 6*n+5.

%F For the corresponding results for the case of non-plane unary-binary trees see A000111. For type B results see A001586. For a related sequence of polynomials see A185415. See also A185416 for a recursive method to compute this sequence. For forests of plane increasing unary binary trees see A185422 and A185423. (End)

%F O.g.f.: A(x) = x - (1/2)*x^2 + (1/2)*x^3 - (3/8)*x^4 + (13/40)*x^5 - (21/80)*x^6 + (123/560)*x^7 - (809/4480)*x^8 + (671/4480)*x^9 - (5541/44800)*x^10 + .... - _Vladimir Kruchinin_, Jan 18 2011

%F Let f(x) = 1+x+x^2. Then a(n+1) = (f(x)*d/dx)^n f(x) evaluated at x = 0. - _Peter Bala_, Oct 06 2011

%F From _Sergei N. Gladkovskii_, May 06 2013 - Dec 24 2013: (Start)

%F Continued fractions:

%F G.f.: 1 + 1/Q(0), where Q(k) = 1/(x*(k+1)) - 1 - 1/Q(k+1).

%F E.g.f.: 1 + 2*x/(W(0)-x), where W(k) = 4*k + 2 - 3*x^2/W(k+1).

%F G.f.: 1 + x/Q(0), m=1, where Q(k) = 1 - m*x*(2*k+1) - m*x^2*(2*k+1)*(2*k+2)/( 1 - m*x*(2*k+2) - m*x^2*(2*k+2)*(2*k+3)/Q(k+1) ).

%F G.f.: 1 + x/Q(0), where Q(k) = 1 - x*(k+1) - x^2*(k+1)*(k+2)/Q(k+1).

%F G.f.: 1 + T(0)*x/(1-x), where T(k) = 1 - x^2*(k+1)*(k+2)/( x^2*(k+1)*(k+2) - (1-x*(k+1))*(1-x*(k+2))/T(k+1) ).

%F G.f.: 1 + x/(G(0)-x), where G(k) = 1 + x*(k+1) - x*(k+1)/(1 - x*(k+2)/G(k+1) ). (End)

%F a(n) ~ 3^(3*(n+1)/2) * n^(n+1/2) / (exp(n)*(2*Pi)^(n+1/2)). - _Vaclav Kotesovec_, Oct 05 2013

%F a(n) = n! * Sum_{k=-oo..oo} (sqrt(3)/(2*Pi*(k+1/3)))^(n+1) for n >= 1. - _Richard Ehrenborg_, Dec 09 2013

%F From _Peter Bala_, Sep 11 2015: (Start)

%F The e.g.f. A(x) = (sqrt(3)/2)*tan((sqrt(3)/2)*x + Pi/6) satisfies the differential equation A"(x) = 2*A(x)*A'(x) with A(0) = 1/2 and A'(0) = 1, leading to the recurrence a(0) = 1/2, a(1) = 1, else a(n) = 2*Sum_{i = 0..n-2} binomial(n-2,i)*a(i)*a(n-1-i) for the sequence [1/2, 1, 1, 3, 9, 39, 189, 1107, ...].

%F Note, the same recurrence, but with the initial conditions a(0) = 1 and a(1) = 1, produces the sequence n! and with a(0) = 0 and a(1) = 1 produces A000182. Cf. A002105, A234797. (End)

%F E.g.f.: exp( Series_Reversion( Integral 1/(2*cosh(x) - 1) dx ) ). - _Paul D. Hanna_, Feb 22 2016

%F a(n) = Sum_{k=1..n} (-3)^((n-k)/2)*((-1)^(n-k)+1)*Sum_{j=0..n-k} C(j+k-1,j)*(j+k)!*2^(-j-k)*(-1)^j*Stirling2(n,j+k),n>0, a(0)=1. - _Vladimir Kruchinin_, Feb 13 2019

%F For n > 0, a(n) = 3^((n+1)/2) * n! * (zeta(n+1, 1/3) - (-1)^n*zeta(n+1, 2/3)) / (2*Pi)^(n+1). - _Vaclav Kotesovec_, Aug 06 2021

%e E.g.f. = 1 + x + (1/2)*x^2 + (1/2)*x^3 + (3/8)*x^4 + (13/40)*x^5 + (21/80)*x^6 + ...

%e G.f. = 1 + x + x^2 + 3*x^3 + 9*x^4 + 39*x^5 + 189*x^6 + 1107*x^7 + ...

%e For n = 3: 123, 132, 231. For n = 4: 1234, 1243, 1324, 1342, 1423, 2314, 2341, 2413, 3412.

%e a(4)=9. The 9 plane (ordered) increasing unary-binary trees are

%e ...................................................................

%e ..4................................................................

%e ..|................................................................

%e ..3..........4...4...............4...4...............3...3.........

%e ..|........./.....\............./.....\............./.....\........

%e ..2....2...3.......3...2...3...2.......2...3...4...2.......2...4...

%e ..|.....\./.........\./.....\./.........\./.....\./.........\./....

%e ..1......1...........1.......1...........1.......1...........1.....

%e ...................................................................

%e ..3...4...4...3....................................................

%e ...\./.....\./.....................................................

%e ....2.......2......................................................

%e ....|.......|......................................................

%e ....1.......1......................................................

%e ...................................................................

%p a:= proc(n) if n < 2 then 1 else n! * sum((sqrt(3)/(2*Pi*(k+1/3)))^(n+1), k=-infinity..infinity) fi end: seq(a(n), n=0..30); # _Richard Ehrenborg_, Dec 09 2013

%p a := proc(n) option remember; local k; if n < 3 then 1 else

%p add(binomial(n-1, k)*a(k)*a(n-k-1), k = 0..n-2) fi end:

%p seq(a(n), n = 0..23); # _Peter Luschny_, May 24 2024

%t Table[n!, {n, 0, 40}]*CoefficientList[Series[ (1 + 1/Sqrt[3] Tan[Sqrt[3]/2 x])/(1 - 1/Sqrt[3] Tan[Sqrt[3]/2 x]), {x, 0, 40}], x]

%t a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ 1/2 + Sqrt[3]/2 Tan[ Pi/6 + Sqrt[3] x/2], {x, 0, n}]]; (* _Michael Somos_, May 22 2011 *)

%t Join[{1}, FullSimplify[Table[3^((n+1)/2) * n! * (Zeta[n+1, 1/3] - (-1)^n*Zeta[n+1, 2/3]) / (2*Pi)^(n+1), {n, 1, 20}]]] (* _Vaclav Kotesovec_, Aug 06 2021 *)

%o (PARI) {a(n) = my(A); if( n<1, n==0, A = O(x); for( k=1, n, A = intformal( 1 + A + A^2)); n! * polcoeff( A, n))}; /* _Michael Somos_, Oct 04 2003 */

%o (Sage)

%o @CachedFunction

%o def c(n,k) :

%o     if n==k: return 1

%o     if k<1 or k>n: return 0

%o     return ((n-k)//2+1)*c(n-1,k-1)+2*k*c(n-1,k+1)

%o def A080635(n):

%o     return add(c(n,k) for k in (0..n))

%o [A080635(n) for n in (0..23)] # _Peter Luschny_, Jun 10 2014

%o (PARI) {a(n) = n! * polcoeff( exp( serreverse( intformal( 1/(2*cosh(x +x*O(x^n)) - 1) ) )), n)}

%o for(n=0, 30, print1(a(n), ", ")) \\ _Paul D. Hanna_, Feb 22 2016

%o (Maxima)

%o a(n):=if n=0 then 1 else sum((-3)^((n-k)/2)*((-1)^(n-k)+1)*sum(binomial(j+k-1,j)*(j+k)!*2^(-j-k)*(-1)^(j)*stirling2(n,j+k),j,0,n-k),k,1,n); /* _Vladimir Kruchinin_, Feb 13 2019 */

%Y Cf. A049774, A185415, A185416, A185422, A185423, A139605, A232864.

%Y Cf. A000182, A002105, A234797.

%Y Column k=0 of A162976.

%K nonn,easy

%O 0,4

%A _Emanuele Munarini_, Feb 28 2003

%E Several typos corrected by _Olivier Gérard_, Mar 26 2011