Given n ranging from $1$ to $100$, find sum of digits equal to half of arithmetic sum of $1$ to $100$
I have a number sequence from $1$ to $100$. Given $2$ bins, the numbers are randomly assigned to each bin.
I know the total sum from $1$ to $100$ is $5050$. Thus, for both bins to have the same sum, each bin must sum up to $2525$. All the $100$ numbers must belong to either bin.
I know there are a total of $2^{100}$ possible combinations. How do I find the number of combinations that sum to $2525$ in each bin?
Thank you.
EDIT: Just to clarify, a bin is just a collection of numbers. So essentially, I have collection $A$ and collection $B$. The sum in each collection must be equal and all $100$ numbers must belong to either collection. Think of them as buckets or whatever is convenient for explanation.
Using the recursion (thanks Bilou06)
$$f(n, S) = f(n - 1, S) + f(n - 1, S - n),$$
we have the following Python code:
n = 100
S = 2525
matrix = [[0]*(S+1) for x in range(0, n+1)]
for S in range(0, S+1):
matrix[0][S] = 0
for n in range(0, n+1):
matrix[n][0] = 1
for n in range(1, n+1):
for S in range(S+1):
matrix[n][S] = matrix[n-1][S] + matrix[n-1][S-n]
print matrix[n][S]
You can change the values of n
and S
when running the code to verify they work for smaller cases.