A285849 Number T(n,k) of permutations of [n] with k ordered cycles such that equal-sized cycles are ordered with increasing least elements; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 1, 1, 0, 2, 6, 1, 0, 6, 19, 18, 1, 0, 24, 100, 105, 40, 1, 0, 120, 508, 1005, 430, 75, 1, 0, 720, 3528, 6762, 6300, 1400, 126, 1, 0, 5040, 24876, 61572, 62601, 28700, 3822, 196, 1, 0, 40320, 219168, 558548, 706608, 431445, 105336, 9114, 288, 1

Offset: 0

Author

Alois P. Heinz, Apr 27 2017

Keywords

• nonn
• tabl

Comments

Each cycle is written with the smallest element first and equal-sized cycles are arranged in increasing order of their first elements.

Examples

			T(3,1) = 2: (123), (132).
T(3,2) = 6: (1)(23), (23)(1), (2)(13), (13)(2), (3)(12), (12)(3).
T(3,3) = 1: (1)(2)(3).
Triangle T(n,k) begins:
  1;
  0,    1;
  0,    1,     1;
  0,    2,     6,     1;
  0,    6,    19,    18,     1;
  0,   24,   100,   105,    40,     1;
  0,  120,   508,  1005,   430,    75,    1;
  0,  720,  3528,  6762,  6300,  1400,  126,   1;
  0, 5040, 24876, 61572, 62601, 28700, 3822, 196, 1;
		

Links

• Alois P. Heinz, Rows n = 0..140, flattened
• Wikipedia, Permutation

Crossrefs

Columns k=0-10 give: A000007, A104150, A285853, A285854, A285855, A285856, A285857, A285858, A285859, A285860, A285861.

Row sums give A196301.

Main diagonal and first lower diagonal give: A000012, A002411.

T(2n,n) gives A285862.

Cf. A132393, A285824.

Programs

Maple

b:= proc(n, i, p) option remember; expand(`if`(n=0 or i=1,
      (p+n)!/n!*x^n, add(b(n-i*j, i-1, p+j)*(i-1)!^j*combinat
      [multinomial](n, n-i*j, i$j)/j!^2*x^j, j=0..n/i)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n$2, 0)):
seq(T(n), n=0..12);

Mathematica

multinomial[n_, k_List] := n!/Times @@ (k!);
b[n_, i_, p_] := b[n, i, p] = Expand[If[n == 0 || i == 1, (p + n)!/n!*x^n, Sum[b[n - i*j, i - 1, p + j]*(i - 1)!^j*multinomial[n, Join[{n - i*j}, Table[i, j]]]/j!^2*x^j, {j, 0, n/i}]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, n}]][b[n, n, 0]];
Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Apr 28 2018, after Alois P. Heinz *)