A393036 Triangular irregular array: T(n,k) is the number of permutations on n letters with cycle type set [k].

1, 0, 1, 0, 1, 0, 1, 3, 0, 1, 6, 0, 1, 25, 0, 1, 60, 120, 0, 1, 231, 420, 0, 1, 658, 2800, 0, 1, 2619, 20160, 0, 1, 8550, 105840, 151200, 0, 1, 35695, 679140, 831600, 0, 1, 129756, 4848360, 8316000, 0, 1, 568503, 30356040, 86486400, 0, 1, 2255344, 217136920, 1089728640

Offset

0,8

Comments

A cycle type set of [k] requires that n be at least k*(k+1)/2 hence in the array k ranges from 0 to floor((sqrt(1+8*n)-1)/2).

References

P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009.

Links

Alois P. Heinz, Rows n = 0..460, flattened

Marko Riedel, Maple code for sequence.

Marko Riedel, Derivation of recurrence and generating functions.

Formula

T(n,k) = n! * rho(n,k) where rho(n,k) = Sum_{p=1..floor(n/k)} rho(n-k*p,k-1)/p!/k^p with rho(n,0) = delta(n,0).

Example

Triangle begins:
  n/k 0 1    2      3      4
   +-------------------------
  0|  1
  1|  0 1
  2|  0 1
  3|  0 1    3
  4|  0 1    6
  5|  0 1   25
  6|  0 1   60    120
  7|  0 1  231    420
  8|  0 1  658   2800
  9|  0 1 2619   2016
 10|  0 1 8550 105840 151200
 ...

Maple

b:= proc(n, i) option remember; `if`(n=0, x^(i-1), add(b(n-i*j, i+1)*
      combinat[multinomial](n, n-i*j, i$j)/j!*(i-1)!^j, j=1..n/i))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 1)):
seq(T(n), n=0..15);  # Alois P. Heinz, Feb 01 2026

Mathematica

b[n_, i_] := b[n, i] = If[n == 0, x^(i-1), Sum[b[n-i*j, i+1]* Multinomial@@Join[{n-i*j}, Table[i, {j}]]/j!*(i-1)!^j, {j, 1, n/i}]];
T[n_] := CoefficientList[b[n, 1], x];
Table[T[n], {n, 0, 15}] // Flatten (* Jean-François Alcover, Feb 14 2026, after Alois P. Heinz *)

Crossrefs

Row sums give A393037.

T(n*(n+1)/2,n) gives A246292.

Cf. A000217, A002024.

Sequence in context: A102765 A355257 A387082 * A129684 A247255 A105147

Adjacent sequences: A393033 A393034 A393035 * A393037 A393038 A393039

Keyword

nonn,tabf

Author

Marko Riedel, Jan 31 2026

Status

approved