I am trying to figure out the maximum possible combinations of a (HEX) string, with the following rules:

  • All characters in uppercase hex (ABCDEF0123456789)
  • The output string must be exactly 10 characters long
  • The string must contain at least 1 letter
  • The string must contain at least 1 number
  • A number or letter can not be represented more than 2 times

I am thinking the easy way to go here (I am most likely wrong, so feel free to correct me):

  1. Total possible combinations: $16^{10} = 1,099,511,627,776$
  2. Minus all combinations with just numbers: $10^{10} = 10,000,000,000$
  3. Minus all combinations with just letters: $6^{10} = 60,466,176$
  4. etc...

Can someone could tell me if this is the right way to go and if so, how to get the total amount of possible combinations where a letter or a number occur more than twice.

Any input or help would be highly appreciated!

Muchos thanks!


I don't know if I tagged this question right, sorry :(


| cite | improve this question | | | | |
  • $\begingroup$ I changed it to combinatorics, which is all about counting things. The thing is, you use combinatorics often in probability, so your choosing of probability wasn't a bad tag. I just thought combinatorics was more accurate. This problem could be done in relation to some probability, or without any relation to probability. $\endgroup$ – GeoffDS Feb 27 '12 at 21:39
  • $\begingroup$ It's not clear if you are counting different combinations (order does not matter) or numbers of strings (order matter) $\endgroup$ – leonbloy May 1 '12 at 1:14

I think the sanest way to split this is by how many different letters and numbers is contained in the string. Call the total number of different symbols $k$. The possibilities are then:

k=5    1+4  2+3  3+2  4+1
k=6    1+5  2+4  3+3  4+2  5+1
k=7    1+6  2+5  3+4  4+3  5+2  6+1
k=8    1+7  2+6  3+5  4+4  5+3  6+2
k=9    1+8  2+7  3+6  4+5  5+4  6+3
k=10   1+9  2+8  3+7  4+6  5+5  6+4

For each of the 33 entries in the table, the number of ways to select which hex digit appear at all is a simple product of binomial coefficients.

From there each row of the table can be summed and treated uniformly. First select which $10-k$ of the $k$ symbols are going to appear twice, for a factor of $\binom{k}{10-k}$. Then multiply by $10!$ for the ways to arrange the symbols you have selected, and divide by $2^{10-k}$ to account for the fact that each pair of two equal symbols cannot be distinguished.

| cite | improve this answer | | | | |
  • $\begingroup$ Thanks Henning, I appreciate your effort to help me! However, this answer is waaaay over my head. I didn't even know what word or symbol to google first :( $\endgroup$ – José Feb 27 '12 at 21:52

Four years and no answer? To continue with your original reasoning...

  1. Total amount of numbers: $10^{10}$ or 10,000,000,000
  2. Total amount of letters: $6^{10}$ or $60,466,176$
  3. Subtract the above two numbers $10^{10}$ and $6^{10}$ from...(drum roll please)...Your last criteria! ("A number or letter cannot be represented more than $2$ times").

So your final answer is: $264,683,239,424$.

I'm sure you're wondering what the probability of your last criteria is. It would be: ($16^2)*(15^2)*(14^2)*(13^2)*(12^2)$.

That is, every two numbers I reduce by one, because for every two spaces, one number cannot repeat. Thanks.

| cite | improve this answer | | | | |

I had a similar question. Basically I think I figured out how to do this.

First of all, if you are dealing with only numbers and you have a base 10 number system, it's pretty easy to figure out the number of combinations. If you have a 3 digit code and only use numbers, you have 999 possible combinations, right? Well, 10^3 gets you there. And I'm using 10, because there are 10 possible combinations of each digit (i.e. 0,1,2,3,4,5,6,7,8,9). Now if you add the hex letters a,b,c,d,e,f then now there are 16 possible combinations for each digit (the 10 numbers + 6 letters). So I think it stands to reason that you take the number of possible combinations for a digit, 16, and raise it by the number of digits in your code. So 16^8 for an 8 digit code, 16^10 for a 10 digit code, 16^16 for a 16 digit code, etc.

I think my thought process is sound, but I am not a mathematician. Maybe someone can verify that this is correct. Of course this assumes perfectly random codes, not within your restrictions of must contain 1 letter, must contain 1 number, can't use any letter or number or letter more than twice. That should significantly reduce the number of possible combinations.
I think though to eliminate number-only codes (the ones that don't have letters) you would just subtract the total number of possibilities, obviously 9,999,999,999. Then subtract the number of letter only codes, which I believe is 6^10. For no letter or number used more than twice, you would have to find how many possible codes fit that condition, and subtract those as well.

| cite | improve this answer | | | | |

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