GATE CSE
First time here? Checkout the FAQ!
x
+5 votes
149 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 !
asked in Combinatory by Veteran (40.9k points)  
edited by | 149 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}$.

1 Answer

0 votes
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.3k points)  
Top Users Feb 2017
  1. Arjun

    5166 Points

  2. Bikram

    4204 Points

  3. Habibkhan

    3748 Points

  4. Aboveallplayer

    2986 Points

  5. sriv_shubham

    2298 Points

  6. Debashish Deka

    2234 Points

  7. Smriti012

    2142 Points

  8. Arnabi

    1998 Points

  9. mcjoshi

    1626 Points

  10. sh!va

    1552 Points

Monthly Topper: Rs. 500 gift card

20,815 questions
25,974 answers
59,606 comments
22,025 users