Permutations and Combinations:

1. Consider a particular 10 digit number with no identical digits. How many new ten digit numbers can you make by rearranging (permuting) the digits of this number?
   
   

2. How many distinct "strings" can be formed by rearranging the letters in the word "statistics"?
   
   

3. A "heptadecagon" is a polygon with 17 sides. How many diagonals does it have?
   

4. If you flip a coin 20 times in a row what is the number of possible outcomes with exactly 12 heads in total?
   
   

5. There are ten students in a lab class (call them A, B, ..., J). The students all pair up randomly for a lab. How many distinct possibilities are there for the resulting set of pairings?
   
   

   (Note the similarity of this question to the general problem of partitioning a set into a collection of subsets of specified sizes. In this case a set of size 10 is being partitioned into a collection of 5 sets of size two each.)
   
   

6. Suppose the students in a class of 50 are divided into two groups of 20 and 30 students each. How many different such partitions are there?
   
   

Probabilities:

1. If you choose three cards from a deck, what is the probability that they're all of the same suit?
   
   

2. There are 100 red and 200 green apples in a sack. If you randomly pick out 3 apples , what is the probability that 2 are red and 1 green?
   
   

3. An 8 digit password must have at least one letter and one number (each digit is either a number or a lower case letter). What is the probability that a random guess will yield the correct password?
   
   

4.  There are ten students in a lab class (call them A, B, ... J). The students all pair up randomly for a lab. What is the probability that A is paired with B?
   
   

5. Suppose you have an "unfair coin", which has a probability of 0.6 of coming up heads. If you toss it 20 times, what is the probability that it comes up heads 12 times?
   
   

6. Suppose a class of 100 students is randomly divided into two groups of 50 each. What is the probability that two students, call them A and B, will be in the same group?

Permutations and Combinations:

1. There are 9 choices for the first place digit (a 10 digit number cannot have zero as its first digit), 9 for the second, 8 for the third and so on. This gives \(9 \times 9!\) new 10 digit numbers.
   
   
2. \( \frac{10!}{3! \times 3! \times 2!} \) distinct strings can be formed. \(10!\) is the number of distinct arrangements of 10 distinct elements. The denominator accounts for the fact that swapping identical letters amongst themselves does not lead to distinct words.
   
   
3. A heptadecagon has \(\frac{17\times 16}{2} ~-~ 17\) diagonals. There are \(\frac{17\times 16}{2}\) distinct (unordered) pairs of vertices. Each pair corresponds to either a side or a diagonal. Subtracting the number of sides yields the number of diagonals.
   
   
4. The question reduces to the number of ways of choosing the twelve spots (out of 20) where the heads appear. So there are \(C^{20}_{12} ~=~\frac{20!}{12!8!}\) such outcomes.
   
   
5. Imagine generating different complete pairings of students as follows: Start with the arrangement: |AB|CD|EF|GH|IJ| and then generate different pairings by reordering (permuting) the 10 students: for each permutation, the slots pick out a complete paring.

   However, permutations with the elements within a slot interchanged (BA vs AB) give the same pairing. So we divide by \(2^5\). Furthermore, the 5 slots themselves can by permuted without changing the “set of pairs”. So we additionally divide by \(5!\). This gives a total of \(\frac{10!}{2^5 \times 5!}\) sets of pairs.
   
   

6. Generate all possible partitions as follows: Start with a particular arrangement of students and partition it: \(|\cdots \textrm{30 students} \cdots | \cdots \textrm{remaining 20 students} \cdots |\). Then permute (reorder) the students in all possible \(50!\) ways. Permutations which only shuffle around students within a partition do not generate distinct groupings – for a given partitioned arrangement there are \(30! \times 20!\) such permutations. Thus, the total of distinct partitions is \(\frac{50!}{30! \times 20!}\).
   
   

Probabilities:

1. There are 52 cards in total with 13 in a suit. Given a first card, the number of outcomes where the second and third cards are of the same suit as the first is \(12 \times 11\). The total number of possible outcomes of picking three cards is: \(52\times 51 \times 50\). Thus the probability in question is \(\frac{52\times12\times11}{52\times51\times50} = \frac{12\times 11}{51\times50}\).
   
   
2. Treating each apple as distinct, there are \(300\times299\times298\) possible outcomes of  picking three apples. Out of these, \(100\times99\times200\), have red apples as the first two picks, and an equal number have red apples as the first and third, and second and third picks respectively. Thus the probability in question is \(\frac{3 \times 100\times 99 \times 200}{300\times 299 \times 298}\).
   
   
3. There are \(36^8\) possible strings given no restrictions with \(10^8\) and \(26^8\) possibilities with no letter and no number respectively. Thus the probability in question is, \(\frac{1}{36^8 ~-~ (10^8 ~+~ 26^8)} ~\sim~ 4 \times 10^{-13} \).
   
   
4. A particular outcome is a set of pairings. Divide up the collection of all possible such sets as follows: All sets with the pair (AB), all sets with (AC), …, all sets with (AJ). Each of these sub-collections will contain an equal number of sets and together they account for all possible sets of pairs. Thus the probability that A is paired with B is \(\frac{1}{10}\).
   
   
5. Each toss is an independent event. Suppose the first 12 tosses come up heads, the probability of that is \((0.6)^12 \times (0.4)^8\). The factor of \(0.4^8\) is there because remaining tosses must come up tails for there to be 12 heads in total. However, the question is not concerned with the positions of the 12 heads amongst the sequence of tosses, just that there are 12 in total. There are \(C^{20}_{12}\) possible occurrences 12 heads in a sequence of 20 tosses. Since each of these is a desired outcome, the probability in question is \(0.6^{12} \times 0.4^{8} \times C^{20}_{12} ~\sim~ 0.18\).
   
   
6. Consider a particular partitioned arrangement of students, say: \(|A \cdots B \cdots | \cdots \textrm{remaining 50 students} \cdots|\). Now fix the location of A and generate a total of 99 arrangements from this one by letting B swap places with every other student – 49 of these arrangements will have A and B in the same group while 50 will have A and B in different groups. Next for each of these 99 arrangements permute the remaining elements in all possible ways. Finally change the location of A, again generate 99 arrangements by swapping B around and then for each of these 99 permute the remaining elements around. By repeating this process you can obtain every one of the \(100!\) permutations of 100 students. What this construction makes explicit is that given the integer \(M\) such that \(99 \times M = 100!\), \(49\times M\) of the arrangements have A and B in the same group and \(50 \times M\) have A and B in different groups. Thus the probability of A and B being in the same group is \(\frac{49 \times M}{49 \times M + 50 \times M} = \frac{49}{99}\).

This video from MIT discusses the “basic counting principle” (integral to the analysis of counting problems) and uses it to analyze permutations as well as the number of subsets of a given set.

This video from MIT contains a clear analysis of “combinations”.

This short video from MIT has a nice discussion of “the number of partitions of a set into subsets of given sizes”.