A375085 Triangle read by rows: T(n,k) is the number of ballotlike paths ending at (n, k), with 0 <= k <= n.

0, 0, 1, 1, 1, 1, 2, 3, 2, 1, 5, 9, 6, 3, 1, 14, 28, 21, 10, 4, 1, 42, 90, 76, 39, 15, 5, 1, 132, 297, 276, 159, 64, 21, 6, 1, 429, 1001, 1002, 643, 288, 97, 28, 7, 1, 1430, 3432, 3641, 2555, 1281, 475, 139, 36, 8, 1, 4862, 11934, 13261, 10004, 5536, 2300, 733, 191, 45, 9, 1

Offset

0,7

Comments

A ballotlike path is a lattice path in the 1st quadrant starting at (0, 0) and ending at (n, k) which uses the steps U = (1, 1), D = (1, -1), u = (1, 0) (for upstairs or umber) and d = (1, 0) (for downstairs or denim), subject to the conditions that the umber horizontal steps do not occur at height zero and the denim horizontal steps do not occur before the first down step. See pp. 8-10 in Lazar and Linusson.

Links

Table of n, a(n) for n=0..65.

Alexander Lazar and Svante Linusson, Two-Row Set-Valued Tableaux: Catalan+k Combinatorics, Proceedings of the 36th Conference on Formal Power Series and Algebraic Combinatorics (Bochum), Séminaire Lotharingien de Combinatoire 91B (2024) Article #80, 12 pp. See p. 10.

Formula

T(n,k) = binomial(2*n-2,n-k-1) - binomial(2*n-2,n-k-2) + binomial(n-2,n-k).

T(n,0) = A000108(n-1).

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

T(n+1,2) - T(n,2) = A026013(n-1) for n > 2.

Example

Triangle begins:
    0;
    0,   1;
    1,   1,   1;
    2,   3,   2,   1;
    5,   9,   6,   3,  1;
   14,  28,  21,  10,  4,  1;
   42,  90,  76,  39, 15,  5, 1;
  132, 297, 276, 159, 64, 21, 6, 1;
  ...

Mathematica

T[n_, k_]:=Binomial[2n-2, n-k-1]-Binomial[2n-2, n-k-2]+Binomial[n-2, n-k]; Table[T[n, k], {n, 0, 10}, {k, 0, n}]//Flatten

Prog

(Python)
from math import isqrt
from sympy import binomial
def A375085(n):
    a = (m:=isqrt(k:=n+1<<1))-(k<=m*(m+1))
    b = n-binomial(a+1, 2)
    return int(binomial(c:=a-1<<1, d:=a-b-1)-binomial(c, d-1)+binomial(a-2, d+1)) if n else 0 # Chai Wah Wu, Nov 14 2024

Crossrefs

Cf. A000108, A026013, A057427 (diagonal), A071724, A375086 (row sums).

Sequence in context: A238165 A081316 A226362 * A228549 A079893 A324646

Adjacent sequences: A375082 A375083 A375084 * A375086 A375087 A375088

Keyword

nonn,tabl

Author

Stefano Spezia, Jul 29 2024

Status

approved