login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A258829 Number T(n,k) of permutations p of [n] such that the up-down signature of 0,p has nonnegative partial sums with a maximal value of k; triangle T(n,k), n>=0, 0<=k<=n, read by rows. 19
1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 5, 11, 3, 1, 0, 16, 38, 28, 4, 1, 0, 61, 263, 130, 62, 5, 1, 0, 272, 1260, 1263, 340, 129, 6, 1, 0, 1385, 10871, 8090, 4734, 819, 261, 7, 1, 0, 7936, 66576, 88101, 33855, 16066, 1890, 522, 8, 1, 0, 50521, 694599, 724189, 495371, 127538, 52022, 4260, 1040, 9, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,8

LINKS

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

FORMULA

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

EXAMPLE

p = 1432 is counted by T(4,2) because the up-down signature of 0,p = 01432 is 1,1,-1,-1 with partial sums 1,2,1,0.

q = 4321 is not counted by any T(4,k) because the up-down signature of 0,q = 04321 is 1,-1,-1,-1 with partial sums 1,0,-1,-2.

T(4,1) = 5: 2143, 3142, 3241, 4132, 4231.

T(4,2) = 11: 1324, 1423, 1432, 2134, 2314, 2413, 2431, 3124, 3412, 3421, 4123.

T(4,3) = 3: 1243, 1342, 2341.

T(4,4) = 1: 1234.

Triangle T(n,k) begins:

1;

0,    1;

0,    1,     1;

0,    2,     2,    1;

0,    5,    11,    3,    1;

0,   16,    38,   28,    4,   1;

0,   61,   263,  130,   62,   5,   1;

0,  272,  1260, 1263,  340, 129,   6, 1;

0, 1385, 10871, 8090, 4734, 819, 261, 7, 1;

MAPLE

b:= proc(u, o, c, k) option remember;

      `if`(c<0 or c>k, 0, `if`(u+o=0, 1,

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

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

    end:

A:= (n, k)-> b(n, 0$2, k):

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

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

MATHEMATICA

b[u_, o_, c_, k_] := b[u, o, c, k] = If[c < 0 || c > k, 0, If[u + o == 0, 1, Sum[b[u - j, o - 1 + j, c + 1, k], {j, 1, u}] + Sum[b[u + j - 1, o - j, c - 1, k], {j, 1, o}]]];

A[n_, k_] := b[n, 0, 0, k];

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

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

CROSSREFS

Columns k=0-10 give: A000007, A000111 for n>0, A259213, A316390, A316391, A316392, A316393, A316394, A316395, A316396, A316397.

Row sums give A258830.

T(2n,n) gives A266947.

Cf. A262124, A262125, A262163, A291722, A316292, A316293.

Sequence in context: A065066 A266291 A064045 * A110314 A152882 A130167

Adjacent sequences:  A258826 A258827 A258828 * A258830 A258831 A258832

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, Jun 11 2015

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 22 10:57 EDT 2018. Contains 316437 sequences. (Running on oeis4.)