An urn contains blue and red balls. If we draw $n$ balls from it with replacement, how many outcomes are possible?
First observe that it does not matter how many blue and red balls are
in the urn, as long as there are of both colors. Since balls are
placed back into the urn (with replacement) after they are
drawn, there is always a supply of both colors. Knowledge of how many
blue and how many red balls are in the urn, could help us determine
the probability of differenti outcomes, but has no influence on the
possible outcomes. Indeed, even if there were 1 blue and 1,000 red
balls in the urn, "all balls drawn are blue" is still a possible
outcome!
Now let's turn to the question of what an outcome is.
♦ If we don't care about the order in which the balls are drawn,
then an outcome consists in the number $n_b$ of blue and $n_r$ of red
balls drawn. It is enough to know one of these two numbers only since
they add up to $n\: (=n_r+n_b)$, the total of balls drawn. The
number of blue balls can be any of $0,1,2,\dots,n$ for a total of
$n+1$ possibilities (notice that we count from 0!). This is
reconciled with the formula for unordered sampling with replacement
by observing that we take $n$ samples from a population of $m=2$
types of balls (blue or red), which yields ${m+n-1\choose
n}={n+1\choose n}=n+1$ possibilities.
♦ If, on the other hand, we care about order, then outcomes are
described as sequences $(c_1,c_2,\dots,c_n)$ of length $n$
($n$-tuples), where $c_j$ indicates the color (blue or red) of the
$j$th ball for $j=1,2,\dots,n$. This yields a total of $2^n$
possible outcomes, since each ball in the sequence is of two possible
colors. Again, since we have a population of $2$ different color
balls, we see that the result is consistent with the formula $m^n$ for
ordered sampling with replacement when $m=2$.
Give a combinatorial proof of the indentity $$ \binom{m+1}{n}=\binom{m}{n}+\binom{m}{n-1} $$
If you sample $n$ objects of $m$ different types with replacement, how many outcomes can you observe in total disregarding the order of the objects?
This was the most commonly asked question concerning Lecture 1 and
coincides with Task 3 on Worksheet 1. We will obtain an answer in
stages.
1. First we observe that the goal is to account for all possible
outcomes and it is therefore irrelevant what the probabilities of the
individual outcomes may be. In particular, there is no need to know how many
objects there are of each type.
As long as there is a steady supply of objects of each type, any of
the types can occur each time we sample one. This is indeed the
case because we replace the objects after each sample is taken. Given
that we are not interested in
the order of the objects, an outcome is fully determined by the number $n_i$ of
objects of each type $i$ where $i=1,2,\dots,m$. In more mathematical
terms, each outcome corresponds to a $m$-tuple
$$
(n_1,n_2,\dots, n_m)
$$
of integers satisfying
$$
0\leq n_i\leq n\text{ for } i=1,\dots, m\text{ and }n_1+n_2+\dots+n_m=n.
$$
The inequality conditions simply say there are none or some (up to at
most $n$) objects of each type, the sum condition that we take a
sample of size $n$. Thus the set
$$
S^n_0=\big\{ (n_1,n_2,\dots, n_m)\, \big |\, 0\leq n_i\leq n,\:
n_1+\dots+n_m=n\big\}
$$
contains all outcomes and we are asked to determine the number
$\#S^n_0$ of its elements.
2. Assume first that $1\leq n_i\leq n$ for $i=1,\dots,m$, that is
consider
$$
S^n_1=\big\{ (n_1,n_2,\dots, n_m)\, \big |\, 1\leq n_i\leq n,\:
n_1+\dots+n_m=n\big\}
$$
This means that we only consider outcomes for which there
is at least one object of each type (clearly $n\geq m$ in this case).
More visually
$$
\underset{n_1}{\underbrace{o_1\, o_1\dots o_1}}\,\big |\,
\underset{n_2}{\underbrace{o_2\, o_2\dots o_2}}\, \big |\,\cdots\,
\big |\,\underset{n_m}{\underbrace{o_m\, o_m\dots o_m}}
$$
where $o_i$ means object of type $i$. In the whole sample there are
clearly a total of $n$ objects and the $m-1$ dividers are placed
anywhere in between the objects to indicate that objects of one type
have ended and objects of the next type are up. Since there is at
least one object of each type, no divider can be placed in front of
all objects, nor after the last one. This would indeed indicate that objects of
the first or of the last type are absent, respectively. For the same reason dividers
cannot be placed next to each other. This shows that the total number
of possible outcomes (elements of $S^n_1$) is the same as the number of ways in which you
can place $m-1$ dividers at $n-1$ possible locations (the $n-1$ spaces
in between the $n$ objects). This yields that
$$
\# S^n_1={n-1\choose m-1}=\frac{(n-1)!}{(n-m)!(m-1)!}
$$
3. Next we deal with the actual problem. Instead of proceeding in a
similar way, we reduce it to the previous case. The reason for opting
not to follow the same reasoning is that dividers can follow one
another if we allow for outcomes for which some types of objects do
not occur, making it much harder to find all possible ways in which
the dividers can be placed. A clever idea, however, comes to the
rescue. Consider the set $S^n_0$ and add $(1,1,\dots,1)$ to each
of its elements to obtain $S^{n+m}_1$. This operation can obviously be
undone by simply subtracting $(1,1,\dots,1)$ from any element of
$S^{n+m}_1$. It follows that
$$
\# S^n_0=\# S^{n+m}_1={n+m-1\choose m-1},
$$
where the last equality follows from step 2. It remains to observe
that
$$
{n+m-1\choose m-1}={n+m-1\choose n},
$$
to obtain another equivalent representation. You can try to find a
reason for the validity of this last identity but it was also discussed
in Video Lecture 1.
What is the difference between a set and a sequence?
A sequence consists of ordered elements. A vector $(x_1,x_2,\dots,
x_n)\in\mathbb{R}^n$ is, for instance, a finite sequence with a well-defined
first element, second element, ...
On the other hand a set is simply a collection of elements and order
does not play any role.
As an example take the set of all participants in a race as opposed to the
sequence determined by the final ranking in the race. If you are sending
an email to the participants, you only about care the set of names. If,
on the other hand, you are giving out prizes, then order really
matters. This is to say that in concrete situations the context will
determine whether one needs to work with a set or a sequence.
For another example take the sequence $(1,2,5,7,5)$ and the set of its
elements $\{1,2,5,7\}$, which clearly shows that sequences can even
have repeating elements, but sets obviously don't since they only
require their elements to be listed once!
Explain the validity of the formula $$ (x_1+x_2+\dots+x_m)^n=\sum _{n_1+n_2+\dots+n_m=n}{n \choose n_1,\dots,n_m}x_1^{n_1}x_2^{n_2}\cdots x_m^{n_m} $$ where $m,n\in\mathbb{N}$ and $x_1,\dots,x_m\in\mathbb{R}$
On the left we have the $n$-fold product $$ \underset{1}{\underbrace{(x_1+x_2+\dots+x_m)}}\, \underset{2}{\underbrace{(x_1+x_2+\dots+x_m)}}\, \cdots\, \underset{n}{\underbrace{(x_1+x_2+\dots+x_m)}} $$ Using distributivity, we can develop this product to obtain the sum all possible products obtained by choosing one of $x_i$, $i=1,\dots,m$, from each of the factors. Let $n_1$ be the number of times we choose $x_1$, $n_2$ the number of times we choose $x_2$, ..., $n_m$ the number of times $x_m$ is chosen. Because of commutativity of multiplication their product will yield $$ x_1^{n_1}\, x_2^{n_2}\cdots x_m^{n_m} $$ Clearly we need to have that $$ n_1+n_2+\dots+n_m=1\text{ and }0\leq n_i\text{ for }i=1,\dots,m, $$ since we have a total of $n$ factors and the $x_i$'s can only appear a non-negative integer number of times. The next question is how many times one can obtain the term $ x_1^{n_1}\, x_2^{n_2}\cdots x_m^{n_m}$. When choosing the $n_1$ factors from which to pull $x_1$ we have ${n\choose n_1}$ choices. For each of these choices we have $n-n_1$ remaining factors from which to choose $x_2$ $n_2$ times or ${n-n_1\choose n_2}$ possibilities. This yields a total $$ {n\choose n_1}{n-n_1\choose n_2} $$ ways to pick $x_1$ $n_1$ times and $x_2$ $n_2$ times. Continuing in this way we see that there are a total of $$ {n\choose n_1}{n-n_1\choose n_2}\cdots{n-n_1-n_2-\dots-n_{m-1}\choose m_n}={n\choose n_1}{n-n_1\choose n_2}\cdots{n_m\choose n_m}={n\choose n_1,n_2,\dots,n_m} $$ ways to obtain $x_1^{n_1}\, x_2^{n_2}\cdots x_m^{n_m}$.
Let $n\leq n\in\mathbb{N}$ and show that $$ {m+1\choose n}={m\choose n}+{m\choose n-1}. $$
This identity can be verified by simply writing out the definition of
each term and carrying out the computations. There is, however, a more
conceptual way to understand it.
Take the $m+1$ objects we are choosing from and place $m$ of them
together and separate the remaining one. Now we can choose $n$ objects
from the pile of $m$ to get all ${m\choose n}$ possibilities that do
not include the one object that we separated. The possibilities that
are left over at this point will all contain the separated object and,
thus, to get to $n$, we only need to choose $n-1$ objects from the "pile"
of $m$, which gives ${m\choose n-1}$ possibilities and, eventually the
sum on the right-hand-side of the identity. Of course this gives all
possible ${m+1\choose n}$ ways to choose $n$ objects from $m+1$.
What is the probability to have a straght in a five card hand? A straight occurs when the 5 cards are of consecutive values but not all of the same suit (in that case the hand would be called a straight flush).
Notice that if a hand consists of 5 consecutive cards, it can be uniquely described by the card of lowest value (we could equally well take the highest value). As we need 4 cards to follow the lowest, the latter can be at most a 10. We therefore have 10 possible choices for the value of the lowest card. Once that is determined we still can choose the suit of the five cards. This would give a total of $4^5$ possibilities but we need to exclude the 4 possible straight flushes, one of each suit, and thus the count is actually $4^5-4$. This yields a total of $10*(4^5-4)$ and a probability of $$ P(``\text{a randomly chosen hand is a straight"})=\frac{10(4^5-4)}{{52\choose 5}}=0.0039 $$
Show the validity of the identity $$ n\binom{n}{i}=i\binom{n-1}{i-1} $$ for $1\leq i\leq n$ and $n\in\mathbb{N}$