|
|
A177253
|
|
Number of permutations of [n] having no adjacent 4-cycles, i.e., no cycles of the form (i, i+1, i+2, i+3).
|
|
7
|
|
|
1, 1, 2, 6, 23, 118, 714, 5016, 40201, 362163, 3623772, 39876540, 478639079, 6223394516, 87138394540, 1307195547720, 20916564680761, 355600269756485, 6401066270800350, 121624180731849810, 2432546364331038479, 51084540451761077514, 1123879093137556106358
(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/4)} (-1)^j*(n-3*j)!/j!.
a(n) - n*a(n-1) = 3a(n-4) + 4*(-1)^{n/4} if 4|n; a(n) - n*a(n-1) = 3a(n-4) otherwise.
The o.g.f. g(z) satisfies z^2*(1+z^4)*g'(z) - (1+z^4)(1-z-3z^4)g(z) + 1 - 3z^4 = 0; g(0)=1.
D-finite with recurrence a(n) -n*a(n-1) -2*a(n-4) +(-n+4)*a(n-5) -3*a(n-8)=0. - R. J. Mathar, Jul 26 2022
|
|
EXAMPLE
|
a(5)=118 because the only permutations of {1,2,3,4,5} having adjacent 4-cycles are (1234)(5) and (1)(2345).
|
|
MAPLE
|
a := proc (n) options operator, arrow: sum((-1)^j*factorial(n-3*j)/factorial(j), j = 0 .. floor((1/4)*n)) end proc: seq(a(n), n = 0 .. 22);
|
|
MATHEMATICA
|
a[n_] := Sum[(-1)^j*(n - 3*j)!/j!, {j, 0, n/4}];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|