A344855 Number T(n,k) of permutations of [n] having k cycles of the form (c1, c2, ..., c_m) where c1 = min_{i>=1} c_i and c_j = min_{i>=j} c_i or c_j = max_{i>=j} c_i; triangle T(n,k), n>=0, 0<=k<=n, read by rows.
1, 0, 1, 0, 1, 1, 0, 2, 3, 1, 0, 4, 11, 6, 1, 0, 8, 40, 35, 10, 1, 0, 16, 148, 195, 85, 15, 1, 0, 32, 560, 1078, 665, 175, 21, 1, 0, 64, 2160, 5992, 5033, 1820, 322, 28, 1, 0, 128, 8448, 33632, 37632, 17913, 4284, 546, 36, 1, 0, 256, 33344, 190800, 280760, 171465, 52941, 9030, 870, 45, 1
Offset: 0
Examples
T(4,1) = 4: (1234), (1243), (1423), (1432). Triangle T(n,k) begins: 1; 0, 1; 0, 1, 1; 0, 2, 3, 1; 0, 4, 11, 6, 1; 0, 8, 40, 35, 10, 1; 0, 16, 148, 195, 85, 15, 1; 0, 32, 560, 1078, 665, 175, 21, 1; 0, 64, 2160, 5992, 5033, 1820, 322, 28, 1; ...
Links
- Alois P. Heinz, Rows n = 0..140, flattened
- Wikipedia, Permutation
Crossrefs
Programs
-
Maple
b:= proc(n) option remember; `if`(n=0, 1, add(expand(x* b(n-j)*binomial(n-1, j-1)*ceil(2^(j-2))), j=1..n)) end: T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n)): seq(T(n), n=0..12); -
Mathematica
b[n_] := b[n] = If[n == 0, 1, Sum[Expand[x*b[n-j]* Binomial[n-1, j-1]*Ceiling[2^(j-2)]], {j, n}]]; T[n_] := CoefficientList[b[n], x]; Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Aug 23 2021, after Alois P. Heinz *)
Formula
Sum_{k=1..n} k * T(n,k) = A345341(n).
For fixed k, T(n,k) ~ (2*k)^n / (4^k * k!). - Vaclav Kotesovec, Jul 15 2021
Comments