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

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

Cf. A001006, A258306.

Sequence in context: A148703 A302180 A045723 * A066768 A225914 A062241

Adjacent sequences: A140453 A140454 A140455 * A140457 A140458 A140459

Keyword

nonn

Author

Joel B. Lewis, Jul 22 2008

Status

approved