Combinatorics/Permutations [duplicate]

A village has about 1 million residents. Suppose each resident has a jar with 100 coins in it.Two jars are considered to be “equivalent” if they have the same number of 10c, 20c, 50c, \$1 and \$2 coins in them. How many different (i.e. nonequivalent) jars of coins exist? Is it theoretically possible that every person in this village has a different jar of coins?

To my understanding, we know the number of coins in each jar is always 100, so for example if we have five 10c coins in a jar then there are 95 coins of other values in that jar. If we have k1 10c coins in the jar where k1 is between 0 and 100 inclusive, then there are 100-k1 coins of other denominations in the jar. We also have k2 20c coins in the jar where k2 is between 0 and 100 inclusive, so the combined number of 50c, \$1, and \$2 coins in the jar is 100-k1-k2 and so on. And we always have some k1, k2, k3, k4, k5, let's say, so that the sum of those k's is 100. Also, I assume there's no concept of the order of coins in a jar of coins, they're just in there. I got stuck from here, is anyone able to help me out?

migrated from mathematica.stackexchange.comJun 13 at 14:37

This question came from our site for users of Wolfram Mathematica.

• Wrong exchange - you're after Mathematics stack, this is for the software Mathematica. That said, Google "Weak Composition"... – rasher Jun 13 at 8:45
• I wouldn't call a place with about a million residents a 'village'. – Servaes Jun 13 at 14:40

Let $$n=100$$ be the number of coins in each jar and $$k=5$$ the number of distinct coins. The number of possible different jars is $$\binom{n+k-1}{k-1}$$:

n = 100;
k = 5;
Binomial[n + k - 1, k - 1]
(*    4598126    *)


There are more distinct jars possible than there are residents in this city.

You can go the brutal way of enumerating the solutions:

S = Solve[{k1 + k2 + k3 + k4 + k5 == 100,
k1 >= 0, k2 >= 0, k3 >= 0, k4 >= 0, k5 >= 0},
{k1, k2, k3, k4, k5}, Integers];
Length[S]
(*    4598126    *)