2
$\begingroup$

What are the total number of ways in which $i$,$j$ can be chosen subject to constrain $1\leq i \leq j \leq n$ ? All are integers. My progress is: I believe that out of the $n$ entries, there are $n \choose 2$ ways to choose $i,j$. But, the given answer is ${n \choose 2} + n$. Some explanation would be helpful.

|cite|improve this question
$\endgroup$
  • $\begingroup$ What are $i, j, n$? Are they natural numbers, real numbers, etc... $\endgroup$ – Mr Pie Feb 14 '18 at 8:04
  • $\begingroup$ Don't you mean $1\leq i\cdots$? Then the given answer is okay. $n$ is added because $i=j$ is allowed. That gives $n$ extra possibilities. $\endgroup$ – drhab Feb 14 '18 at 8:11
2
$\begingroup$

We want to find the number of ways we can choose integers $i, j$ such that $1 \leq i \leq j \leq n$. There are two possibilities:

  1. $i < j$: The number of such selections is the number of two element subsets $\{1, 2, 3, \ldots, n\}$ since the smaller number we select must be $i$ and the larger one must be $j$. The number of such subsets is $$\binom{n}{2}$$

  2. $i = j$: The number of such selections is the number of ways we can select one element from the set $\{1, 2, 3, \ldots, n\}$ since the selected number must equal both $i$ and $j$. The number of ways we can do this is $n$.

Since these cases are mutually exclusive and exhaustive, the number of ways we can choose integers $i, j$ such that $1 \leq i \leq j \leq n$ is $$\binom{n}{2} + n$$

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Thank you for the lucid explanation. $\endgroup$ – LumosMaxima Feb 14 '18 at 14:31
2
$\begingroup$

For $j$ a number in $\{1,\ldots,n\}$ you have $j$ choices of $i$ since $i\in\{1,\ldots,j\}$ so the total number of choices is

$$\sum_{j=1}^n j =\frac{n(n+1)}{2}$$

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Right. But, why is the answer given in the form nC2 + n? $\endgroup$ – LumosMaxima Feb 14 '18 at 8:00
  • $\begingroup$ I know that the two are same. But, by what logic can I arrive at the answer of nC2 + n? $\endgroup$ – LumosMaxima Feb 14 '18 at 8:01
  • $\begingroup$ $n$ is the number of the cases where $i=j$ and you have $nC2$ choices of different numbers $i$ and $j$. $\endgroup$ – user296113 Feb 14 '18 at 8:02
  • $\begingroup$ Alright. So, how does n get added? I mean, in the range [1,n], I have nC2 choices of i,j picked arbitrarily. What after that? $\endgroup$ – LumosMaxima Feb 14 '18 at 8:03
  • 1
    $\begingroup$ Thanks a lot. That surely helped. $\endgroup$ – LumosMaxima Feb 14 '18 at 8:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.