0
$\begingroup$

Assume there are 9 identical balls, and each can be placed in one of 10 numbered slots. All balls must be placed in exactly one slot (i.e., you can't leave a ball out). How many combinations are possible?

To explain a little better, I want to create a "hash" function for Social Security Numbers (SSNs). The hash will end up being a 10-digit number, where each digit is represented by the number of times that digit is found in an SSN. Each of the "balls" in the original question represents a digit from the SSN, while the slots represent a number from 0 (in the low-order position) through 9 (in the high-order position).

For example, an SSN of 123-45-6789 would result in a hash of 1111111110, since the digit "0" (zero) never appears, but each of the remaining digits appears once. Another example: 111-22-3333 would result in a hash of 0000004230, since "3" appears 4 times, "2" appears twice, and "1" appears 3 times.

I'm trying to determine the selectivity of my hash algorithm. Thanks for your help!

$\endgroup$
0
$\begingroup$

If I'm understanding your problem correctly we can reinterpret it as trying to find the number of integer solutions to $x_0 + x_1 + \dots + x_9=9$, where $x_i \ge 0$. Each of the $x_i$ stands for the number of times digit $i$ shows up in the SSN, and the sum of 9 shows that each SSN has 9 digits.

We can use a variant of the stars and bars counting method (http://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)#Theorem_two) to see that we need to calculate the binomial coefficient $\binom{18}{9}$, which gives us the answer of 48620 different solutions.

$\endgroup$
  • $\begingroup$ Yes, that's exactly what I was looking for... Thanks very much! $\endgroup$ – CueBallSTL Mar 4 '14 at 20:00

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.