# Combinations and Permutations (Passwords and Horse Race)

EDIT: Sorry, I was so distracted translating the exercises into English that I didn't notice I hadn't typed what I actually wanted...

I was wondering whether my answers are correct, simply put, and if not then why? Please.

Exercise 1: How many passwords composed of 3 distinct lower case letters followed by 3 numbers can we create?

My Answer: $26\times25\times24 + 10^3 = 16600$

Exercise 2: How many passwords composed of 3 distinct lower case letters and 3 distinct numbers can we create? (the relative positions of the letters and the number don't matter this time)

My Answer: $26\times25\times24\times10\times9\times8 = 11232000$

Exercise 3: Two horse races are organized on a given day. There are 16 horses. During the first race, 10 of those horses will be competing. The other 6 horses will race in the second race.

What are the numbers of possible races for that day?

My Answer: $8008 + 720 = 8728$

• You added $10^3$ rather than multiplying by $10^3$ in your first example. Why? You multiplied in the second exercise. Also, you again added in exercise three. Make sure you understand the difference between when you are supposed to add and when you are supposed to multiply. Further, where did the number $720$ come from for your answer in exercise 3? We don't care about the order in which the horses ended the second race. Nov 12 '17 at 22:15
• I added instead of multiplying because I thought for a moment thats what the followed stood for... Do you have any indication of when to add or multiply, by any chance? It would be greatly appreciated :) Nov 12 '17 at 22:18
• You add when two events cannot occur at the same time. You multiply if two events can occur independently of each other. Nov 12 '17 at 22:19
• in #2, not sure I follow "(relative positions of the letters and numbers dont matter this time)". Unless that's just worded wrong (or I dont understand it), but in a password you have to account for the relative positions. In the first example you dont because they gave you the ordering (letters then numbers) in the second there seems to be no such restriction. a123bc is a diff password than abc123. Number 3, Do you know a way to choose 10 objects from 16? Nov 12 '17 at 22:35

The Rule of Product and the Rule of Sum generalize when you should add and when you should multiply.

In terms of set theory, they say $$|A\times B|=|A|\times |B|$$ and $$|A\sqcup B|=|A|+|B|$$ (where here $$\sqcup$$ mean the disjoint union of $$A$$ and $$B$$, implying that $$A$$ and $$B$$ are disjoint sets sharing no elements in common).

More generally, Inclusion-exclusion states that $$|A\cup B|=|A|+|B|-|A\cap B|$$. The rule of sum is just a special case of the inclusion-exclusion principle for when we have $$A\cap B=\emptyset$$

In terms of counting, the rule of product can be paraphrased to say the following:

If you wish to count how many outcomes there are to a particular scenario and you can describe the outcomes via a sequence of steps such that

• every outcome is counted exactly once
• Each step has a particular number of options available which do not depend on previously made choices in earlier steps

then the total number of outcomes is the product of the number of options at each step.

Note: The number of options at each step cannot change based on earlier choices, however the choices themselves can change.

In terms of counting, the rule of sum can be paraphrased as the following:

If you wish to count how many outcomes there are to a particular scenario and you can describe all outcomes as either outcomes of one case or another such that there is no overlap between the cases, then the total number of outcomes is the sum of the number of outcomes in each case respectively.

Your number you calculated in your attempt for the first: $$26\cdot 25\cdot 24 \color{red}{+}10^3$$ would be the number of elements in the set $$\{abc,abd,abe,abf,\dots,zyx,000,001,002,003,\dots,999\}$$ and is the number of passwords comprised of three distinct lowercase letters only or three digits only. Note $$\{abc,abd,abe,\dots,zyx,000,001,\dots,999\}=\{abc,abd,\dots,zyx\}\sqcup\{000,001,\dots,999\}$$ so the rule of sum applies.

Instead, your question asked you to count the number of passwords formed by three distinct lowercase letters followed by three digits, i.e. you are asked to count $$\{abc000,abc001,abc002,abc003,\dots,zyx998,zyx999\}$$ which can be seen to fall under the rule of product as the following steps:

• Pick the first character
• Pick the second character
• Pick the third character
• Pick the fourth character
• $$\vdots$$

In your second question, we are not only finding passwords of the form $$abc000$$, we are also finding passwords of the form $$ab0c00,000abc,\dots$$. Approach similarly, however include in the beginning an additional step:

• Pick which three of the six spaces are occupied by numerals rather than letters
• Pick the furthest left letter
• Pick the second letter to the left
• Pick the third letter
• Pick the furthest left numeral
• Pick the second numeral
• Pick the third numeral.

Your answer for the second was almost correct but neglected to take the first step that I wrote into account. It does afterall say "the relative positions of the letters and the number don't matter this time" which to me means that letters and numbers can appear in any order but we still consider the password $$abc000$$ to be a different password than $$a000bc$$.

If $$abc000$$ is considered to be the "same" password as $$a000bc$$ in your interpretation of the quoted phrase, then break into two steps: Pick which three letters appear. Pick which three numerals appear. The first step can be counted straightforwardly using binomial coefficients. The second step will then require stars-and-bars.

For the third question, my interpretation is that we only care which ten horses are in the first race and the remaining six will be in the second race. We don't care about the rankings for the races, only who was in which, so there is no need to have $$720$$ added or multiplied to the number $$\binom{16}{10}=8008$$.

• Thank you a lot! I see it quite better now, especially with the Product and Sum rules. I am just not yet quite sure what the answer to my second question would be then? Nov 13 '17 at 6:37
• @Disjoint assuming my interpretation to the question is the correct one (where a different order means a different password, such as $a00b0c$ being a "different password" than $000abc$), you have $\binom{6}{3}$ ways to pick which three of the six spaces are occupied by numerals rather than letters. You then have $26$ options for the leftmost letter, $25$ options for the next letter, and $24$ options for the final letter, $10$ options for the leftmost numeral, $9$ options for the next numeral and $8$ options for the last numeral, so applying rule of product... Nov 13 '17 at 15:36