Count the coins including permutations of the same sequence

Question

I've found a code to find number of possibilities to make change using given coins: How to count possible combination for coin problem. But how to count it, if we think about different permutations of the same sequence? I mean that, e.g. amount is 12, and "4 4 2 2" and "4 2 4 2" should be counted as 2, not 1.

Answer 1

As you've mentioned inside your question you can count the possible combinations as stated in How to count possible combination for coin problem. But in order to include the permutations into your answer:

1. If you distinguish the permutation of the same numbers [1 7 7] and [1 7 7] e.g. just count each sequence([1 7 7] here) as n! (n = # of elements in the sequence) [instead of 1]
2. Otherwise : multiply each sequence by n!/(m!l!...) where m = number of equal elements of type 1, l is number of equal elements of type 2 and so on... . For example for sequence like [a b b c c c] you should count this 6!/(2!*3!) [instead of 1]

---

So use the algorithm inside that link, that I don't repeat again, but just instead of counting each combination as 1 use the formula that I said (depending on the case you desire).

(! is factorial.)