A157253 Arises in combinatorial approach to the power of 2 in the number of involutions.

1, 1, 1, 2, 2, 6, 8, 26, 41, 145, 253, 978, 1858, 7726, 15796, 69878, 152219, 711243, 1638323, 8039510, 19467494, 99862594, 252998224, 1351486758, 3568259503, 19786100599, 54263159347, 311482467134, 884834059454, 5245588599330, 15397757661092

Offset

0,4

Comments

Table 1 of Kim and Kim.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..200

Dongsu Kim and Jang Soo Kim, A combinatorial approach to the power of 2 in the number of involutions, arXiv:0902.4311 [math.CO], 2009-2010.

Formula

a(2*n) = a(2*n-2) + (n-1)*a(2*n-3) + 2*binomial(n-1, 2)*a(2*n-4) + 3*binomial(n-1, 3)*a(2*n-8); a(2*n+1) = a(2*n) + n*a(2*n-1). See eqn. 5 and 6 for g_n(1,1) in Kim and Kim reference. - Andrew Howroyd, May 07 2023

Prog

(PARI)
seq(n)={my(a=vector(n+1)); a[1]=a[2]=1; for(n=2, n, a[n+1] = if(n%2==0, a[n-1] + if(n>=3, (n/2-1)*a[n-2]) + if(n>=4, 2*binomial(n/2-1, 2)*a[n-3]) + if(n>=8, 3*binomial(n/2-1, 3)*a[n-7]), a[n] + (n-1)*a[n-1]/2)); a} \\ Andrew Howroyd, May 06 2023

Crossrefs

Sequence in context: A275441 A197465 A074933 * A003178 A079494 A169970

Adjacent sequences: A157250 A157251 A157252 * A157254 A157255 A157256

Keyword

nonn

Author

Jonathan Vos Post, Feb 25 2009

Extensions

a(7)-a(21) from Kim paper by Michel Marcus, Sep 04 2014

Missing a(19) inserted and more terms from Andrew Howroyd, May 06 2023

Status

approved