|
|
A177251
|
|
Number of permutations of [n] having no adjacent 3-cycles, i.e., no cycles of the form (i, i+1, i+2).
|
|
14
|
|
|
1, 1, 2, 5, 22, 114, 697, 4923, 39612, 357899, 3588836, 39556420, 475392841, 6187284605, 86701097310, 1301467245329, 20835850494474, 354382860600678, 6381494425302865, 121290065781743383, 2426510081356069016, 50969474697328055063, 1121571023472780698152
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
lim_{n->inf} a(n)/n! = 1.
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum_{j=0..floor(n/3)} (-1)^j*(n-2*j)!/j!.
a(n) - na(n-1) = 2a(n-3) + 3*(-1)^{n/3} if 3 | n; a(n) - na(n-1) = 2a(n-3) otherwise.
The o.g.f. g(z) satisfies z^2*(1+z^3)*g'(z) - (1+z^3)(1-z-2z^3)g(z) + 1 - 2z^3 = 0; g(0)=1.
G.f.: hypergeom([1,1],[],x/(1+x^3))/(1+x^3). - Mark van Hoeij, Nov 08 2011
D-finite with recurrence a(n) -n*a(n-1) -a(n-3) +(-n+3)*a(n-4) -2a(n-6)=0. - R. J. Mathar, Jul 26 2022
|
|
EXAMPLE
|
a(4)=22 because the only permutations of {1,2,3,4} having adjacent 3-cycles are (123)(4) and (1)(234).
|
|
MAPLE
|
a := proc (n) options operator, arrow: sum((-1)^j*factorial(n-2*j)/factorial(j), j = 0 .. floor((1/3)*n)) end proc: seq(a(n), n = 0 .. 22);
|
|
MATHEMATICA
|
a[n_] := Sum[(-1)^j*(n - 2*j)!/j!, {j, 0, n/3}];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|