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!)
A126074 Triangle read by rows: T(n,k) is the number of permutations of n elements that have the longest cycle length k. 23
1, 1, 1, 1, 3, 2, 1, 9, 8, 6, 1, 25, 40, 30, 24, 1, 75, 200, 180, 144, 120, 1, 231, 980, 1260, 1008, 840, 720, 1, 763, 5152, 8820, 8064, 6720, 5760, 5040, 1, 2619, 28448, 61236, 72576, 60480, 51840, 45360, 40320, 1, 9495, 162080, 461160, 653184, 604800, 518400, 453600, 403200, 362880 (list; table; graph; refs; listen; history; text; internal format)
OFFSET
1,5
COMMENTS
Sum of the n-th row is the number of all permutations of n elements: Sum_{k=1..n, T(n,k)} = n! = A000142(n) We can extend T(n,k)=0, if k<=0 or k>n.
From Peter Luschny, Mar 07 2009: (Start)
Partition product of prod_{j=0..n-2}(k-n+j+2) and n! at k = -1, summed over parts with equal biggest part (see the Luschny link).
Underlying partition triangle is A102189.
Same partition product with length statistic is A008275.
Diagonal a(A000217(n)) = rising_factorial(1,n-1), A000142(n-1) (n > 0).
Row sum is A000142. (End)
Let k in {1,2,3,...} index the family of sequences A000012, A000085, A057693, A070945, A070946, A070947, ... respectively. Column k is the k-th sequence minus its immediate predecessor. For example, T(5,3)=A057693(5)-A000085(5). - Geoffrey Critzer, May 23 2009
LINKS
Steven Finch, Permute, Graph, Map, Derange, arXiv:2111.05720 [math.CO], 2021.
S. W. Golomb and P. Gaal, On the number of permutations of n objects with greatest cycle length k, Adv. in Appl. Math., 20(1), 1998, 98-107.
IBM Research, Ponder This, December 2006.
Peter Luschny, Counting with Partitions. [From Peter Luschny, Mar 07 2009]
Peter Luschny, Generalized Stirling_1 Triangles. [From Peter Luschny, Mar 07 2009]
D. Panario and B. Richmond, Exact largest and smallest size of components, Algorithmica, 31 (2001), 413-432.
FORMULA
T(n,1) = 1 T(n,2) = n! * Sum_{k=1..[n/2], (1/(k! * (2!)^k * (n-2k)!)} T(n,k) = n!/k * (1-1/(n-k)-...-1/(k+1)-1/2k), if n/3 < k <= n/2 T(n,k) = n!/k, if n/2 < k <= n T(n,n) = (n-1)! = A000142(n-1)
E.g.f. for k-th column: exp(-x^k*LerchPhi(x,1,k))*(exp(x^k/k)-1)/(1-x). - Vladeta Jovovic, Mar 03 2007
From Peter Luschny, Mar 07 2009: (Start)
T(n,0) = [n = 0] (Iverson notation) and for n > 0 and 1 <= m <= n
T(n,m) = Sum_{a} M(a)|f^a| where a = a_1,..,a_n such that
1*a_1+2*a_2+...+n*a_n = n and max{a_i} = m, M(a) = n!/(a_1!*..*a_n!),
f^a = (f_1/1!)^a_1*..*(f_n/n!)^a_n and f_n = product_{j=0..n-2}(j-n+1). (End)
Sum_{k=1..n} k * T(n,k) = A028418(n). - Alois P. Heinz, May 17 2016
EXAMPLE
Triangle T(n,k) begins:
1;
1, 1;
1, 3, 2;
1, 9, 8, 6;
1, 25, 40, 30, 24;
1, 75, 200, 180, 144, 120;
1, 231, 980, 1260, 1008, 840, 720;
1, 763, 5152, 8820, 8064, 6720, 5760, 5040;
...
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=1..k)))
end:
T:= (n, k)-> A(n, k) -A(n, k-1):
seq(seq(T(n, k), k=1..n), n=1..10); # Alois P. Heinz, Feb 11 2013
MATHEMATICA
Table[CoefficientList[ Series[(Exp[x^m/m] - 1) Exp[Sum[x^k/k, {k, 1, m - 1}]], {x, 0, 8}], x]*Table[n!, {n, 0, 8}], {m, 1, 8}] // Transpose // Grid [From Geoffrey Critzer, May 23 2009]
PROG
(Sage)
def A126074(n, k):
f = factorial(n)
P = Partitions(n, max_part=k, inner=[k])
return sum(f // p.aut() for p in P)
for n in (1..9): print([A126074(n, k) for k in (1..n)]) # Peter Luschny, Apr 17 2016
CROSSREFS
Cf. A000142.
T(2n,n) gives A052145 (for n>0). - Alois P. Heinz, Apr 21 2017
Sequence in context: A155788 A108073 A057731 * A108916 A119421 A121581
KEYWORD
base,nonn,tabl
AUTHOR
Dan Dima, Mar 01 2007
STATUS
approved

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 February 28 22:27 EST 2024. Contains 370400 sequences. (Running on oeis4.)