# Counting K successive elements in an N-d grid

An work colleague from a prior job, thinking I must be some kind of math genius, posed this question:

1) 2D: $a b' + b a' + 2 a'b'$

2) 3D: $abc'+ab'c+a'bc+2ab'c'+2a'bc'+2a'b'c+4a'b'c'$

3) 4D: $a'bcd+ab'cd+abc'd+abcd'+2a'b'cd+2a'bc'd+2a'bcd'+2ab'c'd+2ab'cd'+2ac'd'+4a'b'c'd+4a'bc'd'+4ab'c'd'+8a'b'c'd'$

Do you happen to come up with a generalized formula up to n- dimensions (it wouldn’t need to be with letters necessarily).

Obviously I see the progression here but my question on how to express more graciously for any general case.

I fiddled with it and replied:

For the 2D case you can let $x=(a,b)$ then you have

$\sum_{i=1}^2 x'_i \times(x_{3-i}+x'_{3-i})$

It’s ugly and doesn’t look like anything.  Context?

He replied:

Its the solution from 2D to 4D  (and extrapolated, to $n$-dimensions) of the following problem:  Assume you want to establish how many possibilities there are to count $k$ successive elements in a 2D (or nD Grid).

Do you remember the kids game “Connect Four”? Well, that’s an example of this problem, how many ways are there to count 4 elements adjacent to each other (horizontally, vertically and in diagonals) in a 6 x 7 grid or lattice.

in 2D $a'$ and $b'$ are the respective solutions in each dimension: Given a grid of $a$ times $b$ and you want $k$ elements, $a'=a-k+1$ and $b=b-k+1$ (in other words this is the number possible solutions in each row and column; the $2a'b'$ are the ones which correspond to all the diagonals.

I think there has to be an elegant solution to it (in terms of a nice formula), but as I said, it can be easily be extended into higher dimensions.

For Connect4 I found  a few references:

Beyond that, I’m not seduced by this kind of problem and/or don’t have the skills or aptitude.