A102736 Number of permutations of n elements without cycles whose length is a multiple of 3.

1, 1, 2, 4, 16, 80, 400, 2800, 22400, 179200, 1792000, 19712000, 216832000, 2818816000, 39463424000, 552487936000, 8839806976000, 150276718592000, 2554704216064000, 48539380105216000, 970787602104320000, 19415752042086400000, 427146544925900800000, 9824370533295718400000, 225960522265801523200000, 5649013056645038080000000, 146874339472770990080000000, 3818732826292045742080000000

Offset: 0

Author

Vladeta Jovovic, Feb 08 2005

Keywords

• easy
• nonn

Comments

Differs from A247007 first at n=27. - Alois P. Heinz, Sep 09 2014

Examples

			G.f. = 1 + x + 2*x^2 + 4*x^3 + 16*x^4 + 80*x^5 + 400*x^6 + 2800*x^7 + ...
		

Links

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

Crossrefs

Cf. A000090, A000246.

Programs

Maple

a:= proc(n) option remember; `if`(n=0, 1, add(`if`(
      irem(j, 3)=0, 0, a(n-j)*(j-1)!*binomial(n-1, j-1)), j=1..n))
    end:
seq(a(n), n=0..27);  # Alois P. Heinz, Jul 31 2017

Mathematica

nn=21;a=Sum[x^n/n,{n,3,nn,3}];Range[0,nn]!CoefficientList[Series[Exp[Log[1/(1-x)]-a],{x,0,nn}],x]  (* Geoffrey Critzer, Nov 11 2012 *)
a[ n_] := If[ n < 0, 0, n! With[{m = Quotient[n, 3]}, (-1)^m Binomial[-2/3, m]]]; (* Michael Somos, Aug 05 2016 *)

PARI

{a(n) = my(m); if( n<0, 0, m = n\3; n! * (-1)^m * binomial(-2/3, m))}; /* Michael Somos, Aug 05 2016 */

Formula

E.g.f.: (1-x^3)^(1/3)/(1-x).

a(n) ~ n! * 3^(1/3) / (GAMMA(2/3) * n^(1/3)). - Vaclav Kotesovec, Mar 15 2014