## Sözlük

Soldaki anahtar kelimelerden birini seçin…

# ProbabilityCounting

Okuma zamanı: ~30 min

We begin our study of probability with a closely related topic: counting.

We first learn to count the number of elements in a set by mentally traversing it while reciting a sequence of natural numbers: "one, two, three, ...". The last number recited when all elements have been counted is the number of elements in the set. However, that approach quickly becomes impractical if the set is large, and it doesn't yield much insight. Therefore, we will build up a toolkit of principles for reasoning about counting problems.

## The fundamental principle of counting

Exercise
If you flip a coin and roll a die, there are possible flip-roll pairs.

This exercise is a special case of the fundamental principle of counting:

Theorem (Fundamental principle of counting)
If one experiment has possible outcomes, and if a second experiment has possible outcomes for each of the outcomes in the first experiment, then there are possible outcomes for the pair of experiments.

One simple way to prove the fundamental theorem of counting is to observe that the possible outcomes for the pair of experiments can be arranged to form an rectangle:

The fundamental principle of counting may be used to solve problems that have a different setup than the flip-roll problem.

Exercise
The number of ordered triples of distinct elements from is .

Solution. This problem is different from the previous one because the choice for which number goes in the first slot in the tuple affects the subsequent choices. If we choose 3 first, then we can't choose it for the second or third slots. However, the number of options for each choice is the same regardless of the previous choices: we have four choices for the first slot, then three for the second (once the first choice has been made), then two for the third. Thus there are ordered triples.

So that it's extra clear there's no sleight of hand involved in this argument, here's a graphic organizer for all 24 triples and the choices made along the way:

We can generalize this idea to count the number of ordered -tuples of distinct elements of an -element set. We begin forming an -tuple by selecting any one of the possibilities for the first entry. Given any of the choices for the first entry, there are choices for the second entry. By the fundamental principle of counting, there are choices for the first two entries. Continuing in this way, we find that there are

choices for filling in all entries. We write as , read as " falling ".

Exercise
There are three-digit positive integers with distinct digits.

Note: a positive integer must be between 100 and 999 (inclusive) to count as a three-digit integer.

Solution. There are 9 choices for the first digit, then for any of those choices there are 9 choices for the second digit. Finally, given any pair of digits in the first two positions, there are 8 choices for the last entry. So there are choices in total.

## Binomial coefficients

The number of -element subsets of an -element set is denoted . Expressions of the form are called binomial coefficients.

Example
We have , since there are four ways to choose a 3-element subset of a 4-element set. The sets

are all of the 3-element subsets of .

To work out a general procedure for evaluating , we may first count the number of -tuples and then account for all of the repeats. For example, if , then the tuples

should collectively contribute 1, rather than 6, to the total count. Since every set of elements corresponds to $r$-tuples of distinct elements, we divide the number of -tuples by this number to obtain an expression for :

We often abbreviate the product as . Thus

Exercise
Of the 1024 total length-10 strings composed of the symbols H and T, of them have exactly 6 T's and 4 H's. (For example, HHTHTTTHTT is one such string).

Solution. For each 6-element subset of the 10 positions in the string, we can place T's in those six positions and H's in the remaining positions to get a sequence of the given description. Therefore, there are total strings with exactly 6 T's.

Exercise (Principle of Inclusion-Exclusion)
Let be the set of natural numbers up to and including . Let the subset of integers divisible by , and the subset of integers divisible by .

• Compute .
• Compute .
• Compute .
• Explain why .
• Use the prior steps to find .

Solution.

• There are multiples of between and Including zero in the count as well, we get

• There are multiples of between and Adding 1 to account for zero gives

• Elements of are zero and multiples of in It thus follows that

• gives the numer of elements that are in but not in Adding gives the total number of elements in

• Using values calculated above, we have

Exercise
The English alphabet has subsets. (Hint: you can get Bruno to do arithmetic calculations for you!)

For example, and are two such subsets.

Solution. There are subsets of the alphabet, because we can form a subset by choosing for each letter whether to include it or exclude it. By the fundamental principle of counting, the number of ways to make these 26 choices is .

Exercise
Expand the algebraic expression . Show that the coefficients of this expansion are given by the binomial coefficients of the form where ranges from 0 to 3:

Write an analogous expansion for .

Solution. The first equation holds since both sides work out to . The second holds since both sides are equal to

Generally, we have

because a term of the form is formed when expanding the product if and only if the was selected from of the factors and was selected from the remaining factors. This can happen in ways, so the coefficient of is .

Bruno