login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A008307 Table T(n,k) giving number of permutations of [1..n] with order dividing k, read by antidiagonals. 18

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 16:12 EDT 2024. Contains 371254 sequences. (Running on oeis4.)