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.
