|
|
A163951
|
|
The number of functions in a finite set for which the sequence of composition powers ends in a length 2 cycle.
|
|
5
|
|
|
0, 0, 1, 9, 93, 1155, 17025, 292383, 5752131, 127790505, 3167896005, 86756071545, 2602658092419, 84917405260779, 2994675198208785, 113538315994418175, 4606094297461892895, 199122610252964803857, 9139190793845641425261, 443881600924216704982425
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
The number of functions in a finite set {1,..,n} for which the sequence of composition powers ends in a fixed point gave terms of the sequence A000272(n-1)=(n+1)^(n-1).
This is to be seen as a conjecture, and the sequence ending with a length 2 cycle does not seem to have such an easy expression.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
Any transposition (or disjoint combination) is one element to be counted.
When n=2, there is only one, and a(2)=1. When n=3, there are only 3 transpositions, but there are other 6 elements, for instance
f:{1,2,3}->{2,1,1} gives fof:{1,2,3}->{1,2,2} and fofof=f (cycle 2),
(the others are similar), thus giving a(3)=9.
|
|
MAPLE
|
with(combinat):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
add((i-1)!^j*multinomial(n, n-i*j, i$j)/j!*
b(n-i*j, i-1), j=0..n/i)))
end:
A:= (n, k)-> add(binomial(n-1, j-1)*n^(n-j)*b(j, min(j, k)), j=0..n):
a:= n-> A(n, 2) -A(n, 1):
|
|
MATHEMATICA
|
multinomial[n_, k_List] := n!/Times @@ (k!);
b[n_, i_] := b[n, i] = If[n == 0, 1, If[i<1, 0, Sum[(i - 1)!^j*multinomial[ n, Join[{n - i*j}, Table[i, j]]]/j!*b[n - i*j, i - 1], {j, 0, n/i}]]];
A[n_, k_] := Sum[Binomial[n-1, j-1]*n^(n-j)*b[j, Min[j, k]], {j, 0, n}];
a[0] = 0; a[n_] := A[n, 2] - A[n, 1];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|