[Math] How many possible combinations of a HEX string

combinatorics

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!

PS.

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

DS.

Best Answer

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.

Related Question