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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s