A008307 - OEIS

%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