A126074 -id:A126074 - cp's OEIS frontend

A157400 A partition product with biggest-part statistic of Stirling_1 type (with parameter k = -2) as well as of Stirling_2 type (with parameter k = -2), (triangle read by rows).

1, 1, 2, 1, 6, 6, 1, 24, 24, 24, 1, 80, 180, 120, 120, 1, 330, 1200, 1080, 720, 720, 1, 1302, 7770, 10920, 7560, 5040, 5040, 1, 5936, 57456, 102480, 87360, 60480, 40320, 40320, 1, 26784, 438984, 970704, 1103760, 786240, 544320, 362880, 362880

Offset: 1

Peter Luschny, Mar 09 2009, Mar 14 2009

Partition product of Product_{j=0..n-1} ((k+1)*j - 1) and n! at k = -2, summed over parts with equal biggest part (Stirling_2 type) as well as partition product of Product_{j=0..n-2} (k-n+j+2) and n! at k = -2 (Stirling_1 type).
It shares this property with the signless Lah numbers.
Underlying partition triangle is A130561.
Same partition product with length statistic is A105278.
Diagonal a(A000217) = A000142.
Row sum is A000262.
T(n,k) is the number of nilpotent elements in the symmetric inverse semigroup (partial bijections) on [n] having index k. Equivalently, T(n,k) is the number of directed acyclic graphs on n labeled nodes with every node having indegree and outdegree at most one and the longest path containing exactly k nodes. - Geoffrey Critzer, Nov 21 2021

			Triangle starts:
  1;
  1,   2;
  1,   6,    6;
  1,  24,   24,   24;
  1,  80,  180,  120, 120;
  1, 330, 1200, 1080, 720, 720;
  ...

Peter Luschny, Counting with Partitions.
Peter Luschny, Generalized Stirling_1 Triangles.
Peter Luschny, Generalized Stirling_2 Triangles.

Cf. A157396, A157397, A157398, A157399, A080510, A157401, A157402, A157403, A157404, A157405, A157386, A157385, A157384, A157383, A126074, A157391, A157392, A157393, A157394, A157395.

egf:= k-> exp((x^(k+1)-x)/(x-1))-exp((x^k-x)/(x-1)):
T:= (n, k)-> n!*coeff(series(egf(k), x, n+1), x, n):
seq(seq(T(n, k), k=1..n), n=1..10);  # Alois P. Heinz, Oct 10 2015

egf[k_] := Exp[(x^(k+1)-x)/(x-1)] - Exp[(x^k-x)/(x-1)]; T[n_, k_] := n! * SeriesCoefficient[egf[k], {x, 0, n}]; Table[Table[T[n, k], {k, 1, n}], {n, 1, 10}] // Flatten (* Jean-François Alcover, Oct 11 2015, after Alois P. Heinz *)

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-1} (-j-1)
OR f_n = Product_{j=0..n-2} (j-n) since both have the same absolute value n!.
E.g.f. of column k: exp((x^(k+1)-x)/(x-1))-exp((x^k-x)/(x-1)). - Alois P. Heinz, Oct 10 2015

A145877 Triangle read by rows: T(n,k) is the number of permutations of [n] for which the shortest cycle length is k (1<=k<=n).

Original entry on oeis.org

1, 1, 1, 4, 0, 2, 15, 3, 0, 6, 76, 20, 0, 0, 24, 455, 105, 40, 0, 0, 120, 3186, 714, 420, 0, 0, 0, 720, 25487, 5845, 2688, 1260, 0, 0, 0, 5040, 229384, 52632, 22400, 18144, 0, 0, 0, 0, 40320, 2293839, 525105, 223200, 151200, 72576, 0, 0, 0, 0, 362880, 25232230

Offset: 1

Emeric Deutsch, Oct 27 2008

Row sums are the factorials (A000142).
Sum(T(n,k), k=2..n) = A000166(n) (the derangement numbers).
T(n,1) = A002467(n).
T(n,n) = (n-1)! (A000142).
Sum(k*T(n,k),k=1..n) = A028417(n).
For the statistic "length of the longest cycle", see A126074.

			T(4,2)=3 because we have 3412=(13)(24), 2143=(12)(34) and 4321=(14)(23).
Triangle starts:
      1;
      1,    1;
      4,    0,    2;
     15,    3,    0,    6;
     76,   20,    0,    0, 24;
    455,  105,   40,    0,  0, 120;
   3186,  714,  420,    0,  0,   0, 720;
  25487, 5845, 2688, 1260,  0,   0,   0, 5040;
  ...

