A393140 - OEIS

A393140

Triangle read by rows. T(n, k) = C(n, k)*C(k, floor(k/2))*Sum_{i=0..k} C(k, i)*C(n-i, floor((n-i)/2)).

1, 1, 2, 2, 6, 10, 3, 15, 48, 39, 6, 36, 168, 264, 210, 10, 80, 500, 1170, 1830, 960, 20, 180, 1380, 4260, 9900, 10260, 5340, 35, 385, 3570, 13755, 42420, 65520, 67620, 26250, 70, 840, 8960, 41160, 157920, 323680, 498400, 384440, 148610

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

T(n, n - k) is the number of length-n walks on N^2 (the first quadrant of Z^2) by a king starting at (0, 0) of which k moves are horizontal. - Natalia L. Skirrow, Mar 06 2026

LINKS

Paolo Xausa, Table of n, a(n) for n = 0..11475 (rows 0..150 of the triangle, flattened).

FORMULA

Using the notation a // b := floor(a / b).

T(n, k) = ((n - k + 1) * T(n, k - 1) + n * T(n - 1, k - 1)) // ((k + 1) // 2) for k > 0, and C(n, n // 2) for k = 0.

T(n, k) = A107230(n, n - k) * A393138(n, k).

EXAMPLE

Triangle starts:

[0] [ 1]

[1] [ 1, 2]

[2] [ 2, 6, 10]

[3] [ 3, 15, 48, 39]

[4] [ 6, 36, 168, 264, 210]

[5] [10, 80, 500, 1170, 1830, 960]

[6] [20, 180, 1380, 4260, 9900, 10260, 5340]

[7] [35, 385, 3570, 13755, 42420, 65520, 67620, 26250]

[8] [70, 840, 8960, 41160, 157920, 323680, 498400, 384440, 148610]

MATHEMATICA

A393140[n_, k_] := A393140[n, k] = If[k == 0, Binomial[n, Quotient[n, 2]], Quotient[(n-k+1)*A393140[n, k-1] + n*A393140[n-1, k-1], Quotient[k+1, 2]]];

Table[A393140[n, k], {n, 0, 10}, {k, 0, n}] (* Paolo Xausa, Mar 09 2026 *)

PROG

(Python)

from math import comb

from functools import lru_cache

@lru_cache(maxsize=None)

def T(n: int, k: int) -> int:

if k == 0: return comb(n, n // 2)

return ((n - k + 1) * T(n, k - 1) + n * T(n - 1, k - 1)) // ((k + 1) // 2)

for n in range(9): print([T(n, k) for k in range(n + 1)])

CROSSREFS

T(n,0) = A001405, T(n,n) = A151312, A151331 (row sums).