A252814 Number of n X 2 nonnegative integer arrays with upper left 0 and every value within 2 of its city block distance from the upper left and every value increasing by 0 or 1 with every step right or down.

2, 6, 17, 40, 81, 147, 246, 387, 580, 836, 1167, 1586, 2107, 2745, 3516, 4437, 5526, 6802, 8285, 9996, 11957, 14191, 16722, 19575, 22776, 26352, 30331, 34742, 39615, 44981, 50872, 57321, 64362, 72030, 80361, 89392, 99161, 109707, 121070, 133291

Offset

1,1

Links

R. H. Hardin, Table of n, a(n) for n = 1..210

W. Kuszmaul, Fast Algorithms for Finding Pattern Avoiders and Counting Pattern Occurrences in Permutations, arXiv preprint arXiv:1509.08216 [cs.DM], 2015-2017.

Formula

Empirical: a(n) = (1/24)*n^4 + (5/12)*n^3 - (1/24)*n^2 + (7/12)*n + 1.

Conjectures from Colin Barker, Dec 06 2018: (Start)

G.f.: x*(2 - 4*x + 7*x^2 - 5*x^3 + x^4) / (1 - x)^5.

a(n) = 5*a(n-1) - 10*a(n-2) + 10*a(n-3) - 5*a(n-4) + a(n-5) for n>5.

(End)

Example

Some solutions for n=4:
..0..0....0..1....0..1....0..1....0..1....0..1....0..1....0..0....0..0....0..1
..0..1....0..1....1..2....1..2....0..1....0..1....1..2....1..1....1..1....1..2
..1..1....1..1....2..3....2..3....1..2....1..1....2..2....1..2....2..2....2..2
..2..2....1..2....2..3....3..4....2..2....2..2....3..3....1..2....2..3....2..2

Crossrefs

Column 2 of A252820.

Sequence in context: A037261 A239234 A192707 * A072077 A229732 A130104

Adjacent sequences: A252811 A252812 A252813 * A252815 A252816 A252817

Keyword

nonn

Author

R. H. Hardin, Dec 22 2014

Status

approved