Doubt in the solution of a competition combinatorial problem concerning the average number of times the letters of a sequence change I am currently going through  Andreescu's 102 combinatorial problems. I couldn't solve number 28 after repeated attempts, so I checked the solution. The problem and solution go as follows:

However, I do not understand why summing the $N_i$'s and dividing over $20!$ is the average. As I see it, if $S_i$ denotes the number of rows with $i$ boy-girl or girl-boy appearances in the row, the average should be
$\dfrac{\sum_{i=2}^{13}iS_i}{\binom{20}{7}}$.
I was hoping that someone would throw some light on why my formula is incorrect and the logic behind the solution (I am relatively new to combinatorial problems in competitions.)
 A: 
I was hoping that someone would throw some light on why my formula is incorrect and the logic behind the solution

Your approach, which I discuss in the Addendum, focuses on the expected number of rows with $i$ [BG or GB] appearances.
The offered solution takes a totally different approach.  Instead, the offered solution examines each of the $(20)!$ possible seatings, and determines how many of these seatings have [BG or GB] starting in position $i$.

A simpler problem will allow you to visualize the distinction.
Suppose that you were going to examine the $10000$ $4$-digit numbers, where each number was zero-filled on the left, and the numbers ranged from $0000$ through $9999.$
You might then ask, in these $10000$ numbers, how many times does the digit $1$ appear?  You then have two choices for attacking the problem:

*

*You can ask: how many of the $10000$ numbers will have $k$ $1$'s, where $k$ is some element in $0,1,2,3,4$?  This corresponds to the approach that you are taking.


*You can ask: how many occurrences of the digit $1$ will occur in the leftmost digit?  Assume that this computation is $d_1$.  Then, you can ask the same question for the number of occurrences in the digit $1$ in the 2nd, 3rd, and 4th positions from the left.  If you denote these computations as $d_2, d_3, d_4,$ respectively, then the (overall) desired computation is $d_1 + d_2 + d_3 + d_4$.
The 2nd approach above corresponds to the method taken in the given solution.  One key difference in the original problem, and the sample problem above, is that an occurrence of a $1$ in (for example) the leftmost digit is an independent event compared to the occurrence of a $1$ in one of the other positions.
In the original problem, the analogous events are not independent.  That is, if there is a BG beginning in position 1, this affects whether there is a GB beginning in position 2, because one of the B's has been already used.
However, if you examine this linearity of expectation article, you will find a proof that linearity of expectation holds even when the events are not independent.

Addendum

As I see it, if $S_i$ denotes the number of rows with $i$ boy-girl or girl-boy appearances in the row, the average should be


$\dfrac{\sum_{i=2}^{13}iS_i}{\binom{20}{7}}$.

Your approach is valid, but incomplete.  Your denominator of $~\displaystyle \binom{20}{7}~$ reflects the number of ways that the $7$ boys could be seated.
If you index each of these seatings, as $~\displaystyle A_1, A_2, \cdots, A_n ~: ~n = \binom{20}{7},~$ and you left $f(k)$ denote the number of [BG or GB] occurrences in seating number $A_k$, then you can compute the average number of [BG or GB]
occurrences as
$$\frac{\large\sum_{k=1}^\binom{20}{7} f(k)}{\binom{20}{7}}.$$
Your approach, which is also valid, is similar.
In your approach, you would cycle through each of
$$~f(1), f(2), \cdots, f(n) ~: ~n = \binom{20}{7}~$$ and determine how many of these values were equal to $i$, for $i$ equal to some value in $\{1,2,\cdots,14\}$.  If you let $S_i$ determine how many of the $\displaystyle ~\binom{20}{7}~$ seatings have $i$ occurrences, then you can compute the average as
$$\frac{\sum_{i=1}^{14} iS_i}{\binom{20}{7}}.$$
There are however, two defects in your approach:

*

