Mth 232 Discrete Math
Mth 232 Note - Spring 1999		Leonhard Euler 1707-1783

k-combinations with repetition according to Euler

The formula for the number of  k-combinations with repetition was derived by Leonhard Euler (1707-1783). Euler's argument goes as follows:

Suppose we have  n  distinct objects. We can label them with the integers from  1  to  n.  Now consider a  k-combination, that is, an unordered selection of  k  integers, possibly with repetitions, from among 1....n, say  i₁, i₂, ..., i_k.  Even though we do not care about the order, we can certainly arrange the selected integers in order, for convenience in counting the possibilities. Suppose therefore that the sequence  i₁, i₂, ..., i_k  is in nondecreasing order (that is, increasing, but not strictly). Then the sequence

i₁, i₂+1, i₃+2, ..., i_k+(k-1)

is a strictly increasing sequence of  k  integers selected from the integers from  1  to  n+k-1.  Moreover each such sequence can occur. The number of such sequences is the number of  k-combinations, without repetition, from  n+k-1  distinct objects. Thus the number of  k-combinations, with repetitions, from  n  distinct object is

Here is another way to view k-cominations: suppose we have n distinct cells (boxes) and k indistinguishable objects (think of x's) to place in the cells. How many ways can it be done? Order the cells, so we can refer to them by number. Lay out the objects (the x's) in a line. Place dividers between them to divide them into lots that go in successive cells. We will require n-1 dividers. A configuration of objects and dividers looks like

Now the configuration above can also be described without the dividers simply by labelling each x according to the cell it goes in, for example by using succesive letters of the alphabet. Thus the configuration above could be described by

Mth 232 Index