A246552 2-adic valuation of the number of involutions of n (A000085).

0, 0, 1, 2, 1, 1, 2, 3, 2, 2, 3, 4, 3, 3, 4, 5, 4, 4, 5, 6, 5, 5, 6, 7, 6, 6, 7, 8, 7, 7, 8, 9, 8, 8, 9, 10, 9, 9, 10, 11, 10, 10, 11, 12, 11, 11, 12, 13, 12, 12, 13, 14, 13, 13, 14, 15, 14, 14, 15, 16, 15, 15, 16, 17, 16, 16, 17, 18, 17, 17, 18, 19, 18, 18, 19, 20, 19, 19, 20, 21, 20, 20, 21, 22, 21, 21, 22, 23, 22, 22, 23

Offset: 0

Author

Joerg Arndt, Sep 06 2014

Keywords

• nonn
• easy

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (1,0,0,1,-1).

Crossrefs

Cf. A000085 (involutions).

Cf. A011371 (2-adic valuation of n!), A007814 (2-adic valuation of derangements (A000166)).

Programs

Magma

I:=[0, 0, 1, 2, 1]; [n le 5 select I[n] else Self(n-1)+Self(n-4)-Self(n-5): n in [1..100]]; // Vincenzo Librandi, Sep 06 2014

Maple

seq(n-2*floor(n/4)-floor((n+3)/4), n=0..100) ; # Ridouane Oudra, Dec 11 2023

Mathematica

CoefficientList[Series[x^2 (1 + x - x^2)/((1 - x)^2 (1 + x) (1 + x^2)), {x, 0, 100}], x] (* Vincenzo Librandi, Sep 06 2014 *)
LinearRecurrence[{1,0,0,1,-1},{0,0,1,2,1},100] (* Harvey P. Dale, Jun 13 2016 *)

PARI

N=166; x='x+O('x^N);
v=Vec(serlaplace(exp(x+x^2/2)));
vector(#v,n,valuation(v[n],2))

PARI

concat([0,0],Vec(x^2*(1+x-x^2)/((1-x)^2*(1+x)*(1+x^2))+O(x^166)))

PARI

a(n) = (3 - (-1)^n - (1+3*I)*(-I)^n - (1-I*3)*I^n + 2*n)/8 \\ Colin Barker, Oct 16 2015

Formula

a(n) = a(n-1) + a(n-4) - a(n-5).

G.f.: x^2*(1+x-x^2)/((1-x)^2*(1+x)*(1+x^2)).

a(n) = (3 - (-1)^n - (1+3*i)*(-i)^n - (1-i*3)*i^n + 2*n)/8 where i=sqrt(-1). - Colin Barker, Oct 16 2015

a(n) = (2*n+3-2*cos(n*Pi/2)-cos(n*Pi)-6*sin(n*Pi/2))/8. - Wesley Ivan Hurt, Oct 01 2017

a(n) = n - 2*floor(n/4) - floor((n+3)/4). - Ridouane Oudra, Dec 11 2023