|
|
A008307
|
|
Table T(n,k) giving number of permutations of [1..n] with order dividing k, read by antidiagonals.
|
|
18
|
|
|
1, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 10, 3, 2, 1, 1, 26, 9, 4, 1, 1, 1, 76, 21, 16, 1, 2, 1, 1, 232, 81, 56, 1, 6, 1, 1, 1, 764, 351, 256, 25, 18, 1, 2, 1, 1, 2620, 1233, 1072, 145, 66, 1, 4, 1, 1, 1, 9496, 5769, 6224, 505, 396, 1, 16, 3, 2, 1, 1, 35696, 31041, 33616, 1345, 2052, 1, 56, 9, 4, 1, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,5
|
|
COMMENTS
|
Solutions to x^k = 1 in Symm_n (the symmetric group of degree n).
|
|
REFERENCES
|
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 257.
J. D. Dixon, B. Mortimer, Permutation Groups, Springer (1996), Exercise 1.2.13.
|
|
LINKS
|
|
|
FORMULA
|
T(n+1,k) = Sum_{d|k} (n)_(d-1)*T(n-d+1,k), where (n)_i = n!/(n - i)! = n*(n - 1)*(n - 2)*...*(n - i + 1) is the falling factorial.
E.g.f. for n-th row: Sum_{n>=0} T(n,k)*t^n/n! = exp(Sum_{d|k} t^d/d).
|
|
EXAMPLE
|
Array begins:
1, 1, 1, 1, 1, 1, 1, 1, ...
1, 2, 1, 2, 1, 2, 1, 2, ...
1, 4, 3, 4, 1, 6, 1, 4, ...
1, 10, 9, 16, 1, 18, 1, 16, ...
1, 26, 21, 56, 25, 66, 1, 56, ...
1, 76, 81, 256, 145, 396, 1, 256, ...
1, 232, 351, 1072, 505, 2052, 721, 1072, ...
1, 764, 1233, 6224, 1345, 12636, 5761, 11264, ...
|
|
MAPLE
|
A:= proc(n, k) option remember; `if`(n<0, 0, `if`(n=0, 1,
add(mul(n-i, i=1..j-1)*A(n-j, k), j=numtheory[divisors](k))))
end:
# alternative
local x, d ;
add(x^d/d, d=numtheory[divisors](m)) ;
exp(%) ;
coeftayl(%, x=0, n) ;
%*n! ;
end proc:
|
|
MATHEMATICA
|
t[n_ /; n >= 0, k_ /; k >= 0] := t[n, k] = Sum[(n!/(n - d + 1)!)*t[n - d, k], {d, Divisors[k]}]; t[_, _] = 1; Flatten[ Table[ t[n - k, k], {n, 0, 12}, {k, 1, n}]] (* Jean-François Alcover, Dec 12 2011, after given formula *)
|
|
CROSSREFS
|
Columns give A000012, A000085, A001470, A001472, A052501, A053496, A053497, A053498, A053499, A053500, A053501, A053502, A053503, A053504, A053505.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|