# Sum of 16 unsigned integers, possible combinations.

I have two arrays with 16 unsigned integers. I compute the sum of the first array = x and the sum of the second array = y. What is the chance they will be the same? Also, how many combinations out of the total combinations are the same?

An example: Lets say an array1 contains these numbers (low values just for clarification): 3,4,2,5,3,6,7,5,3,7,8,2,9,1,4,3

Then I compute the sum of those values: 72

Then I have another array2 with these numbers: 4,2,5,7,9,5,3,2,4,7,5,4,8,3,2,4

Then I compute the sum of those values: 74

A third array3 like this: 4,8,8,5,5,9,1,4,6,3,3,2,8,1,2,3

Then I compute the sum of those values: 72

array1 and array3 have the same value even though the numbers are different.

My question is how many times can the same number appear with different content for a given array of unsigned integers?

Some calculations I did on my own. There are 65536 different possible numbers for an unsigned integer. There are 16 unsigned integers in the array. 65536 * 16 = 1048576. This is the maximum number I can have when I sum up all the numbers in the array. That is about as far as I can go.

I hope I explained it well enough. If not then just let me know and I will try my best to clarify.

Thanks for any input.

• If you were willing to consider the sums as "equal" mod 65536 (i.e., you compute the sum as an unsigned int), then the problem becomes somewhat easier. Are you sure that this is not what you want? Also, suppose we're talking about just 3 numbers instead of 16. Would you like to count (1, 1, 4) as "different content" from (1, 4, 1)? Commented Feb 5, 2015 at 20:28
• Welcome to our site! Commented Feb 5, 2015 at 20:43
• John Hughes, Not sure I understand your first point, the "equal" mod 65536. (1,1,4) and (1,4,1) would yield the same sum. Both with a value of 6. No, they are not different content. I am only interested in the sum of the numbers. (1,1,4) for one array and (1,4,1) is a possible situation in my "application" and both would compute to 6 telling my "application" that it has reached a breaking point. Maybe I should tell what my "application" is, maybe it would help. What do you think? kjetil b halvorsen, thanks :) Commented Feb 5, 2015 at 21:41
• On a side note, how come I can't make paragraphs in comments? Commented Feb 5, 2015 at 21:47
• @Sigmundur: Comments support a limited set of markdown, and remove what is considered excess space. Click on help next to comment box for details. Commented Feb 5, 2015 at 23:47

I'm assuming the numbers in the array are uniformly distributed, that is, an array is equivalent to a sequence of 16 draws on the discrete uniform distribution over $[0,65535]$.

In that case, the number of ways that some number $N$ can be made by an array is just the number of restricted weak compositions. With your parameters, this can be had via the generating function:

$\frac{\left(1-z^{65536}\right)^{16}}{(1-z)^{16}}$

The coefficient of $z$ at $N$ will give you the number of ways $N$ can be formed, and dividing that by the total number of possible arrays ($65536^{16}$) will give you the probability that some random array will sum to the given $N$ (under the stated assumptions).

Summing the squares of all the probabilities from 0 to 1,048,560 will give you the probability of two randomly generated arrays having the same sum. (N.b. it's 1048560, not the 1048576 you have: the unsigned 16-bit numbers range from 0 to 65535).

I seem to recall a few authors deriving a closed-form for the number of restricted weak compositions, I'll try and search my archive of papers if/when I have time (or try Google).

Addendum: You can also derive the probabilities directly for a given sum $N$ via standard methods for sums of discrete uniform RV (convolution, closed-form formulae, etc.) and then use those to get to the same result.

Update per OP request with small example:

For a 4-vector case with elements 0-9, the generating function is $\frac{\left(1-z^{10}\right)^4}{(1-z)^4}$. Expanding this out to 36 (4*9) gets us:

$1+4 z+10 z^2+20 z^3+35 z^4+56 z^5+ ... +35 z^{32}+20 z^{33}+10 z^{34}+4 z^{35}+z^{36}$

The coefficients give us the number of ways a sum equal to the corresponding exponent can be formed, e.g., 1 way to form 0, 10 ways to form 2, and so on.

Taking the coefficients and dividing by the total combination possible (10^4) gies you the probability of each sum for a random 4-vector.

This is equivalent to a 3-fold (4 elements - 1) convolution of a list of length 10 of elements all 1/10 - both result in the list of probabilities of a random vector summing to some value 0 to 36.

Lastly, for your 4-vector example, squaring that result and summing gets us $\frac{481603}{10000000}$, the probability that two random 4-vectors have the same sum.

• Could you make a small but concrete example using, for example, arrays that hold only 4 values and the values range from 0-9? Commented Feb 10, 2015 at 11:42
• @Sigmundur: Added requested trivial example. Commented Feb 10, 2015 at 22:38

To get the total number of combinations that give the same sum, you want to solve the problem of how many different ways you can assign 16 non-negative integers that give a specified sum, possibly with some restrictions. This is a famous basic combinatorics problem. If your target sum is $X < 2^{16}$, then the number of ways is ${{X + 15} \choose 15} = (X+15)!/(X! * 15!)$. If your target sum is greater than $2^{16}$ then the problem is trickier because you aren't allowed to have any one number be greater than or equal to $2^{16}$. I'm not sure how to solve that case.

• Alright. But just to clarify, I am not interested in a specific number X. But I still want to know what you mean. So if my target sum is... 100. Then it is 100 + 15 factorial divided by 100 factorial times 15 factorial? I don't know how to do those fancy equation stuff :D Commented Feb 5, 2015 at 21:46