OFFSET
1,4
COMMENTS
An involution is a self-inverse permutation. A permutation of [n] = {1, 2, ..., n} is indecomposable if it does not fix [j] for any 0 < j < n.
From Paul Barry, Nov 26 2009: (Start)
G.f. of a(n+1) is 1/(1-x-2x^2/(1-x-3x^2/(1-x-4x^2/(1-x-5x^2/(1-...))))) (continued fraction).
a(n+1) is the binomial transform of the aeration of A000698(n+1). Hankel transform of a(n+1) is A000178(n+1). (End)
From Groux Roland, Mar 17 2011: (Start)
a(n) is the INVERTi transform of A000085(n+1)
a(n) is also the moment of order n for the density: sqrt(2/Pi^3)*exp((x-1)^2/2)/(1-(erf(I*(x-1)/sqrt(2)))^2).
More generally, if c(n)=int(x^n*rho(x),x=a..b) with rho(x) a probability density function of class C1, then the INVERTi transform of (c(1),..c(n),..) starting at n=2 gives the moments of mu(x) = rho(x) / ((s(x))^2+(Pi*rho(x))^2) with s(x) = int( rho'(t)*log(abs(1-t/x)), t=a..b) + rho(b)*log(x/(b-x)) + rho(a)*log((x-a)/x).
(End)
For n>1 sum over all Motzkin paths of length n-2 of products over all peaks p of (x_p+y_p)/y_p, where x_p and y_p are the coordinates of peak p. - Alois P. Heinz, May 24 2015
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..800 (terms n = 1..50 from Joel B. Lewis)
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.
Claudia Malvenuto and Christophe Reutenauer, Primitive Elements of the Hopf Algebras of Tableaux, arXiv:2010.06731 [math.CO], 2020.
FORMULA
G.f.: 1 - 1/I(x), where I(x) is the ordinary generating function for involutions (A000085).
G.f.: Q(0) +1/x, where Q(k) = 1 - 1/x - (k+1)/Q(k+1) ; (continued fraction). - Sergei N. Gladkovskii, Sep 16 2013
EXAMPLE
The unique indecomposable involution of length 3 is 321. The indecomposable involutions of length 4 are 3412, 4231 and 4321.
G.f. = x + x^2 + 3*x^3 + 7*x^4 + 23*x^5 + 71*x^6 + 255*x^7 + 911*x^8 + ...
MAPLE
b:= proc(x, y, t) option remember; `if`(y>x or y<0, 0,
`if`(x=0, 1, b(x-1, y-1, false)*`if`(t, (x+y)/y, 1)
+ b(x-1, y, false) + b(x-1, y+1, true)))
end:
a:= n-> `if`(n=1, 1, b(n-2, 0, false)):
seq(a(n), n=1..35); # Alois P. Heinz, May 24 2015
MATHEMATICA
CoefficientList[Series[1 - 1/Total[CoefficientList[Series[E^(x + x^2/2), {x, 0, 50}], x] * Range[0, 50]! * x^Range[0, 50]], {x, 0, 50}], x]
CROSSREFS
KEYWORD
nonn
AUTHOR
Joel B. Lewis, Jul 22 2008
STATUS
approved