|
|
A163952
|
|
The number of functions in a finite set for which the sequence of composition powers ends in a length 3 cycle.
|
|
3
|
|
|
0, 0, 0, 2, 32, 480, 7880, 145320, 3009888, 69554240, 1779185360, 49995179520, 1532580072320, 50934256044672, 1825145974743000, 70172455476381440, 2882264153273207360, 125985060813367664640, 5840066736661562391968, 286204501001426735001600
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
See A163951 for the cases ending with length 2 cycles and fixed points.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
Any period 3 permutation (or disjoint combinations) is one element to be counted.
For n=3, where there are only 2 cases: f1:{1,2,3}->{2,3,1} and f2:{1,2,3}->{3,1,2} but for n>3 there are other elements (non-permutations) to be counted (for instance, with n=5, we count with f:{1,2,3,4,5}->{2,4,5,3,4}).
|
|
MAPLE
|
b:= proc(n, m) option remember; `if`(m>3, 0, `if`(n=0, x^m, add(
(j-1)!*b(n-j, ilcm(m, j))*binomial(n-1, j-1), j=1..n)))
end:
a:= n-> coeff(add(b(j, 1)*n^(n-j)*binomial(n-1, j-1), j=0..n), x, 3):
|
|
MATHEMATICA
|
b[n_, m_] := b[n, m] = If[m>3, 0, If[n == 0, x^m, Sum[(j - 1)! b[n - j, LCM[m, j]] Binomial[n - 1, j - 1], {j, 1, n}]]];
a[n_] := If[n==0, 0, Coefficient[Sum[b[j, 1] n^(n-j) Binomial[n-1, j-1], {j, 0, n}], x, 3]];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|