login
Number of permutations in the symmetric group S_n in which cycle lengths are odd and greater than 1.
6

%I #31 Jan 18 2024 12:06:40

%S 1,0,0,2,0,24,40,720,2688,42560,245376,4072320,31672960,569935872,

%T 5576263680,109492807424,1290701905920,27616577064960,380852962029568,

%U 8845627365089280,139696582370328576,3506062524305162240,62387728088875499520,1684340707284076756992

%N Number of permutations in the symmetric group S_n in which cycle lengths are odd and greater than 1.

%H Alois P. Heinz, <a href="/A130915/b130915.txt">Table of n, a(n) for n = 0..450</a> (terms n = 1..200 from Vincenzo Librandi)

%F E.g.f.: exp(-x)*sqrt((1+x)/(1-x)).

%F a(n) ~ 2*n^n/exp(n+1). - _Vaclav Kotesovec_, Oct 08 2013

%F a(n) = (-1)^n*Sum_{k = 0..n} (1 if n = k, otherwise (-1)^(n + k)*(n - k)!*Sum_{i = 1..n - k} Sum_{j = i..n - k} 2^(j - i)*Stirling1(j, i)*binomial(n - k - 1, j - 1)/j!*binomial(n, k)). - _Detlef Meya_, Jan 18 2024

%F a(n) = (n-1)*(n-2)*(a(n-2)+a(n-3)) for n>=3. - _Alois P. Heinz_, Jan 18 2024

%e a(3)=2 because we have (123) and (132).

%p g:=exp(-x)*sqrt((1+x)/(1-x)): gser:=series(g,x=0,30): seq(factorial(n)*coeff(gser,x,n),n=0..20); # _Emeric Deutsch_, Aug 25 2007

%p # second Maple program:

%p a:= proc(n) option remember;

%p `if`(n<3, 1/2, a(n-2)+a(n-3))*(n-1)*(n-2)

%p end:

%p seq(a(n), n=0..30); # _Alois P. Heinz_, Jan 18 2024

%t nn=20;Drop[Range[0,nn]!CoefficientList[Series[((1+x)/(1-x))^(1/2)Exp[-x],{x,0,nn}],x],1] (* _Geoffrey Critzer_, Dec 15 2012 *)

%t a[n_] := (-1)^n*Sum[If[n==k, 1, (-1)^(n + k)*(n - k)!*Sum[Sum[2^(j - i)*StirlingS1[j, i]*Binomial[n - k - 1, j - 1]/j!, {j, i, n - k}], {i, 1, n - k}]*Binomial[n, k]], {k, 0, n}]; Flatten[Table[a[n], {n, 1, 20}]] (* _Detlef Meya_, Jan 18 2024 *)

%o (PARI) my(x='x+O('x^33)); Vec(serlaplace(exp(-x)*sqrt((1+x)/(1-x)))) \\ _Joerg Arndt_, Jan 18 2024

%Y Cf. A000246, A000166.

%K easy,nonn

%O 0,4

%A _Vladeta Jovovic_, Aug 23 2007

%E More terms from _Emeric Deutsch_, Aug 25 2007

%E a(0)=1 prepended by _Alois P. Heinz_, Jan 18 2024