login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A214086 Number of involutions of length n having exactly n inversions. 3
1, 0, 0, 1, 1, 2, 10, 17, 39, 119, 254, 613, 1623, 3791, 9281, 23469, 56823, 140035, 349167, 857868, 2122297, 5274213, 13044870, 32357838, 80421284, 199613489, 496144310, 1234420850, 3070773600, 7644879181, 19044266176, 47450853932, 118290412077, 295019269801 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,6

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..2000

Wikipedia, Inversion

Wikipedia, Involution

FORMULA

a(n) = T(n,n) with T(n,k) = T(n-1,k) + Sum_{j=1..n-1} T(n-2,k-2*(n-j)+1) for n>=0, k>0; T(n,k) = 0 for n<0 or k<0; T(n,0) = 1 for n>=0.

a(n) ~ c * d^n / sqrt(n), where d = 2.529010713480526199368... is the root of the equation 4 - 23*d - 36*d^2 - 8*d^3 + 4*d^5 = 0, c = 0.08933570507578447270759... . - Vaclav Kotesovec, Sep 07 2014

EXAMPLE

a(0) = 1: (), the empty involution.

a(3) = 1: (3,2,1); inversions are (3,2), (3,1), (2,1).

a(4) = 1: (3,4,1,2); inversions are (3,1), (3,2), (4,1), (4,2).

a(5) = 2: (1,5,3,4,2), (4,2,3,1,5).

a(6) = 10: (1,2,6,5,4,3), (1,4,6,2,5,3), (1,5,3,6,2,4), (1,5,4,3,2,6), (2,1,6,4,5,3), (3,2,1,6,5,4), (3,5,1,4,2,6), (4,2,3,1,6,5), (4,2,5,1,3,6), (4,3,2,1,5,6).

MAPLE

T:= proc(n, k) option remember; `if`(n<0 or k<0, 0, `if`(k=0, 1,

      T(n-1, k) + add(T(n-2, k-2*(n-j)+1), j=1..n-1)))

    end:

a:= n-> T(n$2):

seq(a(n), n=0..50);

MATHEMATICA

Table[Count[Map[Inversions, Involutions[n]], n], {n, 1, 10}]

CROSSREFS

Diagonal of A213910.

Cf. A128566.

Sequence in context: A316753 A304809 A304805 * A127492 A258974 A077247

Adjacent sequences:  A214083 A214084 A214085 * A214087 A214088 A214089

KEYWORD

nonn

AUTHOR

Geoffrey Critzer and Alois P. Heinz, Mar 06 2013

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 3 03:03 EST 2021. Contains 341756 sequences. (Running on oeis4.)