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,8

Comments

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

Links

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

Wikipedia, Permutation

Example

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;

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

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.

Sequence in context: A255484 A021797 A068959 * A243398 A175474 A271877

Adjacent sequences: A285846 A285847 A285848 * A285850 A285851 A285852

Keyword

nonn,tabl

Author

Alois P. Heinz, Apr 27 2017

Status

approved