Alois P. Heinz, Rows n = 1..141, flattened
Steven Finch, Permute, Graph, Map, Derange, arXiv:2111.05720 [math.CO], 2021.
D. Panario and B. Richmond, Exact largest and smallest size of components, Algorithmica, 31 (2001), 413-432.

Cf. A000142, A000166, A002467, A028417, A126074.

T(2n,n) gives A110468(n-1) (for n>0). - Alois P. Heinz, Apr 21 2017

F:=proc(k) options operator, arrow: (1-exp(-x^k/k))*exp(-(sum(x^j/j, j = 1 .. k-1)))/(1-x) end proc: for k to 16 do g[k]:= series(F(k),x=0,16) end do: T:= proc(n,k) options operator, arrow: factorial(n)*coeff(g[k],x,n) end proc: for n to 11 do seq(T(n,k),k=1..n) end do; # yields sequence in triangular form

Rest[Transpose[Table[Range[0, 16]! CoefficientList[
      Series[(Exp[x^n/n] -1) (Exp[-Sum[x^k/k, {k, 1, n}]]/(1 - x)), {x, 0, 16}],x], {n, 1, 8}]]] // Grid (* Geoffrey Critzer, Mar 04 2011 *)

E.g.f. for column k is (1-exp(-x^k/k))*exp( -sum(j=1..k-1, x^j/j ) ) / (1-x). - Vladeta Jovovic

A293211 Triangle T(n,k) is the number of permutations on n elements with at least one k-cycle for 1 <= k <= n.

Original entry on oeis.org

1, 1, 1, 4, 3, 2, 15, 9, 8, 6, 76, 45, 40, 30, 24, 455, 285, 200, 180, 144, 120, 3186, 1995, 1400, 1260, 1008, 840, 720, 25487, 15855, 11200, 8820, 8064, 6720, 5760, 5040, 229384, 142695, 103040, 79380, 72576, 60480, 51840, 45360, 40320, 2293839, 1427895, 1030400, 793800, 653184, 604800, 518400, 453600, 403200, 362880

Offset: 1

Dennis P. Walsh, Oct 02 2017

T(n,k) is equivalent to n! minus the number of permutations on n elements with zero k-cycles (sequence A122974).

			T(n,k) (the first 8 rows):
:     1;
:     1,     1;
:     4,     3,     2;
:    15,     9,     8,    6;
:    76,    45,    40,   30,   24;
:   455,   285,   200,  180,  144,  120;
:  3186,  1995,  1400, 1260, 1008,  840,  720;
: 25487, 15855, 11200, 8820, 8064, 6720, 5760, 5040;
  ...
T(4,3)=8 since there are exactly 8 permutations on {1,2,3,4} with at least one 3-cycle: (1)(234), (1)(243), (2)(134), (2)(143), (3)(124), (3)(142), (4)(123), and (4)(132).

Dennis P. Walsh, The number of permutations with no k-cycles

Columns k=1-10 give: A002467, A027616, A027617, A029571, A029572, A029573, A029574, A029575, A029576, A029577.
Row sums give A132961.
T(n,n) gives A000142(n-1) for n>0.
T(2n,n) gives A052145.
Cf. A122974, A126074.

T:=(n,k)->n!*sum((-1)^(j+1)*(1/k)^j/j!,j=1..floor(n/k)); seq(seq(T(n,k),k=1..n),n=1..10);

Table[n!*Sum[(-1)^(j + 1)*(1/k)^j/j!, {j, Floor[n/k]}], {n, 10}, {k, n}] // Flatten (* Michael De Vlieger, Oct 02 2017 *)

T(n,k) = n! * Sum_{j=1..floor(n/k)} (-1)^(j+1)*(1/k)^j/j!.
T(n,k) = n! - A122974(n,k).
E.g.f. of column k: (1-exp(-x^k/k))/(1-x). - Alois P. Heinz, Oct 11 2017

A028418 Sum over all n! permutations of n letters of maximum cycle length.

Original entry on oeis.org

1, 3, 13, 67, 411, 2911, 23563, 213543, 2149927, 23759791, 286370151, 3734929903, 52455166063, 788704078527, 12648867695311, 215433088624351, 3884791172487903, 73919882720901823, 1480542628345939807, 31128584449987511871, 685635398619169059391

Offset: 1

