6.2 PARTITIONS AND BIJECTIONS 203Example 6.2.6 Imagine a piece of graph paper. Starting at the origin draw a path to
the point (10, 10) that stays on the grid lines (which are one unit apart) and has a total
length of 20. For example, one path is to go from (0,0) to (0,7) to (4,7) to ( 4 ,10)
to (10, 10). Another path goes from (0, 0) to (10, 0) to (10, 10). How many possible
different paths are there?
Solution: Each path can be completely described by a 20-1etter sequence of U's
and R's, where "U" means "move one unit up" and "R" means "move one unit to the
right." For example, the path that goes from(O, 0) to (0, 7 ) to (4,7) to (4, 10 ) to (10, 10)
would be described by the string
UUUUUUURRRRUUURRRRRR.
'--v-""-v-"-..,.....-�
7 4 3 6
Since the path starts at (0, 0) , has length 20, and ends at (10, 10), each path must have
exactly IOU's and lO R's. Hence the total number of paths is just a simple Mississippi
problem, whose answer is20! ( 20 )
1O!1O!
=
10. •
The next example can be done by partitioning as well as encoding, although the
encoding solution is ultimately more productive.
Example 6.2.7 How many different ordered triples (a, h, e) of non-negative integers
are there such that a + h + e = 50?
Solution: We will present two completely different solutions, the first using par
titioning, the second using encoding. First, it is easy to see that for each non-negative
integer n, the equation a + h = n is satisfied by n + 1 different ordered pairs (a, h),
namely
(O,n), (l,n -1), (2,n -2), ... , (n, O).
So we can partition the solutions of a + h + e = 50 into the disjoint cases where c =
O,e = l,e = 2, ... ,e = 50. For example, if e = 17, then a +h = 33 so there will be 34
different ordered triples (a, h, 17 ) that satisfy a + h + e = 50. Our answer is therefore
51 · 52
1 +2+3+ .. ·+51 = -
2-'
The problem was solved easily by partitioning, but encoding also works. To see
how, let us replace 50 with a smaller number, say, 11, and recall how we first learned
about addition in first or second grade. You practiced sums like "3 + 6 + 2 = II" by
drawing sequences of dots:
••••••••••••Each ordered triple (a,h , e) of non-negative integers that sum to 11 can be thought of
as an allocation of 11 dots, separated by two plus signs. The triple (3, (^6) ,2) can be
encoded by the string ••• + •••••• + ••. Zero is not a problem; we encode it with
no dots. Hence + + ••••••••••• corresponds to (0, 0, 11) and ••••• + + ••••••