Wednesday, October 15, 2008

Problem Of The Week 53

How many ways can a size k + 1 subset with maximum element m + 1 can be created from the given set S={1,2,3,.....,n+1} ?

2 comments:

  1. Here, the maximum value that m can take is n and same for k.
    Tried with examples but m not able to come to a general solution.
    When m=k, the no. of ways =1
    When m>k, the solution is
    (m+1)C{k+1) + mC(k+1) + (m-1)C(k+1)...
    A stupid solution I know. Working on generalizing this.
    Still in CAT the best way to tackle such questions would be to go for value of n=5/6 and the values of k upto 5 and similarly for m.

    ReplyDelete
  2. its simpler
    the highest term can be selected in one way
    as it is m+1

    now other k terms have to be selected from m values
    so mck

    ReplyDelete