login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A140456 a(n) is the number of indecomposable involutions of length n. 6
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 (list; graph; refs; listen; history; text; internal format)
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

Joel B. Lewis and 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 24 04:43 EDT 2022. Contains 354005 sequences. (Running on oeis4.)