What are the total number of ways in which $i$, $j$ can be chosen subject to constrain $1\leq i \leq j \leq n$?

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.

• What are $i, j, n$? Are they natural numbers, real numbers, etc... – Mr Pie Feb 14 '18 at 8:04
• 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. – drhab Feb 14 '18 at 8:11

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$$

• Thank you for the lucid explanation. – LumosMaxima Feb 14 '18 at 14:31

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}$$

• Right. But, why is the answer given in the form nC2 + n? – LumosMaxima Feb 14 '18 at 8:00
• I know that the two are same. But, by what logic can I arrive at the answer of nC2 + n? – LumosMaxima Feb 14 '18 at 8:01
• $n$ is the number of the cases where $i=j$ and you have $nC2$ choices of different numbers $i$ and $j$. – user296113 Feb 14 '18 at 8:02
• 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? – LumosMaxima Feb 14 '18 at 8:03
• Thanks a lot. That surely helped. – LumosMaxima Feb 14 '18 at 8:09