|
%I #48 Dec 16 2021 22:19:48
%S 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,
%T 81,56,1,6,1,1,1,764,351,256,25,18,1,2,1,1,2620,1233,1072,145,66,1,4,
%U 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
%N Table T(n,k) giving number of permutations of [1..n] with order dividing k, read by antidiagonals.
%C Solutions to x^k = 1 in Symm_n (the symmetric group of degree n).
%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 257.
%D J. D. Dixon, B. Mortimer, Permutation Groups, Springer (1996), Exercise 1.2.13.
%H Alois P. Heinz, <a href="/A008307/b008307.txt">Antidiagonals n = 1..141, flattened</a>
%H M. B. Kutler, C. R. Vinroot, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Vinroot/vinroot3.html">On q-Analogs of Recursions for the Number of Involutions and Prime Order Elements in Symmetric Groups</a>, JIS 13 (2010) #10.3.6, eq (5) for primes k.
%F 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.
%F E.g.f. for n-th row: Sum_{n>=0} T(n,k)*t^n/n! = exp(Sum_{d|k} t^d/d).
%e Array begins:
%e 1, 1, 1, 1, 1, 1, 1, 1, ...
%e 1, 2, 1, 2, 1, 2, 1, 2, ...
%e 1, 4, 3, 4, 1, 6, 1, 4, ...
%e 1, 10, 9, 16, 1, 18, 1, 16, ...
%e 1, 26, 21, 56, 25, 66, 1, 56, ...
%e 1, 76, 81, 256, 145, 396, 1, 256, ...
%e 1, 232, 351, 1072, 505, 2052, 721, 1072, ...
%e 1, 764, 1233, 6224, 1345, 12636, 5761, 11264, ...
%p A:= proc(n,k) option remember; `if`(n<0, 0, `if`(n=0, 1,
%p add(mul(n-i, i=1..j-1)*A(n-j,k), j=numtheory[divisors](k))))
%p end:
%p seq(seq(A(1+d-k, k), k=1..d), d=1..12); # _Alois P. Heinz_, Feb 14 2013
%p # alternative
%p A008307 := proc(n,m)
%p local x,d ;
%p add(x^d/d, d=numtheory[divisors](m)) ;
%p exp(%) ;
%p coeftayl(%,x=0,n) ;
%p %*n! ;
%p end proc:
%p seq(seq(A008307(1+d-k,k),k=1..d),d=1..12) ; # _R. J. Mathar_, Apr 30 2017
%t 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 *)
%Y Rows give A000034, A284517, A284518.
%Y Columns give A000012, A000085, A001470, A001472, A052501, A053496, A053497, A053498, A053499, A053500, A053501, A053502, A053503, A053504, A053505.
%Y Main diagonal gives A074759. - _Alois P. Heinz_, Feb 14 2013
%K nonn,tabl,easy,look,nice
%O 1,5
%A _N. J. A. Sloane_
%E More terms from _Vladeta Jovovic_, Apr 13 2001
|
