What problem in combinatorics-on-words could this be a formula for: $\frac{2^i i}{2}$?

Question

This came from a problem that I have solved, but it got me thinking.

Below is the original question I had to answer (as was translated to English by me just now):

G is a simple graph on 32 vertices, defined as follows:

A vertex in G is a 5-part-long string consisting of the letters a,b.

For example, the string aabab is a vertex in G. Likewise, aaaaa is a vertex in G.

Any two vertices x,y are connected by an edge if and only if the strings (vertrices) x,y coincide (are identical) in each of the five letters (parts/elements) of the string except one element.

For example, there is an edge between the vertex aabab to the vertex abbab, because these strings differ from each other only in one place (the second letter in the string).

What is the number of edges in G?

So I figured out that the answer is $80 = \frac{2^i i}{2}$ , where i is the length of the string, i.e. $\frac{2^5 \cdot 5}{2}$. If the string was 7-part-long, for example, the answer would be $448 = \frac{2^7 \cdot 7}{2}$.

But what if the strings had to differ in two places instead of one? I'm unsure what formula I would use then. Does this type of combinatorial problem have a name?

Answer 1

For any simple graph, the sum of the degrees is twice the number of edges.

If the strings have length $n$, and if an edge is defined as a mismatch at exactly $k$ positions, then each string has degree $\binom{n}{k}$.

Since there are $2^n$ strings, the sum of the degrees is $\binom{n}{k}2^n$, hence the number of edges is $\binom{n}{k}2^{n-1}$.

Answer 2

It helps to think in terms of binary vectors and bitwise modulo 2 addition (XOR). Map $a\rightarrow 0,b\rightarrow 1,$ say. Let $n$ be the length.

Consider all vectors of Hamming weight $k$ (with exactly $k$ 1's). There are $\binom{n}{k}$ such vectors. Let $$V_n=\{0,1\}^n.$$

Let $a$ be any word of weight $k$. Note that as $u$ ranges over $V_n,$ the pair $(u,u+a)$ ranges over the ordered pair of words that are exactly apart by the word $a$.

We want the unordered pair, so the answer is $\binom{n}{k} 2^{n-1},$ since $|V_n|=2^n.$