edited by
1,701 views

1 Answer

Best answer
1 votes
1 votes

First let's solve the Question(Example 5) :

Q : What will be the Next larger 4-combination of the set $\left \{ 1,2,3,4,5,6 \right \}$ after $\left \{ 1,2,5,6 \right \}$ :

 See, the $Meaning$ of $r-combinations$ : 

  1. The $r-combinations$ can be listed using lexicographic order.
  2. A $r-combination$ is a subset of $r$ elements which are listed in increasing order.

 Now, Using this Definition, we can directly(intuitively) find the Next larger 4-combination of the set $\left \{ 1,2,3,4,5,6 \right \}$ after $\left \{ 1,2,5,6 \right \}$ which will be $\left \{ 1,3,4,5 \right \}$ (because of simple Dictionary order and with the added condition of being increasing.)

The First 4-combination will be $\left \{ 1,2,3,4 \right \}$ (as it would be in Dictionary) (NOTE that $\left \{ 1,1,1,1 \right \}$) can't be the first 4-combination in the Dictionary as there is added condition of "Increasing order"..A $4-combination$ is a subset of $4$ elements which are listed in increasing order.)

The next 4-combination will be $\left \{ 1,2,3,5 \right \}$ as in dictionary. 

So, let's list some combinations as they would be present in the 4-combinations dictionary :

1. $\left \{ 1,2,3,4 \right \}$

2. $\left \{ 1,2,3,5 \right \}$

3. $\left \{ 1,2,3,6 \right \}$

Now, the series that begins with $1,2,3$ (in that order) has ended. 

4. $\left \{ 1,2,4,5 \right \}$ 

5. $\left \{ 1,2,4,6 \right \}$

Now, the series that begins with $$1,2,4$(in that order) has ended. 

6. $\left \{ 1,2,5,6 \right \}$

Now, the series that begins with $1,2,5$(in that order) has ended. 

And so on. So, that is the intuitive idea. It tells us what is actually happening here.


Now, You can just easily prove that the Algorithm for finding the Next r-combination which is as follows :

Algorithm $r$ : 

[ The next r-combination after $a_1a_2 ··· a_r$ can be obtained in the following way:

First, locate the last element $a_i$ in the sequence such that $a_i \neq n − r + i$. Then, replace $a_i$ with $a_{i + 1}$ and $a_j$ with $a_i + j − i + 1$, for $j = i + 1, i + 2,...,r$    ]

produces the next larger r-combination in lexicographic order.

Hint for Proving : 

1. In the above intuitive manual way we were finding the Longest Series which hasn't ended yet and we were increasing the next element(s) following this series --- in r-combination manner.  Like In Example $5$, $\left \{ 1,2,5,6 \right \}$ ... Series that begins with $1,2$ has ended. So, the Longest series that hasn't ended yet is ----which begins with $1$. So, We increased its following elements in r-combination manner which gave us $\left \{ 1,3,4,5 \right \}$

Similarly in the Algorithm $r$, Notice the point "locate the last element" 

2. In the r-combination, $\left \{ a_1,a_2,.....a_r \right \}$, What is the maximum value that $a_r$ can take?? 

$a_r$ can take maximum value $n$. Similarly, What is the maximum value that $a_1$ can take??

$a_1$ can take maximum value $n-r+1$ (Because after $a_1$ there are $r-1$ elements which will be in increasing order).

Similarly, What is the maximum value that $a_i$ can take?

Say the maximum value that $a_i$ can take is $x$, so, we can say that $x + (r-i) \leq n$ (Because after $a_i$ there are $r-i$ elements which will be in increasing order and the last element can take at most value $n$).

So, From  $x + (r-i) \leq n$, we can say that the Maximum value that $a_i$ can take, is = $n -r +i$

Now, Consider the Algorithm $r$ and make use of Hint 1 and 2....... You will have your Proof (Which Rosen has left for Reader)

selected by

Related questions

0 votes
0 votes
1 answer
1
aditi19 asked Dec 10, 2018
383 views
this is an example taken from Rosen. but I’m unable to understand to understand the solution given therecan someone pls explain me in details
1 votes
1 votes
1 answer
2
anip asked Aug 15, 2018
502 views
How to find the coefficient ( for eg $x^7$ ) in the generating function$(1+x+x^2+x^3+..)(1+x^2+x^4+x^6+..)(1+x^5+x^{10}+x^{15}+..)$ ?
1 votes
1 votes
3 answers
4
Lakshman Bhaiya asked Mar 2, 2018
4,239 views
How many ways are there to put four different employees into three indistinguishable offices when each office can contain any number of employees?