Joe Keane (jgk(AT)jgk.org)

nonn

Sum the n-permutations having at least 1 cycle of length >= i for all i >= 1. A000142 + A033312 + A066052 + A202364 + ... The summation is precisely that indicated in the title since each permutation whose longest cycle = i is counted i times. - Geoffrey Critzer, Jan 09 2013

S. W. Golomb, Shift-Register Sequences, Holden-Day, San Francisco, 1967, p. 183.
R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996, page 358.

Alois P. Heinz, Table of n, a(n) for n = 1..450 (first 142 terms from Thomas Dybdahl Ahle)
Ph. Flajolet and A. Odlyzko, Singularity analysis of generating functions, p. 22.

Cf. A006128, A028417, A060014, A126074.

Column k=1 of A322384.

b:= proc(n, m) option remember; `if`(n=0, m, add((j-1)!*
      b(n-j, max(m,j))*binomial(n-1, j-1), j=1..n))
    end:
a:= n-> b(n, 0):
seq(a(n), n=1..25);  # Alois P. Heinz, May 14 2016

kmax = 19; gf[x_] = Sum[ 1/(1-x) - 1/(E^((x^(1+k)*Hypergeometric2F1[1+k, 1, 2+k, x])/ (1+k))*(1-x)), {k, 0, kmax}];
a[n_] := n!*Coefficient[Series[gf[x], {x, 0, kmax}], x^n]; Array[a, kmax]
(* Jean-François Alcover, Jun 22 2011, after e.g.f. *)
a[ n_] := If[ n < 1, 0, 1 + Total @ Apply[ Max, Map[ Length, First /@ PermutationCycles /@ Drop[ Permutations @ Range @ n, 1], {2}], 1]]; (* Michael Somos, Aug 19 2018 *)

E.g.f.: Sum_{k>=0} (1/(1-x) - exp(Sum_{j=1..k} x^j/j)).
a(n) = f(n, 0, n, n!) where f(L, r, n, m) = m*r if r >= l, otherwise Sum_{k=0..L-1} (f(k, max(L-k,r), n-1, m/n) + (n-L)*f(L, r, n-1, m/n)). - Thomas Dybdahl Ahle, Aug 15 2011
a(n) = Sum_{k=1..n} k * A126074(n,k). - Alois P. Heinz, May 17 2016

More terms from Vladeta Jovovic, Sep 19 2002

More terms from Thomas Dybdahl Ahle, Aug 15 2011

A157384 A partition product of Stirling_1 type [parameter k = -4] with biggest-part statistic (triangle read by rows).

Original entry on oeis.org

1, 1, 4, 1, 12, 20, 1, 72, 80, 120, 1, 280, 1000, 600, 840, 1, 1740, 9200, 9000, 5040, 6720, 1, 8484, 79100, 138600, 88200, 47040, 60480, 1, 57232, 874720, 1789200, 1552320, 940800, 483840, 604800, 1, 328752, 9532880

Offset: 1

Peter Luschny, Mar 07 2009, Mar 14 2009

Partition product of prod_{j=0..n-2}(k-n+j+2) and n! at k = -4,
summed over parts with equal biggest part (see the Luschny link).
Underlying partition triangle is A144354.
Same partition product with length statistic is A049352.
Diagonal a(A000217(n)) = rising_factorial(4,n-1), A001715(n+2).
Row sum is A049377.

Peter Luschny, Counting with Partitions.
Peter Luschny, Generalized Stirling_1 Triangles.

Cf. A157386, A157384, A157383, A157400, A126074, A157391, A157392, A157393, A157394, A157395

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-2).

A157383 A partition product of Stirling_1 type [parameter k = -3] with biggest-part statistic (triangle read by rows).

Original entry on oeis.org

1, 1, 3, 1, 9, 12, 1, 45, 48, 60, 1, 165, 480, 300, 360, 1, 855, 3840, 3600, 2160, 2520, 1, 3843, 29400, 46200, 30240, 17640, 20160, 1, 21819, 272832, 520800, 443520, 282240, 161280, 181440

Offset: 1

Peter Luschny, Mar 07 2009, Mar 14 2009

Partition product of prod_{j=0..n-2}(k-n+j+2) and n! at k = -3,
summed over parts with equal biggest part (see the Luschny link).
Underlying partition triangle is A144353.
Same partition product with length statistic is A046089.
Diagonal a(A000217(n)) = rising_factorial(3,n-1), A001710(n+1).
Row sum is A049376.

