Suppose $n \geq 4$. Show that in a list of all $2^{n−1}$ compositions of $n$, the integer 3 occurs exactly $n\cdot 2^{n-5}$ times. (Hint: As in lectures, look at ways of drawing lines between $n$ dots.)
I understand that for 4, say, you draw a line between the 1st and 2nd dot and then you have the partition (1,3) and also drawing a line between the 3rd and 4th dot gives you the partition (3,1). There's the two examples for 4.
It's when you get to the examples for $n \geq 4$ that I struggle. I know that there will be a sum ...+3+... and that the numbers on either side of the 3 are important but how this then gets to $n \cdot 2^{n-5}$ is where I lose track.
I don't have an example like this in my lecture notes. Only the formulas to say that the number of compositions of n is $2^{n-1}$ and a diagram explaining how the dots and bars works to find total compositions of n but nothing on how these could be used to find the number of compositions containing a specific integer.
Imagine if you will making this "dots and bars" representation for every possible composition and laying them out in a grid.
$$\begin{array}{cccccccc}\bullet &\bullet &\color{red}{\mid \bullet} &\color{red}{\bullet} &\color{red}{\bullet} &\color{red}{\mid} \bullet &\mid\bullet&\cdots\\\bullet &\bullet &\mid \bullet &\mid\bullet &\bullet &\mid \bullet& \bullet&\cdots\\\bullet &\mid\bullet &\mid \bullet &\mid\bullet &\bullet &\mid \bullet &\bullet&\cdots\\\bullet&\color{red}{\mid\bullet}&\color{red}{\bullet}&\color{red}{\bullet}&\color{red}{\mid}\bullet&\bullet&\mid\bullet&\cdots\\&&\vdots&&\vdots\end{array}$$
The above example corresponding to $2+\color{red}{3}+1+\dots,~2+1+2+\dots,1+1+1+2+\dots,1+\color{red}{3}+2+\dots$ etc...
Now... let us count the number of $3$'s in a partition that occur not by organizing our thoughts into rows of the grid... but rather organize our thoughts in terms of columns.
We count how many partitions have a pattern $\color{red}{\mid \bullet\bullet\bullet\mid}$ which started in column $k$ for each $k$ from $2$ to $n-3$. (We focus our attention at the moment on those which occur central in the grid, not on the edge. We consider the literal edge cases later)
Well, to count these, we note that the bar on the left of the pattern must be present, the two places for bars in the middle must be empty and the bar on the right must be present. All other positions of bars can either be present or not be present with no restriction. There are $n-1$ possible positions for bars in general, $4$ of which have their state pre-determined since we are considering where those positions gave rise to a $3$ in the composition, leaving $n-1-4=n-5$ positions remaining to decide whether they have or do not have a bar. This gives rise to $2^{n-5}$ compositions who have a $3$ in the desired columns within our grid.
Note, we do not care that we have double-counted some of these compositions which had multiple $3$'s because we wanted such compositions to have contributed to our total multiple times... once for each of the $3$'s within the composition which is exactly what we have done.
Since there are $n-4$ different choices for which "inner columns" we could have considered, this gives us $(n-4)\cdot 2^{n-5}$ occurrences of $3$ within compositions we have counted so far.
Now, we still need to count the edge cases where our composition began with a $3$ or ended with a $3$. In these scenarios, we only have $n-4$ remaining positions for bars to worry about whether they were included or not, not $n-5$, giving $2^{n-4}=2\cdot 2^{n-5}$ for those which began with a $3$ and the same for those ending with a $3$.
This gives us a final total of:
$$(n-4)\cdot 2^{n-5}+2\cdot 2^{n-5}+2\cdot 2^{n-5}=(n-4+2+2)\cdot 2^{n-5}=n\cdot 2^{n-5}$$
occurrences of $3$'s within the collection of all compositions of $n$.