A140456 a(n) is the number of indecomposable involutions of length n.

1, 1, 1, 3, 7, 23, 71, 255, 911, 3535, 13903, 57663, 243871, 1072031, 4812575, 22278399, 105300287, 510764095, 2527547455, 12794891007, 66012404863, 347599231103, 1863520447103, 10178746224639, 56548686860543, 319628408814847, 1835814213846271

Offset: 1

Author

Joel B. Lewis, Jul 22 2008

Keywords

• nonn

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

Examples

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

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.

Crossrefs

Cf. A000085 (involutions), A000698 (indecomposable fixed-point free involutions), and A003319 (indecomposable permutations).

Cf. A001006, A258306.

Programs

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]

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