login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A080635 Number of permutations on n letters without double falls and without initial falls. 18

%I

%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 a(n) = 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 Increasing colored 1-2 trees of order n with choice of two colors for the right branches of the vertices of out degree 2. - _Wenjin Woan_, May 21 2011

%D Paul Barry, Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices, Journal of Integer Sequences, 19, 2016, #16.3.5.

%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 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 Miklos Bona, Istvan Mezo, <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 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 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 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, 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.

%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( binomial(n, k) * a(k) * a(n-k), k = 0 .. n) - 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 M. 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

%F [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.

%F 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,

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

%F (End)

%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 G.f.: 1 + 1/Q(0), where Q(k)= 1/(x*(k+1)) - 1 - 1/Q(k+1); (continued fraction). - _Sergei N. Gladkovskii_, May 06 2013

%F E.g.f.: 1 + 2*x/(W(0)-x), where W(k)= 4*k + 2 - 3*x^2/W(k+1); (continued fraction). - _Sergei N. Gladkovskii_, May 07 2013

%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) ) ; (continued fraction). - _Sergei N. Gladkovskii_, Sep 23 2013

%F G.f.: 1 + x/Q(0), where Q(k) = 1 - x*(k+1) - x^2*(k+1)*(k+2)/Q(k+1); (continued fraction). - _Sergei N. Gladkovskii_, Oct 01 2013

%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 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) ); (continued fraction). - _Sergei N. Gladkovskii_, Nov 02 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 G.f.: 1 + x/(G(0) -x), where G(k) = 1 + x*(k+1) - x*(k+1)/(1 - x*(k+2)/G(k+1) ); (continued fraction). - _Sergei N. Gladkovskii_, Dec 24 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

%e E.g.f = 1 + x + x^2/2 + x^3/2 + 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

%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 *)

%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

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 23 07:20 EDT 2018. Contains 316520 sequences. (Running on oeis4.)