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

%I #53 Nov 11 2021 10:23:09

%S 1,1,1,1,3,2,1,9,8,6,1,25,40,30,24,1,75,200,180,144,120,1,231,980,

%T 1260,1008,840,720,1,763,5152,8820,8064,6720,5760,5040,1,2619,28448,

%U 61236,72576,60480,51840,45360,40320,1,9495,162080,461160,653184,604800,518400,453600,403200,362880

%N Triangle read by rows: T(n,k) is the number of permutations of n elements that have the longest cycle length k.

%C 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.

%C From _Peter Luschny_, Mar 07 2009: (Start)

%C 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).

%C Underlying partition triangle is A102189.

%C Same partition product with length statistic is A008275.

%C Diagonal a(A000217(n)) = rising_factorial(1,n-1), A000142(n-1) (n > 0).

%C Row sum is A000142. (End)

%C 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

%H Alois P. Heinz, <a href="/A126074/b126074.txt">Rows n = 1..141, flattened</a>

%H Steven Finch, <a href="https://arxiv.org/abs/2111.05720">Permute, Graph, Map, Derange</a>, arXiv:2111.05720 [math.CO], 2021.

%H S. W. Golomb and P. Gaal, <a href="https://doi.org/10.1006/aama.1997.0567">On the number of permutations of n objects with greatest cycle length k</a>, Adv. in Appl. Math., 20(1), 1998, 98-107.

%H IBM Research, <a href="http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/December2006.html">Ponder This</a>, December 2006.

%H Peter Luschny, <a href="http://www.luschny.de/math/seq/CountingWithPartitions.html">Counting with Partitions</a>. [From _Peter Luschny_, Mar 07 2009]

%H Peter Luschny, <a href="http://www.luschny.de/math/seq/stirling1partitions.html">Generalized Stirling_1 Triangles</a>. [From _Peter Luschny_, Mar 07 2009]

%H D. Panario and B. Richmond, <a href="https://doi.org/10.1007/s00453-001-0047-1">Exact largest and smallest size of components</a>, Algorithmica, 31 (2001), 413-432.

%F 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)

%F 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

%F From _Peter Luschny_, Mar 07 2009: (Start)

%F T(n,0) = [n = 0] (Iverson notation) and for n > 0 and 1 <= m <= n

%F T(n,m) = Sum_{a} M(a)|f^a| where a = a_1,..,a_n such that

%F 1*a_1+2*a_2+...+n*a_n = n and max{a_i} = m, M(a) = n!/(a_1!*..*a_n!),

%F f^a = (f_1/1!)^a_1*..*(f_n/n!)^a_n and f_n = product_{j=0..n-2}(j-n+1). (End)

%F Sum_{k=1..n} k * T(n,k) = A028418(n). - _Alois P. Heinz_, May 17 2016

%e Triangle T(n,k) begins:

%e 1;

%e 1, 1;

%e 1, 3, 2;

%e 1, 9, 8, 6;

%e 1, 25, 40, 30, 24;

%e 1, 75, 200, 180, 144, 120;

%e 1, 231, 980, 1260, 1008, 840, 720;

%e 1, 763, 5152, 8820, 8064, 6720, 5760, 5040;

%e ...

%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=1..k)))

%p end:

%p T:= (n, k)-> A(n, k) -A(n, k-1):

%p seq(seq(T(n,k), k=1..n), n=1..10); # _Alois P. Heinz_, Feb 11 2013

%t 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]

%o (Sage)

%o def A126074(n, k):

%o f = factorial(n)

%o P = Partitions(n, max_part=k, inner=[k])

%o return sum(f // p.aut() for p in P)

%o for n in (1..9): print([A126074(n,k) for k in (1..n)]) # _Peter Luschny_, Apr 17 2016

%Y Cf. A000142.

%Y Cf. A071007, A080510, A028418.

%Y Cf. A157386, A157385, A157384, A157383, A157400, A157391, A157392, A157393, A157394, A157395. - _Peter Luschny_, Mar 07 2009

%Y T(2n,n) gives A052145 (for n>0). - _Alois P. Heinz_, Apr 21 2017

%K base,nonn,tabl

%O 1,5

%A _Dan Dima_, Mar 01 2007

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 13:25 EDT 2024. Contains 371254 sequences. (Running on oeis4.)