|
| |
|
|
A080635
|
|
Number of permutations on n letters without double falls and without initial falls.
|
|
12
| |
|
|
1, 1, 1, 3, 9, 39, 189, 1107, 7281, 54351, 448821, 4085883, 40533129, 435847959, 5045745069, 62594829027, 828229153761, 11644113200031, 173331882039141, 2723549731505163, 45047085512477049, 782326996336904679
(list; graph; refs; listen; history; 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).
E.g.f. A(x) satisfies A' = 1 - A + A^2. - Michael Somos, Oct 04 2003
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 (callan(AT)stat.wisc.edu), Mar 30 2007
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+... [From Vladimir Kruchinin, Jan 18 2011]
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
| 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, in Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1922, pp. 24-48.
G. Datolli, P. L. Ottaviani, A. Torre and L. V\'azquez, Evolution operator equations: integration with algebraic and finite differences methods.[...], Rivista del Nuovo Cimento 20,2 (1997) 1-133. eq. (I.2.18).
|
|
|
LINKS
| F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of increasing trees
|
|
|
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.: 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. W. Lang (wolfdieter.lang_AT_physik_DOT_uni-karlsruhe_DOT_de), 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 (pauldhanna(AT)juno.com), 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]
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
|
|
|
EXAMPLE
| E.g.f = 1 + x + x^2/2 + x^3/2 + 3/8*x^4 + 13/40*x^5 + 21/80*x^6 + ...
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......................................................
...................................................................
|
|
|
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) = local(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 */
|
|
|
CROSSREFS
| Cf. A049774, A185415, A185416, A185422, A185423.
Cf. A139605
Sequence in context: A149027 A180741 A121101 * A130905 A030799 A058105
Adjacent sequences: A080632 A080633 A080634 * A080636 A080637 A080638
|
|
|
KEYWORD
| nonn,easy
|
|
|
AUTHOR
| Emanuele Munarini (munarini(AT)mate.polimi.it), Feb 28 2003
|
|
|
EXTENSIONS
| Several typos corrected by Olivier Gérard (olivier.gerard(AT)gmail.com), Mar 26 2011
|
| |
|
|
