login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 13
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET
0,8
COMMENTS
The sequence of column k satisfies a linear recurrence with constant coefficients of order k*(k+1)/2 = A000217(k).
LINKS
Wikipedia, Permutation
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
EXAMPLE
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;
...
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 *)
CROSSREFS
Row sums give A187251.
Main diagonal gives A000012, lower diagonal gives A000217, second lower diagonal gives A000914.
T(n+1,n) gives A000217.
T(n+2,n) gives A000914.
T(2n,n) gives A345342.
Sequence in context: A100329 A193535 A332645 * A081247 A298753 A173050
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, May 30 2021
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 20 07:26 EDT 2024. Contains 373512 sequences. (Running on oeis4.)