TITLE: For any positive integer $n$, let$ G_n$ be the graph whose vertices are all binary string of length $n$
QUESTION [0 upvotes]: For any positive integer $n$, let $G_n$ be the graph whose vertices are all binary string of length $n$ that have precisely two block of 1's, each of which is of length at most 3, and two vertices are adjacent if and only if the corresponding strings differ in exactly one position. Determine the number of vertices in $G_n$ and edges in $G_n$
I couldn't understand how to create this graph. Anyone please help me
Hints: let string 10011. $B_1= 1$ length of 1 and $b_2=11$ length 2

REPLY [1 votes]: The number of strings of length $n$ having exactly two blocks of $1$'s, the first of length $a$, the second of length $b$, is readily computed to equal $n+1-a-b\choose2$, provided $n\ge a+b$. This gives us the number of vertices as
$$v_n={n-1\choose 2}+2{n-2\choose 2}+3{n-3\choose 2}+2{n-4\choose 2}+{n-5\choose 2} =\frac{9n(n-7)}{2}+60$$
To count the edges, let's count from their end point with more $1$'s: From each block of length $2$ or $3$, we can toggle eithre the first or the second bit. Hence the number of edges is 
$$e_n=2{n-2\choose 2} +8{n-3\choose 2}+8{n-4\choose 2}+4{n-5\choose 2}=11n^2-91n+194$$
Note howeverm that both formulas hold only for $n\ge 5$. For smaller $n$, those binomals with negative "numerator" have to be dropped. Thus
$$v_1=v_2=0; \quad v_3=1; \quad v_4= 5;\quad v_{n\ge 5}=\frac{9n(n-7)}{2}+60$$
and
$$e_1=e_2=e_3=0;\quad e_4=2;\quad e_{n\ge 5}=11n^2-91n+194. $$
{"set_name": "stack_exchange", "score": 0, "question_id": 1796815}