login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons 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

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

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

Columns k=0-10 give: A000007, A166444, A346317, A346318, A346319, A346320, A346321, A346322, A346323, A346324, A346325.

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.

Cf. A132393, A186366, A345341.

Sequence in context: A100329 A193535 A332645 * A081247 A298753 A173050

Adjacent sequences:  A344852 A344853 A344854 * A344856 A344857 A344858

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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 22 05:36 EDT 2021. Contains 348160 sequences. (Running on oeis4.)