*For some reason, you chose to have the summation go from $2$ through $13$, rather than $1$ through $14$.


*You gave no analysis of how you might analytically compute $S_i$.  It may be argued that the solution provided was given because the computation's analysis is so elegant.  This leaves open the question: how would you pursue your approach?
A: Because both of my previous answers are so long-winded, I am adding a 3rd answer as a separate response.  This answer represents a hybrid approach that combines Stars and Bars theory with Linearity of Expectation.  This response has some similarities and some difference to both my (other) Stars and Bars answer, and the official solution given in the original posting.
For Stars and Bars theory, see
this article and
this article.
For a discussion of Linearity of Expectation, including a proof that Linearity of Expectation holds when it is applied to dependent events, see this article.
When the $7$ boys are placed anywhere in the row of $20$ positions, they create $8$ regions.  One region before the first boy (on the left), and then one region after each of the boys.
Consider the number of solutions to

*

*$x_1 + x_2 + \cdots + x_8 = 13.$


*$x_1, x_2, \cdots, x_8 \in \Bbb{Z_{\geq 0}}.$
As expected, the number of solutions is
$\displaystyle \binom{13 + [8-1]}{8-1} = \binom{20}{7}.$
Let $P$ denote the probability that in any of the $~\displaystyle \binom{20}{7}~$ solutions chosen at random, the variable $~x_4~$ is $~\geq 1.$
$P$ may be calculated as follows:
Consider the revised equation:

*

*$x_1 + x_2 + \cdots + x_8 = 13.$


*$x_4 \in \Bbb{Z_{\geq 1}}, ~~~~x_1, x_2, x_3, x_5, x_6, x_7, x_8 \in \Bbb{Z_{\geq 0}}.$
Settng $y_4 = x_4 - 1,$ the revised equation bijects to :

*

*$y_4 + x_1 + x_2 + x_3 + x_5 + x_6 + x_7 + x_8 = (13 - 1) = 12.$


*$y_4 \in \Bbb{Z_{\geq 0}}, ~~~~x_1, x_2, x_3, x_5, x_6, x_7, x_8 \in \Bbb{Z_{\geq 0}}.$
Per Stars and Bars theory, the revised equation has 
$\displaystyle \binom{12 + [8-1]}{8-1} = \binom{19}{7} ~$ solutions.
Therefore, the probability that a random solution has $x_4 \geq 1$ can be computed as
$$P = \frac{\binom{19}{7}}{\binom{20}{7}} = \frac{13}{20}.$$
Further, by reasons of symmetry, the same computation of $P$ applies to any of the other variables.  Thus, for $i \in \{1,2,3,\cdots,8\}$, the probability that a random solution to
$x_1 + \cdots + x_8 = 13 ~: ~x_1, \cdots, x_8 \in \Bbb{Z_{\geq 0}}$ 
will have $x_i \geq 1$ is $~\displaystyle P = \frac{13}{20}.$
An occurrence of [G:Boy-1] will occur if and only if $x_1 \geq 1.$
An occurrence of [Boy-7:G] will occur if and only if $x_8 \geq 1.$
For $i \in \{2,3,\cdots,7\}$

*

*an occurrence of [Boy-(i-1):G] occurs 
if and only if


*$x_i \geq 1, ~$ which occurs 
if and only if


