194 views
• Using numbers from  S = $\left \{ 1,2,3,4.......n \right \}$
• We can use maximum up to m numbers to form a set using numbers from S. Repetition of numbers allowed.
• How many ways we can form a set such that,  $\sum x_i = K$.  Where $K$ is another positive integer. Where $x_i$ are the elements belong $S$ that are included in the newly formed set.

For example :

• S = $\left \{ 1,2,3,4,5...11,12 \right \}$
•  m = $4$
• if $K = 6$
• Then possible few possible sets are $\{2,4\}, \;\; \{1,3,2\}, \;\; \{1,4,1\},\;\; \{1,1,1,3\}$ etc.
• $\{1,1,1,1,2\}$ is not valid set for example.
• Now how many such sets for a particular instance of the problem ? with
• S = $\left \{ 1,2,3,4,5,6...12 \right \}$ , $m = 5$, $K = 8$ ?
• If there is any generic idea ?
• Ordered / Unordered both the cases !
retagged | 194 views
Do we have to count {1,2,3} and {1,3,2} different ?
no need to count ..updated !
After a little bit of work around I ended up with 16 as the answer to this specific question. Let me know if that is right, I will then share my approach.

Ii don't know share your approach!

Actually, I need the ordered collection only ..sorry for describing the QS as an unordered set. @kapil asked earlier about this.

will this recurrence work ? for ordered collection?

f(m,k) = no of ordered collection using the numbers from S

$f(m,k) = \begin{cases} 1 \qquad m=0 , k = 0\\ \\ 0 \qquad m=0 , k > 0\\ \\ \sum_{x_i \; }^{\{\{0\} \cup S \}\;} f(m-1,k-x_i) \quad m \geq 1 , (k+x_i) \geq 0 \\ \end{cases}$

@Debashish we can solve using generating functions .

$G(x)=(x+x^{2}+x^{3}+...+x^{m})^{n}$

which is infinite series. The number of such sets would be of coefficient $x^{k}$.

in my openion no of subset possible with a given set is countable ,

approach is we have to enumarate it by some another way

first take 0 length subset which is 1

then take 1 lenth subset which is n

then take 2 lenth subset and count all the two length subset passoibel

similarly we can enumarate them so , its countable
answered by Loyal (3.8k points)

+1 vote