Peter Luschny, Counting with Partitions.
Peter Luschny, Generalized Stirling_1 Triangles.

Cf. A157386, A157385, A157384, A157400, A126074, A157391, A157392, A157393, A157394, A157395

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

A157386 A partition product of Stirling_1 type [parameter k = -6] with biggest-part statistic (triangle read by rows).

Original entry on oeis.org

1, 1, 6, 1, 18, 42, 1, 144, 168, 336, 1, 600, 2940, 1680, 3024, 1, 4950, 33600, 35280, 18144, 30240, 1, 26586, 336630, 717360, 444528, 211680, 332640, 1, 234528, 4870992, 11313120, 10329984, 5927040, 2661120, 3991680

Offset: 1

Peter Luschny, Mar 07 2009, Mar 14 2009

Partition product of prod_{j=0..n-2}(k-n+j+2) and n! at k = -6,
summed over parts with equal biggest part (see the Luschny link).
Underlying partition triangle is A144356.
Same partition product with length statistic is A049374.
Diagonal a(A000217(n)) = rising_factorial(6,n-1), A001725(n+4).
Row sum is A049402.

Peter Luschny, Counting with Partitions.
Peter Luschny, Generalized Stirling_1 Triangles.

Cf. A157385, A157384, A157383, A157400, A126074, A157391, A157392, A157393, A157394, A157395

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-4).

A157385 A partition product of Stirling_1 type [parameter k = -5] with biggest-part statistic (triangle read by rows).

Original entry on oeis.org

1, 1, 5, 1, 15, 30, 1, 105, 120, 210, 1, 425, 1800, 1050, 1680, 1, 3075, 18600, 18900, 10080, 15120, 1, 15855, 174300, 338100, 211680, 105840, 151200, 1, 123515, 2227680, 4865700, 4327680, 2540160, 1209600, 1663200, 1, 757755

Offset: 1

Peter Luschny, Mar 07 2009, Mar 14 2009

Partition product of prod_{j=0..n-2}(k-n+j+2) and n! at k = -5,
summed over parts with equal biggest part (see the Luschny link).
Underlying partition triangle is A144355.
Same partition product with length statistic is A049353.
Diagonal a(A000217(n)) = rising_factorial(5,n-1), A001720(n+3).
Row sum is A049378.

Peter Luschny, Counting with Partitions.
Peter Luschny, Generalized Stirling_1 Triangles.

Cf. A157386, A157384, A157383, A157400, A126074, A157391, A157392, A157393, A157394, A157395

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-3).

A349979 Irregular triangle read by rows: T(n,k) is the number of n-permutations whose second-longest cycle has length exactly k; n>=0, 0<=k<=floor(n/2).

Original entry on oeis.org

1, 1, 1, 1, 2, 4, 6, 15, 3, 24, 61, 35, 120, 290, 270, 40, 720, 1646, 1974, 700, 5040, 11025, 14707, 8288, 1260, 40320, 85345, 117459, 90272, 29484, 362880, 749194, 1023390, 974720, 446040, 72576, 3628800, 7347374, 9813210, 10666480, 6332040, 2128896

Offset: 0

Steven Finch, Dec 07 2021

If the permutation has no second cycle, then its second-longest cycle is defined to have length 0.

			Triangle begins:
[0]     1;
[1]     1;
[2]     1,     1;
[3]     2,     4;
[4]     6,    15,      3;
[5]    24,    61,     35;
[6]   120,   290,    270,    40;
[7]   720,  1646,   1974,   700;
[8]  5040, 11025,  14707,  8288,  1260;
[9] 40320, 85345, 117459, 90272, 29484;
    ...

Alois P. Heinz, Rows n = 0..200, flattened
Steven Finch, Second best, Third worst, Fourth in line, arxiv:2202.07621 [math.CO], 2022.

Column 0 gives 1 together with A000142.
Column 1 gives 1 - (n-1)! + A006231(n).
Row sums give A000142.
T(2n,n) gives A110468(n-1) for n>=1.
Cf. A126074, A145877, A332851, A349980, A350015, A350016, A350273, A350274.

b:= proc(n, l) option remember; `if`(n=0, x^l[1], add((j-1)!*
      b(n-j, sort([l[], j])[2..3])*binomial(n-1, j-1), j=1..n))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n/2))(b(n, [0$2])):
seq(T(n), n=0..12);  # Alois P. Heinz, Dec 07 2021