*an occurrence of [G:Boy-i] occurs.
Therefore, by Linearity of Expectation, the expected combined number of occurrences of [GB] or [BG] is
$$[1 \times P] + [6 \times 2 \times P] + [1 \times P]$$
$$= 14 \times P = 14 \times \frac{13}{20} = \frac{182}{20} = 9.1.$$
A: Sometimes it is helpful to reduce the problem to smaller numbers so that it can be calculated manually. Here we take $5$ instead of $20$ persons and consider a group of two boys and three girls.
\begin{align*}
\{B_1,B_2,G_1,G_2,G_3\}\tag{1}
\end{align*}
In order to analyse the situation it is sufficient to consider the
\begin{align*}
\color{blue}{\binom{5}{2}=10}
\end{align*}
different rows
\begin{align*}
\begin{array}{l|c}
B\quad B\color{blue}{\bullet} G\quad G\quad G&1\\
B\color{blue}{\bullet} G\color{blue}{\bullet} B\color{blue}{\bullet} G\quad G&3\\
B\color{blue}{\bullet} G\quad G\color{blue}{\bullet} B\color{blue}{\bullet} G&3\\
B\color{blue}{\bullet} G\quad G\quad G\color{blue}{\bullet} B&2\\
G\color{blue}{\bullet} B\quad B\color{blue}{\bullet} G\quad G&2\\
G\color{blue}{\bullet} B\color{blue}{\bullet} G\color{blue}{\bullet} B\color{blue}{\bullet} G&4\\
G\color{blue}{\bullet} B\color{blue}{\bullet} G\quad G\color{blue}{\bullet} B&3\\
G\quad G\color{blue}{\bullet} B\quad B\color{blue}{\bullet} G&2\\
G\quad G\color{blue}{\bullet} B\color{blue}{\bullet} G\color{blue}{\bullet} B&3\\
G\quad G\quad G\color{blue}{\bullet} B\quad B&1
\end{array}
\end{align*}
Each of these rows represents the $2!\cdot 3!=12$ pairwise different configurations when we use the elements from (1) giving a total of $12\cdot 10=5!$ rows. But this is not so important, as we can only focus on $BG$ and $GB$ combinations which are marked with $\color{blue}{\mathrm{blue}}$ dots.
One approach:
We get the multiplicities from the right-most column of the table above and derive according to OPs approach
\begin{align*}
\color{blue}{\frac{1\cdot S_1+2\cdot S_2 + 3\cdot S_3+4\cdot S_4}{\binom{5}{2}}}=\frac{1\cdot 2+2\cdot 3+3\cdot 4+4\cdot 1}{10}
\color{blue}{=2,4}
\end{align*}
Another approach:
We focus on the combinations $BG$ and $GB$ for each of the four position pairs $(1,2), (2,3), (3,4), (4,5)$.
\begin{align*}
\begin{array}{ccccc}
B&G&\cdot&\cdot&\cdot\\
\cdot&B&G&\cdot&\cdot\\
\cdot&\cdot&B&G&\cdot\\
\cdot&\cdot&\cdot&B&G\\
G&B&\cdot&\cdot&\cdot\\
\cdot&G&B&\cdot&\cdot\\
\cdot&\cdot&G&B&\cdot\\
\cdot&\cdot&\cdot&G&B\\
\end{array}
\end{align*}
We fix a specific position $j, 1\leq j\leq 4$ and let's say the combination $BG$. We calculate the probability of the event that $BG$ occurs at a specific position $j$ by dividing the favorable number of possibilities by the total number which is as we have two boys and three girls:
\begin{align*}
\color{blue}{\frac{2\cdot 3}{5\cdot 4}}\tag{2}
\end{align*}
We note that (2) is strongly related with $N_j$ from OPs problem, since we can (2) write as
\begin{align*}
\frac{2\cdot 3}{5\cdot 4}=\frac{2\cdot 3\cdot 3!}{5\cdot 4\cdot 3!}=\frac{2\cdot 3\cdot 3!}{5!}\tag{3}
\end{align*}
Doubling (3) since we have to respect $BG$ as well as $GB$ at a specific position and using the linearity of expectation we calculate according to (2) and (3)
\begin{align*}
\color{blue}{\frac{N_1+N_2+N_3+N_4}{5!}}=4\cdot \frac{2 (2\cdot 3) 3!}{5!}=4\cdot\frac{ 2(2\cdot 3)}{5\cdot 4}\color{blue}{=2,4}
\end{align*}
and both results coincide.
