A140456 - OEIS

%I #55 Oct 27 2023 21:45:33

%S 1,1,1,3,7,23,71,255,911,3535,13903,57663,243871,1072031,4812575,

%T 22278399,105300287,510764095,2527547455,12794891007,66012404863,

%U 347599231103,1863520447103,10178746224639,56548686860543,319628408814847,1835814213846271

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

%C 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.

%C From _Paul Barry_, Nov 26 2009: (Start)

%C 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).

%C 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)

%C From _Groux Roland_, Mar 17 2011: (Start)

%C a(n) is the INVERTi transform of A000085(n+1)

%C 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).

%C 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).

%C (End)

%C 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

%H Alois P. Heinz, <a href="/A140456/b140456.txt">Table of n, a(n) for n = 1..800</a> (terms n = 1..50 from Joel B. Lewis)

%H Aoife Hennessy, <a href="http://repository.wit.ie/1693/1/AoifeThesis.pdf">A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths</a>, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.

%H Claudia Malvenuto and Christophe Reutenauer, <a href="https://arxiv.org/abs/2010.06731">Primitive Elements of the Hopf Algebras of Tableaux</a>, arXiv:2010.06731 [math.CO], 2020.

%F G.f.: 1 - 1/I(x), where I(x) is the ordinary generating function for involutions (A000085).

%F 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

%e The unique indecomposable involution of length 3 is 321. The indecomposable involutions of length 4 are 3412, 4231 and 4321.

%e G.f. = x + x^2 + 3*x^3 + 7*x^4 + 23*x^5 + 71*x^6 + 255*x^7 + 911*x^8 + ...

%p b:= proc(x, y, t) option remember; `if`(y>x or y<0, 0,

%p       `if`(x=0, 1, b(x-1, y-1, false)*`if`(t, (x+y)/y, 1)

%p                  + b(x-1, y, false) + b(x-1, y+1, true)))

%p     end:

%p a:= n-> `if`(n=1, 1, b(n-2, 0, false)):

%p seq(a(n), n=1..35);  # _Alois P. Heinz_, May 24 2015

%t 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]

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

%Y Cf. A001006, A258306.

%K nonn

%O 1,4

%A _Joel B. Lewis_, Jul 22 2008