Formula for how many different weights are possible?

Question

Suppose a set of weights contains one 1g, one 2g and two 10g. There are 11 different weights that can be achieved by combining these.

Is it possible to come up with a formula that would calculate the number of different combinations possible for any set of weights? (For example, a 2g + 3g and 5g are equal, so will count as only one).

You could use generating functions, more about that here https://en.wikipedia.org/wiki/Generating_function — Jeff Hanks, Mar 27 '22 at 14:14

score 0 · Answer 1 · answered Apr 09 '23 at 11:36

Your example would have 12 weights if you counted weight = 0 as well. This is 2x2x3 different weights.

As long as you cannot produce the same weight in two different ways you just multiply (number of coins plus 1).

Otherwise you can take two coin values and find all their combinations, and may be that’s the only possible duplicates. Say 3 one penny, three two penny, 100 ten-penny. 1+2 produce 10 combinations 0 to 9, so you get 10 x 101 values.

hjpotter92 · Answer 2 · 2014-07-02T05:37:12.067

0

If you have $n$ types of weights, of which $m$ have more than one copy in the sample space with copies $p_1, p_2, \cdots , p_m$; then you can find the total number of combinations as:

$$ \dfrac{n!}{p_1! \cdot p_2! \cdots p_m!} - m $$

The $m$ is subtrated because those $ m $ pieces are not unique and all of them will be counted as a single piece.

In case of $2$g, $3$g and $5$g, you can achieve: $ \dfrac{3!}{0!} = 6 $ combinations: $ 2, 3, 5, 7, 8, 10 $ g respectively.

edited Jul 02 '14 at 05:37

answered Jul 02 '14 at 05:27

hjpotter92

3,049

2

But this does not count for situations where two different combinations add up to the same weight, does it? – thameera Jul 02 '14 at 05:30
1

@thameera Check the updated answer – hjpotter92 Jul 02 '14 at 05:31
1

I see. But in the first example in my question the weights 1, 2, 10, 10 has 11 combinations, but this seems to give 4!/2! = 12. – thameera Jul 02 '14 at 05:34
1

Sorry, I forgot to subtract $m$. – hjpotter92 Jul 02 '14 at 05:36
3

It is a complicated problem, and one cannot expect a simple general expression. One might look for a generating functions approach. That will, however, only shift the problem. – André Nicolas Jul 02 '14 at 05:37

Formula for how many different weights are possible?

2 Answers2