0
$\begingroup$

Canadian postal codes (for those of you who don't know) are as follows: letter, digit, letter, digit, letter, digit (letters and digits can be repeated) How many possible postal codes are there if the letters must be in alphabetical order? My best guess is that since the 3 letters can only be in alphabetical order 1/3rd of the time(aaa, aab, aac, aad, aae, etc.), you would use an indirect method by firstly find the total combinations without restrictions, which is 17,576,000 possible combos. Therefore, is (1/3)(17,576,000) the correct way to solve? It feels like I'm forgetting something.....

$\endgroup$
  • $\begingroup$ If the letters are distinct, they're only in alphabetical order one-sixth of the time. You should probably break it up into cases: all the letter are distinct, exactly two of them are the same, all three are the same. $\endgroup$ – saulspatz Mar 31 '18 at 20:09
  • $\begingroup$ You are using a simplified model for Canadian postal codes. However, using the actual model would make the problem much more difficult. $\endgroup$ – N. F. Taussig Apr 2 '18 at 23:55
  • $\begingroup$ @N.F.Taussig Do you mean the province restrictions? Certain provinces have certain letters? $\endgroup$ – Noah Woodworth Apr 3 '18 at 0:00
  • $\begingroup$ No. Postal codes do not include the letters D, F, I, O, Q, or U. That does not affect the difficulty of the problem. However, the first letter cannot be a W or Z. Taking that into account would make the problem much more difficult. See the section on the number of possible postal codes. $\endgroup$ – N. F. Taussig Apr 3 '18 at 0:03
1
$\begingroup$

No, that's not right. Say you only had $2$ letters $a$ and $b$. Then you have $8$ possible 3-letter strings, but of those, $aaa$, $aab$, $abb$, and $bbb$ are valid. So, it is not $\frac{1}{3}$ of all possible strings.

In fact, if all three letters are different, then it is in alphabetical order $\frac{1}{6}$ of the time, since they can be in $3!=6$ possible orders. But since you can have repeat letters, it is not $\frac{1}{6}$ of all possible strings either.

Still, start with that: out of all $3$ letter strings with $3$ different letters (of which there are $26 \cdot 25 \cdot 24$), $\frac{1}{6}$ are valid. As N.F.Taussig correctly points out in the comments, this is the same as the number of ways you can pick three different letters, i.e. $26 \choose 3$, as they can only be put in one alphabetical order.

Now try and figure out all valid $3$ letters strings with $2$ letters being the same, and finally find all with all $3$ letters the same (that last one is easy: $26$)

So, the question is: how many valid strings are there where two letters are the same?

Answer:

There are $26 \choose 2$ pairs of letters, and thus also that many with two of the same letter that are alphabetically before the third letter (and there is only one way to make that into a valid string) and also that many where there are two of the same letter that come alphabetically after the third letter (and again there is only one way to make that into a valid string). Hence, there are $2 \cdot {26 \choose 2}$ valid strings where two letters are the same. This gives a total of $${26 \choose 3} + 2 \cdot {26 \choose 2} + 26$$ $3$-letter strings in alphabetical order, and now you just need to multiple by $1000 to get the total number of possible license plates.

$\endgroup$
  • $\begingroup$ So if I understand correctly, there are (26!/(26-2)!) out of 26^(3) valid strings? which equates to being valid 25/338 of the time? $\endgroup$ – Noah Woodworth Mar 31 '18 at 20:39
  • $\begingroup$ Your answer is incorrect. Since the letters must be in alphabetical order, choosing three different letters completely determines their order. You would divide by $6$ if you were considering permutations of the three letters to account for symmetry. $\endgroup$ – N. F. Taussig Apr 1 '18 at 1:13
  • 1
    $\begingroup$ @N.F.Taussig Oh, right! It's $\frac{1}{6}$ of all possible 3-letter strings of which there are $26*25*24$. Thanks! $\endgroup$ – Bram28 Apr 1 '18 at 3:03
  • $\begingroup$ @N.F.Taussig so this?: (26*26*26) + 2(26*26*25) + (26*25*24) $\endgroup$ – Noah Woodworth Apr 1 '18 at 18:37
  • $\begingroup$ @NoahWoodworth No. You only have $26$ three letter strings where all three letters are the same, so it's just $26$ for that term, rather than $26\cdot26\cdot26$. And for the strings where all three letters are different, it's $\frac{1}{6}$ of all strings with three letters. $26 \cdot 25\cdot24$ is the number of all strings with three different letters, so you get $\frac{26\cdot25\cdot24}{6}$ for that term. For the number of strings with two of the same letters, hover over the yellow box in my answer. $\endgroup$ – Bram28 Apr 1 '18 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.