Counting Rule for distinct tuples, elements of tuples unique kinds, order doesn't matter?

Question

My question: Can you help me understand counting rules? I do not understand the application of different counting rules for use in probability. I have a problem that I THINK I solved by counting by hand, but I want to use the formulas given by my teacher, listed at the bottom of my question. I especially don't understand formulas 4.) and 5.) but I think I need to use one of them.

An example: A secretary types three letters and the three corresponding envelopes. In a hurry, he places at random one letter in each envelope. What is the probability that at least one letter is in the correct envelope?

So, am I thinking permutations here? Combinations? One of the other three rules or some combination? What's the difference between "distinct", "unique"? How do these words apply to this context? How does the term "order" apply to this context. There are seem to be elements of two "kinds" here, and maybe "partitions"? Does order matter? I am having a very hard time understanding what these how these vocabulary words apply to this seemingly simple problem.

My work: I count 9 possible ordered pairs (2-tuples?). I think that order does not matter, i.e. (letter,envelope) = (envelope,letter). I also note that each element of the ordered pair must be of a unique kind. I remember that the probability of at least one correct ordered pair is $P(C)=1-(C_N)$, where $C_N$ is the event that no correct combinations occur.

Now I count 6 combinations that are incorrect, out of 9 total. So again, just counting I think that the probability of the event at least one correct combo is $P(C)= 1 -{6 \choose 3}/{9 \choose 3}$, but this does not yield an answer that matches what I find online.

The formulas: I have been given 5 counting rules to assist me in my probability theory homework, 3 of which have titles, and then two more for which the teacher did not have a title or name, only an equation and a confusing (for me) description of use. I am consistently at a loss to match the type of problem to the correct formula(s). I cannot find the last two rules in my textbook or by googling.

1.) Permutations

2.) Combinations

3.) Multiplication rule

4.) Let $r_1,r_2,\dots,r_k \in \mathbb{Z}^+: \sum_{i=1}^{k}r_i=n$, then the number of ways n elements can be partitioned into k groups in which group $i$ contains $r_i$ is:

$$n!/(r_1!r_2!\dots r_k!)$$

5.) The number of distinct permutations of length k from a set of n objects where each object in the permutation is unique in kind is: $$n!/(n_1!n_2!\dots n_k!)$$

Answer 1

A secretary types three letters and the three corresponding envelopes. In a hurry, he places one letter at random in each envelope. What is the probability that at least one letter is in the correct envelope?

Line up the envelopes in some order, say alphabetically by addressee. There are $3!$ ways to place one letter in each envelope since there are three ways to place a letter in the first envelope, two ways to place one of the remaining letters in the second envelope, and one way to place the last letter in the third envelope. They are

$(A, a), (B, b), (C,c)$

$(A,a), (B,c), (C,b)$

$\color{red}{(A,b), (B,a), (C,c)}$

$(A,b), (B,c), (C,a)$

$\color{red}{(A,c), (B,a), (C,b)}$

$(A,c), (B,a), (C,c)$

Those arrangements shown in red do not satisfy the requirement that at least one letter is in the correct envelope. The other four do. Hence, the desired probability is $$\frac{4}{3!} = \frac{4}{6} = \frac{2}{3}$$

I count $9$ possible ordered pairs ($2$-tuples?).

We are not interested in ordered pairs here since placing a letter in envelope $A$ eliminates the possibility that a second letter can be placed in envelope $A$. It also eliminates the possibility that letter can be placed in a different envelope. For instance, if we place letter $b$ in envelope $A$, the ordered pairs shown in red are eliminated before we place the next letter in envelope $B$. $$\color{red}{(A, a), (A, b), (A,c),} (B, a), \color{red}{(B, b)}, (B,c), (C,a), \color{red}{(C,b)}, (C,c)$$ What we are doing is matching letters with envelopes. Once we line up the envelopes, we have three choices for which of the letters will be placed in the first envelope, two choices for which of the remaining letters will be placed in the second envelope, and one choice for placing the remaining letter in the remaining envelope. Clearly, the order matters here, so there are $3! = 6$ possible matchings.

Now I count $6$ combinations that are incorrect out of $9$ total.

You are counting individual envelopes, rather than the six possible matchings listed in my answer.

Moreover, combinations are used to count subsets. The number $$\binom{n}{k} = \frac{n!}{k!(n - k)!}$$ is the number of subsets (or unordered selections) of size $k$ that can be selected from a set with $n$ elements. We are not counting subsets here.

Answer 2

Putting $n$ labeled letters into $n$ labeled envelopes certainly ranges under permutations, or bijective maps $f: \>[n]\to[n]$. It is a basic fact of combinatorics that there are $n!$ such maps. In the problem at hand we have to count the number of permutations which satisfy a certain extra condition. When $n$ is small, $3$ in your example, the simplest way is to list all $6$ permutations and check by hand which of them fulfill the constraint. If $n\gg1$ this is unfeasible, and we need a general theory dealing with this constraint. Your teacher did not assume that you have met this theory before; it is treated in connection with the inclusion/exclusion principle.