I am trying to find the number of compositions of a given number restricted by the numbers present in a subset. I read that this is called A-Restricted Composition. where A is a set of numbers
Composition of 10 from set A(1,2,3)
1x10
1x8+2x1
2x1+1x8
2x2+1x6
3x2+2x2
2x2+3x2 -> Different order than last one
2x5
etc etc.
Number of Compositions of a number n = 2^(n-1)
But how can I calculate if the parts of the composition is restricted to a set of numbers, without finding each one of them?
If I try to find each one of them, it could be very erroneous.