3
$\begingroup$

$K$ numbers are chosen with replacement from the numbers $1,2,3, \cdots N$.In how many ways we can choose the numbers so that the maximum number chosen is exactly $R \le N $ ?

The explanation given in my module is like this :

Since the maximum number is $R$, each of $K$ numbers can be chosen in $R$ ways.so, the number be can be chosen in $R^K$ ways.These includes the $(R-1)^k$ choices in which none of the $K$chosen numbers is $R$. Hence, the required number is $R^K - (R-1)^k $.

I am not getting this explanation,and after reading Arturo Magidin's answer I am somewhat more confused now.

  • 0
    @Debanjan: Oh, that's because I screwed up. Mine is the way so the maximum is at *most* R, not exactly R.2010-11-11
  • 0
    @Debanjan: Corrected now. I've explained what I was thinking, and I've explained their answeer. And now, to bed.2010-11-11
  • 0
    @Debanjan: Please pick a better title.2010-11-11
  • 0
    @Moron: Please suggest one :)2010-11-11
  • 0
    @Debanjan: "Number of ways to choose by restricting maximum" or something like. "A problem in Combinatorics" is too generic a title. Please read the FAQ/meta threads on how to post new questions. For instance: http://meta.math.stackexchange.com/questions/588/how-can-i-ask-a-good-question/646#646. btw -1 till you edit the title.2010-11-11
  • 0
    @Moron: I guess it is okay now ? Also I am changing the title of some of other questions I asked before.2010-11-11
  • 1
    @Deb: Yes, better :-) Removed the -1.2010-11-11

2 Answers 2

4

The explanation in your module is a common technique in combinatorics. If you want to count how many there are of something, count some set that includes all of them and some more, then subtract out the members of the set that don't belong. We can work a small example (unfortunately the numbers get large quickly). Let K=4, R=2. N doesn't matter in this problem as we just throw away all the numbers $\{R+1, R+2, R+3,\ldots,N\}$. There are $2^4=16$ strings of four numbers with each number being 1 or 2. You can list them-they look like the binary numbers from 0 to 15 with the zeros changed to twos. But one =1^4 of them is all ones, so we shouldn't count it. The answer is $15=2^4-1^4=R^K-(R-1)^K$

  • 0
    I understood the problem form this line `N doesn't matter in this problem as we just throw away all the numbers {R+1,R+2,R+3,…,N}.` the rest is not much hard to figure :)2010-11-11
5

EDIT: My original answer was incorrect even with the interpretation I had in mind. Here is the correction.

I originally gave a formula for the number of ways to pick $K$ numbers so that the maximum is at most $R$, rather than exactly $R$. Moreover, I interpreted the question as asking for the number of different selections, so that if you first picked $1$ and then $2$, this was the same "pick" as first picking $2$ and then $1$.

If we interpret it that way, so that we are asking for different multisets of choices, then we are asking about combinations with repetitions.

The number of ways of choosing $r$ objects from among $n$ objects with replacement is $\binom{n+r-1}{r}$.

So the number of ways to pick $K$ from among the $R$ that are less than or equal to $R$ is $\binom{R+K-1}{K}$. However, some of them will not include the number $R$; how many? Well, $\binom{(R-1)+K-1}{K}=\binom{R-K-2}{K}$, since these are the number of choices from among the first $R-1$ instead. Thus, the total with this interpretation is:

\begin{equation*} \binom{R+K-1}{K} - \binom{R+K-2}{K} = \binom{R+K-2}{K-1}. \end{equation*}

Alternatively, reserve one spot for for $R$, and then pick the remaining $K-1$ any way you want from among the first $R$.

However, the explanation posted tells us that in fact they are thinking of the order of the choices as important: so picking $1$ first and $2$ second is different from picking $2$ first and $1$ second.

In that case, we can pick any of the first $R$ numbers at each step, $K$ steps, so that gives $R^K$ choices. In some of them we never picked $R$, however; how many? Well, if we can only pick from among $1,\ldots,R-1$, then by the same argument we have $(R-1)^K$ possibilities. So the total is $R^K - (R-1)^K$ as explained there.

Added: Since, as you say, you've never seen the formula for combinations with repetitions, and since it is dear to my heart (I figured it out from scratch during my first semester, when considering the question of how many different rolls with $n$ $r$-sided dice there are by constructing a big table, eventually recognizing it as Pascal's Triangle on its side, then using the combinatorial formula for the entry to get the formula, and finally coming up with a proof of it) (and that was probably more than you needed to know) here goes:

Suppose you have $n$ elements; without loss of generality, assume they are the numbers $1$ through $n$. Now, we want to pick $r$ elements form them with repetitions, so we will have $b_1,\ldots,b_r$. Order them so that $b_1\leq b_2\leq\cdots\leq b_r$. Now consider the vector $(b_1,b_2+1,b_3+2,\ldots,b_{r}+r-1)$. Then the entries of these vector are all distinct, and each entry is a number between $1$ and $n+r-1$. Different choices lead to different vectors, so the number of possible choices with repetitions is at most the number of ways to pick $r$ objects from $n+r-1$ possibilities without repetition.

Conversely, suppose you pick $r$ numbers from among $1,2,\ldots,n+r-1$ without repetition, $a_1,a_2,\ldots,a_r$. Order them so that $a_1\lt a_2\lt\cdots\lt a_r$. Then consider $(a_1, a_2-1, a_3-2,\ldots,a_r-r+1)$. Since $a_i\geq i$, then $a_i-(i-1)\geq 1$, and $a_i\lt a_{i+1}$ so $a_i-i+1 \leq a_{i+1}-i$. Thus, this new vector corresponds, as before, to a choice of $r$ numbers from among $1,2,\ldots,n$ with repetitions allowed. Different choices lead to different vectors, so the number of possible ways to pick $r$ objects from $n+r-1$ possibilities without repetition is at most the number of ways to pick $r$ objects from among $n$ possibilities with repetions.

Thus, the two quantities are equal. Since the number of ways to pick $r$ objects from among $n+r-1$ possibilities without repetition is $\binom{n+r-1}{r}$, the formula follows.

(When I proved it to myself, I took my original set and added symbols "R1", "R2",$\ldots$,R(r-1), which stood for "repeat position 1", "repeat position 2", etc. Then I picked from among $1,2,\ldots,n$,R1,R2,$\ldots$,R(r-1) without repetition, and wrote them in order, with $1\lt 2\lt\cdots\lt n\lt$ R1$\lt\cdots\lt$ R(r-1); this then gave me a "pick with repetitions".)

  • 0
    @Debanjan: Or is the problem that you do not know the formula for combinations with replacement?2010-11-11
  • 0
    Yes I never knew this formula , I just searched through my module they haven't mentioned it,I wonder why is it so :(2010-11-11
  • 0
    I really appreciate the proof, moreover I was going to ask for it :)2010-11-11
  • 0
    +1,A great explanation! :) I really learned a lot from it,but honestly I didn't understood your approach much unless I read Ross's answer and it's mainly because I haven't understood the question before that so I think it will be nice if I accept his answer, but truly I am really grateful to you for this post :)2010-11-11
  • 2
    @Debanjan: Not a problem; one accepts the answer one finds most helpful/nicest/best. Since Ross's was the one that really made the penny drop, and mine assumed too much, then Ross's answer is the appropriate one to accept.2010-11-11