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
1, 1, 1, 3, 9, 39, 189, 1107, 7281, 54351, 448821, 4085883, 40533129, 435847959, 5045745069, 62594829027, 828229153761, 11644113200031, 173331882039141, 2723549731505163, 45047085512477049, 782326996336904679, 14233537708408467549, 270733989894887810547 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

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).

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.

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

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

REFERENCES

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

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..464

M. Aigner, Catalan and other numbers: a recurrent theme, Algebraic combinatorics and computer science, 347-390, Springer Italia, Milan, 2001.

F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of increasing trees, preprint.

F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of Increasing Trees, in Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.

Cyril Banderier et al., Explicit formulas for enumeration of lattice paths: basketball and the kernel method, arXiv:1609.06473 [math.CO], 2016. See series expansion p. 35.

G. Datolli, P. L. Ottaviani, A. Torre and L. Vazquez, Evolution operator equations: integration with algebraic and finite differences methods.[...], La Rivista del Nuovo Cimento 20,2 (1997) 1-133. eq. (I.2.18).

R. Ehrenborg, Cyclically consecutive permutation avoidance, arXiv:1312.2051 [math.CO], 2013

S. Elizalde and M. Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110-125.

M. E. Jones and J. B. Remmel, Pattern matching in the cycle structures of permutations, Pure Math. Appl. (PU.M.A.), 22 (2011) 173-208.

Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.

Markus Kuba, Alois Panholzer, Combinatorial families of multilabelled increasing trees and hook-length formulas, arXiv:1411.4587 [math.CO], 2014.

FORMULA

E.g.f.: ( 1 + 1/sqrt(3) * tan( sqrt(3)/2 * x) ) / ( 1 - 1/sqrt(3) * tan( sqrt(3)/2 * x) ).

Recurrence: a(n+1) = sum( binomial(n, k) * a(k) * a(n-k), k = 0 .. n) - a(n) + 0^n.

E.g.f.: A(x) satisfies A' = 1 - A + A^2. - Michael Somos, Oct 04 2003

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.

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.

From Peter Bala: (Start)

An alternative form of the e.g.f. for this sequence taken from

[BERGERON et al.] is

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

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

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

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,

(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

(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.

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

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

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

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)

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

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

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

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

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

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

a(n) ~ 3^(3*(n+1)/2) * n^(n+1/2) / (exp(n)*(2*Pi)^(n+1/2)). - Vaclav Kotesovec, Oct 05 2013

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

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

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

From Peter Bala, Sep 11 2015: (Start)

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, ...].

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)

E.g.f.: exp( Series_Reversion( Integral 1/(2*cosh(x) - 1) dx ) ). - Paul D. Hanna, Feb 22 2016

EXAMPLE

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

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

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

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

...................................................................

..4................................................................

..|................................................................

..3..........4...4...............4...4...............3...3.........

..|........./.....\............./.....\............./.....\........

..2....2...3.......3...2...3...2.......2...3...4...2.......2...4...

..|.....\./.........\./.....\./.........\./.....\./.........\./....

..1......1...........1.......1...........1.......1...........1.....

...................................................................

..3...4...4...3....................................................

...\./.....\./.....................................................

....2.......2......................................................

....|.......|......................................................

....1.......1......................................................

...................................................................

MAPLE

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

MATHEMATICA

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]

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

PROG

(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 */

(Sage)

@CachedFunction

def c(n, k) :

    if n==k: return 1

    if k<1 or k>n: return 0

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

def A080635(n):

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

[A080635(n) for n in (0..23)] # Peter Luschny, Jun 10 2014

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

for(n=0, 30, print1(a(n), ", ")) \\ Paul D. Hanna, Feb 22 2016

CROSSREFS

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

Cf. A000182, A002105, A234797.

Column k=0 of A162976.

Sequence in context: A121101 A280066 A287063 * A278749 A208816 A130905

Adjacent sequences:  A080632 A080633 A080634 * A080636 A080637 A080638

KEYWORD

nonn,easy

AUTHOR

Emanuele Munarini, Feb 28 2003

EXTENSIONS

Several typos corrected by Olivier Gérard, Mar 26 2011

STATUS

approved

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 February 20 04:19 EST 2018. Contains 299358 sequences. (Running on oeis4.)