Let be a positive integer. Consider all arrangements of identical green coins, identical white coins and identical orange coins in a row. Each such arrangement of coins can be considered as a sequence of blocks, where coins within a block have the same colour and any two adjacent blocks contain coins of two different colours. For example, for the case , the arrangement GGGOOWOOGWWWW is formed by 6 blocks, namely GGG, OO, W, OO, G and WWW.
Show that the average number of blocks, over all distinct arrangements of the coins, can be expressed in the form , and determine the values of the constants and .
Solution
For any arrangement, we say that a position is a change if and only if the coin at position has a different colour to the coin at position . Note that the number of blocks in any arrangement is one greater than the number of changes in that arrangement. For instance, the example arrangement given in the problem statement contains 5 changes (at positions 4, 6, 7, 9 and 10), and the number of blocks is .
Next we count the total number of changes in all distinct coin arrangements, partitioning the count according to the position at which the change occurs (denote this total number of changes by ). If position is a change, we can choose the coin at position in 3 ways and the coin at position in 2 ways. For the remaining positions we can arrange the coins in ways. Since the number of blocks is always one greater than the number of changes, we obtain
where the factor accounts for all of the possible change positions i.e., all possible values of .
Since the number of blocks is always one greater than number of changes, the total number of blocks over all distinct coin arrangements, is obtained from by adding , which is equal to the total number of distinct coin arrangements, hence
Thus the average number of blocks over all distinct coin arrangements is
Thus we have established the result, with and .