MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Hamming graphs and power series [closed]

Possible Duplicate:
Hamming graphs and power series

Let $i$ and $h$ be two adjacent nodes in a Hamming graph and let $a$ be any positive real. Let us denote by $d_{ij}$ the distance between node $i$ and node $j$ in the graph. I'm trying to find a compact formula for the following (finite) power series, where $j$ runs over all nodes of the graph:

$$S= \sum_j a^{d_{ij}+d_{hj} }. \tag{1}$$

Is this a studied problem?

If the graph is an $n$-hypercube, which is the case I'm most interested in, it seems that

$$S = \sum_{d=0}^n {{n-1}\choose {d}}a^{2d+1} + {{n-1}\choose {d-1}}a^{2d-1}\tag{2}$$

In fact, if you fix node $i$ and consider all the nodes at distance $d$ from $i$, ${{n-1}\choose {d}}$ of them are at distance $d+1$ from $h$, while the remaining ${{n-1}\choose {d-1}}$ are at distance $d-1$. However, I fail to see now how (2) can be further simplified.

I would appreciate any reference to this problem.

Thank you, M.

-
Doesn't (2) immediately simplify to $2\sum\limits_{d=0}^{n-1}\binom{n-1}{d}a^{2d+1}$ ? Which is $2a\left(a^2+1\right)^{n-1}$ by the binomial theorem? – darij grinberg Jan 27 2012 at 16:30
Darij, I'm glad we covered all copies of the question. Gerhard "Ask Me About System Design" Paseman, 2012.01.27 – Gerhard Paseman Jan 27 2012 at 16:35
Ops, yes, you are right :) Any suggestion for the more general case (1)? M. – Michele Jan 27 2012 at 16:38
Yes, but check the other copy for a suggestion. Gerhard "Ask Me About System Design" Paseman, 2012.01.27 – Gerhard Paseman Jan 27 2012 at 16:48