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.
$\begingroup$
$\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
$\begingroup$
$\endgroup$
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:
$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}$$
$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$$
answered Feb 14 '18 at 13:56
-
1
$\begingroup$
$\endgroup$
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}$$
-
$\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
