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!)
A291680 Number T(n,k) of permutations p of [n] such that in 0p the largest up-jump equals k and no down-jump is larger than 2; triangle T(n,k), n>=0, 0<=k<=n, read by rows. 15
1, 0, 1, 0, 1, 1, 0, 1, 3, 2, 0, 1, 9, 8, 4, 0, 1, 25, 36, 20, 10, 0, 1, 71, 156, 108, 58, 26, 0, 1, 205, 666, 586, 340, 170, 74, 0, 1, 607, 2860, 3098, 2014, 1078, 528, 218, 0, 1, 1833, 12336, 16230, 11888, 6772, 3550, 1672, 672, 0, 1, 5635, 53518, 85150, 69274, 42366, 23284, 11840, 5454, 2126 (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

T(n,n) = A206464(n-1) for n>0.

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

EXAMPLE

T(4,1) = 1: 1234.

T(4,2) = 9: 1243, 1324, 1342, 2134, 2143, 2314, 2341, 2413, 2431.

T(4,3) = 8: 1423, 1432, 3124, 3142, 3214, 3241, 3412, 3421.

T(4,4) = 4: 4213, 4231, 4312, 4321.

T(5,5) = 10: 53124, 53142, 53214, 53241, 53412, 53421, 54213, 54231, 54312, 54321.

Triangle T(n,k) begins:

  1;

  0, 1;

  0, 1,   1;

  0, 1,   3,    2;

  0, 1,   9,    8,    4;

  0, 1,  25,   36,   20,   10;

  0, 1,  71,  156,  108,   58,   26;

  0, 1, 205,  666,  586,  340,  170,  74;

  0, 1, 607, 2860, 3098, 2014, 1078, 528, 218;

MAPLE

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

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

      add(b(u+j-1, o-j, k), j=1..min(k, 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_, k_] := b[u, o, k] = If[u+o == 0, 1, Sum[b[u-j, o+j-1, k], {j, 1, Min[2, u]}] + Sum[b[u+j-1, o-j, k], {j, 1, Min[k, 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, May 29 2019, after Alois P. Heinz *)

PROG

(Python)

from sympy.core.cache import cacheit

@cacheit

def b(u, o, k): return 1 if u + o==0 else sum([b(u - j, o + j - 1, k) for j in range(1, min(2, u) + 1)]) + sum([b(u + j - 1, o - j, k) for j in range(1, min(k, o) + 1)])

def T(n, k): return b(0, n, k) - (0 if k==0 else b(0, n, k - 1))

for n in range(13): print([T(n, k) for k in range(n + 1)]) # Indranil Ghosh, Aug 30 2017

CROSSREFS

Columns k=0-10 give: A000007, A057427, A291683, A321110, A321111, A321112, A321113, A321114, A321115, A321116, A321117.

T(2n,n) gives A320290.

Cf. A203717, A206464, A264868.

Sequence in context: A322324 A142071 A350448 * A193283 A193277 A118972

Adjacent sequences:  A291677 A291678 A291679 * A291681 A291682 A291683

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 18 16:18 EDT 2022. Contains 356215 sequences. (Running on oeis4.)