login
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

%I #11 Dec 06 2018 10:10:05

%S 2,6,17,40,81,147,246,387,580,836,1167,1586,2107,2745,3516,4437,5526,

%T 6802,8285,9996,11957,14191,16722,19575,22776,26352,30331,34742,39615,

%U 44981,50872,57321,64362,72030,80361,89392,99161,109707,121070,133291

%N 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.

%H R. H. Hardin, <a href="/A252814/b252814.txt">Table of n, a(n) for n = 1..210</a>

%H W. Kuszmaul, <a href="http://arxiv.org/abs/1509.08216">Fast Algorithms for Finding Pattern Avoiders and Counting Pattern Occurrences in Permutations</a>, arXiv preprint arXiv:1509.08216 [cs.DM], 2015-2017.

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

%F Conjectures from _Colin Barker_, Dec 06 2018: (Start)

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

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

%F (End)

%e Some solutions for n=4:

%e ..0..0....0..1....0..1....0..1....0..1....0..1....0..1....0..0....0..0....0..1

%e ..0..1....0..1....1..2....1..2....0..1....0..1....1..2....1..1....1..1....1..2

%e ..1..1....1..1....2..3....2..3....1..2....1..1....2..2....1..2....2..2....2..2

%e ..2..2....1..2....2..3....3..4....2..2....2..2....3..3....1..2....2..3....2..2

%Y Column 2 of A252820.

%K nonn

%O 1,1

%A _R. H. Hardin_, Dec 22 2014