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!)
A291684 Number T(n,k) of permutations p of [n] such that 0p has a nonincreasing jump sequence beginning with k; triangle T(n,k), n>=0, 0<=k<=n, read by rows. 15
1, 0, 1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 5, 5, 5, 0, 1, 9, 12, 14, 16, 0, 1, 17, 36, 36, 47, 52, 0, 1, 31, 81, 98, 117, 166, 189, 0, 1, 57, 174, 327, 327, 425, 627, 683, 0, 1, 101, 413, 788, 988, 1116, 1633, 2400, 2621, 0, 1, 185, 889, 1890, 3392, 3392, 4291, 6471, 9459, 10061 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,9

COMMENTS

An up-jump j occurs at position i in p if p_{i} > p_{i-1} and j is the index of p_i in the increasingly sorted list of those elements in {p_{i}, ..., p_{n}} that are larger than p_{i-1}. A down-jump j occurs at position i in p if p_{i} < p_{i-1} and j is the index of p_i in the decreasingly sorted list of those elements in {p_{i}, ..., p_{n}} that are smaller than p_{i-1}. First index in the lists is 1 here.

LINKS

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

FORMULA

Sum_{k=0..n} T(n,k) = T(n+1,n+1) = A291685(n).

T(2n,n) = T(2n,n+1) for all n>0.

EXAMPLE

T(3,1) = 1: 123.

T(3,2) = 2: 213, 231.

T(3,3) = 2: 312, 321.

Triangle T(n,k) begins:

  1;

  0, 1;

  0, 1,   1;

  0, 1,   2,   2;

  0, 1,   5,   5,   5;

  0, 1,   9,  12,  14,  16;

  0, 1,  17,  36,  36,  47,   52;

  0, 1,  31,  81,  98, 117,  166,  189;

  0, 1,  57, 174, 327, 327,  425,  627,  683;

  0, 1, 101, 413, 788, 988, 1116, 1633, 2400, 2621;

MAPLE

b:= proc(u, o, t) option remember; `if`(u+o=0, 1,

      add(b(u-j, o+j-1, j), j=1..min(t, u))+

      add(b(u+j-1, o-j, j), j=1..min(t, o)))

    end:

T:= (n, k)-> b(0, n, k)-`if`(k=0, 0, b(0, n, k-1)):

seq(seq(T(n, k), k=0..n), n=0..12);

MATHEMATICA

b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, 1, Sum[b[u - j, o + j - 1, j], {j, 1, Min[t, u]}] + Sum[b[u + j - 1, o - j, j], {j, 1, Min[t, o]}]];

T[n_, k_] :=  b[0, n, k] - If[k == 0, 0, b[0, n, k - 1]];

Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-Fran├žois Alcover, Jul 09 2018, after Alois P. Heinz *)

CROSSREFS

Columns k=0-10 give: A000007, A057427, A292168, A292169, A292170, A292171, A292172, A292173, A292174, A292175, A292176.

Row sums and T(n+1,n+1) give A291685.

T(2n,n) gives A291688, T(2n+1,n+1) gives A303203, T(n,ceiling(n/2)) gives A303204.

Sequence in context: A273899 A102404 A089246 * A105929 A065600 A029583

Adjacent sequences:  A291681 A291682 A291683 * A291685 A291686 A291687

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, Aug 29 2017

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 21 08:06 EDT 2021. Contains 348150 sequences. (Running on oeis4.)