password combinations

[Ilias]

Hello, I am reading some notes and there is this statement that says:
"The possible passwords , with length k, if you use only CAPITAL letters and at LEAST one number is36^k - 26^k ".
I understand this, but before reading the solution i had found one of my own.

k * 10 * 36^(k-1)
that is because, if the number is in the first spot, you have 10 digits to chose for the first and 36 for the rest of the positions
10 *36(k-1)
if the number is in the second place 36*10*36(k-2) etc.

the number can be in all k spots so k * 10 * 36^(k-1).
This does not produce the same result, but i don't understand why.

 

[Dr.Peterson]

Hello, I am reading some notes and there is this statement that says:
"The possible passwords , with length k, if you use only CAPITAL letters and at LEAST one number is36^k - 26^k ".
I understand this, but before reading the solution i had found one of my own.

k * 10 * 36^(k-1)
that is because, if the number is in the first spot, you have 10 digits to chose for the first and 36 for the rest of the positions
10 *36(k-1)
if the number is in the second place 36*10*36(k-2) etc.

the number can be in all k spots so k * 10 * 36^(k-1).
This does not produce the same result, but i don't understand why.

You are counting the number of possible passwords consisting of k symbols, each of which can be either a capital letter or a digit, with the requirement that there must be at least one digit.

You understand that one way to get the answer is to count the total number of ways to arrange k symbols, each a letter or a digit (36^k), and subtract from that the ways that consist only of letters (26^k).

So the numerical answer for k=5 is is 36^5 - 26^5 = 48,584,800

Your attempt gives 5*10*36^4 = 83,980,800, which is an overcount. Why?

The trouble is the word "the": "if the number is in the first spot". This is inappropriate when there are in fact more than one digit!

You talk about "the" digit being in a given spot, and then filling in other spots with either a letter or a digit. But you could get the same password if "the" digit were in another place. For example, you could get 1ABC2 by putting "the" 1 in the first place, or by putting "the" 2 in the last place. Your count includes both, so you have overcounted. This is a very common mistake.

 

[lex]

You are saying "the number is in the first spot" and then you have numbers in any of the other spots. You are counting the same patterns many times.
If you modify your argument to: "if the FIRST number is in the first spot..."

then your calculation is [MATH]\hspace2ex 10\cdot 36^{k-1} + 26 \cdot 10 \cdot 36^{k-2} + 26^2 \cdot 10 \cdot 36^{k-3}+ + 26^{k-1} \cdot 10[/MATH]
which is [MATH]\hspace2ex 10 \cdot 36^{k-1} \left[1+ \left(\tfrac{26}{36} \right) + \left(\tfrac{26}{36} \right) ^2 + \left(\tfrac{26}{36} \right) ^3 +....+ \left(\tfrac{26}{36} \right) ^{k-1} \right][/MATH][MATH]=10 \cdot 36^{k-1} \cdot \tfrac{\left[1- \left(\tfrac{26}{36} \right) ^k \right]} {\left(1- \tfrac{26}{36} \right)}\\ =36^k \cdot \left[1- \left(\tfrac{26}{36} \right) ^k \right]\\ =36^k-26^k[/MATH]