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?


marked as duplicate by N. F. Taussig combinatorics Jun 13 at 17:34

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

migrated from mathematica.stackexchange.com Jun 13 at 14:37

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

  • 1
    $\begingroup$ Wrong exchange - you're after Mathematics stack, this is for the software Mathematica. That said, Google "Weak Composition"... $\endgroup$ – rasher Jun 13 at 8:45
  • $\begingroup$ I wouldn't call a place with about a million residents a 'village'. $\endgroup$ – 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];
(*    4598126    *)

Not the answer you're looking for? Browse other questions tagged or ask your own question.