b[n_, l_] := b[n, l] = If[n == 0, x^l[[1]], Sum[(j - 1)!*b[n - j, Sort[ Append[l, j]][[2 ;; 3]]]*Binomial[n - 1, j - 1], {j, 1, n}]];
T[n_] := With[{p = b[n, {0, 0}]}, Table[Coefficient[p, x, i], {i, 0, n/2}]];
Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Dec 28 2021, after Alois P. Heinz *)

Sum_{k=0..floor(n/2)} k * T(n,k) = A332851(n). - Alois P. Heinz, Dec 07 2021

A349980 Irregular triangle read by rows: T(n,k) is the number of n-permutations whose second-shortest cycle has length exactly k; n >= 0, 0 <= k <= max(0,n-1).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 3, 6, 7, 3, 8, 24, 31, 15, 20, 30, 120, 191, 135, 40, 90, 144, 720, 1331, 945, 280, 420, 504, 840, 5040, 10655, 7077, 4480, 1260, 2688, 3360, 5760, 40320, 95887, 64197, 41552, 11340, 18144, 20160, 25920, 45360, 362880, 958879, 646965, 395360, 238140, 72576, 151200, 172800, 226800, 403200

Offset: 0

Steven Finch, Dec 07 2021

If the permutation has no second cycle, then its second-longest cycle is defined to have length 0.

			Triangle begins:
[0]     1;
[1]     1;
[2]     1,     1;
[3]     2,     1,     3;
[4]     6,     7,     3,     8;
[5]    24,    31,    15,    20,    30;
[6]   120,   191,   135,    40,    90,   144;
[7]   720,  1331,   945,   280,   420,   504,   840;
[8]  5040, 10655,  7077,  4480,  1260,  2688,  3360,  5760;
[9] 40320, 95887, 64197, 41552, 11340, 18144, 20160, 25920, 45360;
    ...

Alois P. Heinz, Rows n = 0..141, flattened
Steven Finch, Second best, Third worst, Fourth in line, arxiv:2202.07621 [math.CO], 2022.

Column 0 gives 1 together with A000142.
Column 1 gives the nonzero terms of A155521.
Row sums give A000142.
T(n,n-1) gives A059171(n) for n>=1.
Cf. A126074, A145877, A332906, A349979, A350015, A350016, A350273, A350274.

m:= infinity:
b:= proc(n, l) option remember; `if`(n=0, x^`if`(l[2]=m,
      0, l[2]), add(b(n-j, sort([l[], j])[1..2])
               *binomial(n-1, j-1)*(j-1)!, j=1..n))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..max(0, n-1)))(b(n, [m$2])):
seq(T(n), n=0..10);  # Alois P. Heinz, Dec 07 2021

m = Infinity;
b[n_, l_] := b[n, l] = If[n == 0, x^If[l[[2]] == m, 0, l[[2]]], Sum[b[n-j, Sort[Append[l, j]][[1;;2]]]*Binomial[n - 1, j - 1]*(j - 1)!, {j, 1, n}]];
T[n_] := With[{p = b[n, {m, m}]}, Table[Coefficient[p, x, i], {i, 0, Max[0, n - 1]}]];
Table[T[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, Dec 28 2021, after Alois P. Heinz *)

Sum_{k=0..max(0,n-1)} k * T(n,k) = A332906(n). - Alois P. Heinz, Dec 07 2021

More terms from Alois P. Heinz, Dec 07 2021

cp's OEIS Frontend

A157400 A partition product with biggest-part statistic of Stirling_1 type (with parameter k = -2) as well as of Stirling_2 type (with parameter k = -2), (triangle read by rows).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A145877 Triangle read by rows: T(n,k) is the number of permutations of [n] for which the shortest cycle length is k (1<=k<=n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A293211 Triangle T(n,k) is the number of permutations on n elements with at least one k-cycle for 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A028418 Sum over all n! permutations of n letters of maximum cycle length.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A157384 A partition product of Stirling_1 type [parameter k = -4] with biggest-part statistic (triangle read by rows).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A157383 A partition product of Stirling_1 type [parameter k = -3] with biggest-part statistic (triangle read by rows).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A157386 A partition product of Stirling_1 type [parameter k = -6] with biggest-part statistic (triangle read by rows).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A157385 A partition product of Stirling_1 type [parameter k = -5] with biggest-part statistic (triangle read by rows).

Views

Author

Keywords

Comments

Links