|
| |
|
|
A080635
|
|
Number of permutations on n letters without double falls and without initial falls.
|
|
21
|
|
|
|
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.
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
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
|
|
|
LINKS
|
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.
|
|
|
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_{k=0..n} binomial(n, k) * a(k) * a(n-k)) - 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 Michael 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
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)
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
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
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
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
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
|
|
|
EXAMPLE
|
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 + ...
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 *)
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 *)
|
|
|
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)
return add(c(n, k) for k in (0..n))
(PARI) {a(n) = n! * polcoeff( exp( serreverse( intformal( 1/(2*cosh(x +x*O(x^n)) - 1) ) )), n)}
(Maxima)
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 */
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
