Question

The exact probabilities of equation \((9-9)\) rest on the claim that the number of ways of adding \(N\) distinct nonnegative integers to give a total of \(M\) is \((M+N-1) !\) \([M !(N-1) !]\). One way to prove it involves the following trick. It represents two ways that \(N\) distinct integers can add to \(M-9\) and 5 , respectively, in this special case. $$ \begin{array}{c|cccccccccccccc} \hline \text { 1 } & \text { X } & \text { X } & \text { X } & \text { I } & \text { I } & \text { X } & \text { I } & \text { I } & \text { I } & \text { I } & \text { X } & \text { I } & \text { I } \\ \hline 2 & \text { I } & \text { X } & \text { X } & \text { I } & \text { I } & \text { I } & \text { I } & \text { X } & \text { I } & \text { I } & \text { I } & \text { X } & \text { X } \\ \hline \end{array} $$ The X's represent the total of the integers, \(M\) - each row has \(5 .\) The I's represent "dividers" between the distinct integers, of which there will of course be \(N-\) I -each row has 8 . The first row says that \(n_{1}\) is 3 (three \(X\) 's before the divider between it and \(n_{2}\) ). \(n_{2}\) is 0 (no \(X\) 's between its left divider with \(n_{1}\) and its right divider with \(\left.n_{3}\right), n_{3}\) is \(1, n_{4}\) through \(n_{6}\) are \(0, n_{2}\) is \(1,\) and \(n_{8}\) and \(n_{9}\) are 0\. The second row says that \(n_{2}\) is \(2, n_{6}\) is \(1, n_{9}\) is \(2,\) and all other \(n\) are 0 . Further rows could account for all possible ways that the integers can add to \(M\). Argue that. properly applied, the binomial coefficient (discussed in Appendix J) can be invoked to give the correct total number of ways for any \(N\) and \(M\).

Short answer

The total number of ways of adding N distinct non-negative integers to give a total of M can be represented by the binomial coefficient \((M+N-1)C(M)\) which is equivalent to \((M+N-1)!/[M!(N-1)!]\).

Step-by-step solution

Understand the representation

In the given tables, the X's represent the total of the integers M, each row has 5 X's. The I's represent 'dividers' between the distinct integers, of which there will be \(N-1\), each row has 8 I's. The first row interprets that \(n_1\) is 3 (three X’s before the divider) and \(n_2\) is 0 (no X's between its left divider with \(n_1\) and its right divider with \(n_3\)), similarly all \(n_i\) are defined. The second row does the same.

Analogy to combination formula

Every distinct set of N non-negative integers summing to M corresponds to a unique arrangement of M X's and N-1 I's, and vice versa. Therefore, counting these arrangements will give us the number of ways to choose N non-negative integers that sum to M. The total number of arrangements for \(M+N-1\) elements including M identical X's and \(N-1\) identical I's can be found using the combination formula \((M+N-1)!/[M!(N-1)!]\).

Relate to binomial coefficient

\((M+N-1)!/[M!(N-1)!]\) can be written as a binomial coefficient as \((M+N-1)C(M)\). Therefore, we conclude that, properly applied, the binomial coefficient can be invoked to give the correct total number of ways for any N and M.

Key concepts

Combinatorics

Combinatorics is the branch of mathematics focused on counting, arrangement, and combination of elements within sets. It's like finding all possible ways to organize things.
In the context of the given problem, combinatorics helps us determine how numerous distinct non-negative integers can sum up to a particular number. It's about placing markers (the X's) and dividers (the I's) in such a way that each combination provides a distinct solution.
For example, let's say you have M X's and N-1 I's to arrange in a row. Every unique arrangement gives you a new set of integers whose sum is fixed. The number of such unique arrangements can be calculated using the formula \((M+N-1)!/[M!(N-1)!]\). This formula is derived from the concept of combinations, which is a fundamental part of combinatorics.

Probability Distributions

Probability distributions describe how probabilities are assigned to different outcomes of a random variable. They help predict how likely certain events are.
In our situation, combinatorics isn't directly about probability, but it forms a basis for understanding probability distributions. When you're counting various ways of forming sums with integers, you are exploring the distribution of sums.

By using binomial coefficients, you can connect combinatorial counting (like arranging the X's and I's) to probability. These coefficients determine the probability of each possible arrangement occurring, which mirrors how probabilities are distributed across possible outcomes.

Thus, we can see that a deep understanding of combinatorial problems can augment our grasp of probability distributions by highlighting possible outcomes and their likelihood.

Integer Partitions

Integer partitions involve expressing a number as the sum of other numbers. Think of it like breaking a number into pieces in different ways. Each arrangement of the X's and I's is a different partition of the integer M.
For instance, if you have a fixed total M, every combination of non-negative integers that sum up to M represents a distinct partition.

• The task is to find out how many such partitions exist for given values of M and N.
• This is where our formula, \((M+N-1)!/[M!(N-1)!]\), becomes crucial. It essentially tells us how many different ways the integer M can be split into N distinct parts.
• By applying this formula, you're figuring out all possible integer partitioning of M using N distinct nonnegative integers.

Through understanding integer partitions, you better grasp the concept of divisions within sets, emphasized by the exercise we've discussed.