+355 Let $n$ be a positive integer.
(a) There are $n^2$ ordered pairs $(a,b)$ of positive integers, where $1 < a,$ $b < n.$ Using a counting argument, show that this number is also equal to \[n + 2 \binom{n}{2}.\]
(b) There are $n^3$ ordered triples $(a,b,c)$ of positive integers, where $1 < a,$ $b,$ $c < n.$ Using a counting argument, show that this number is also equal to \[n + 3n(n - 1) + 6 \binom{n}{3}.\]
+1926 Alright, I'll try to tackle this problem!
(a) We can try to count the number of ordered pairs (a, b) ourselves. We can split these into two cases.
1. \(a=b\)
2. \(a \neq b\)
1. Since we can choose any numbers between 1 and n, there are obviously n possibilities we can achieve.
2. Since we can choose any 2 numbers between 1 and n that are not equal, we just have \(n \choose 2\).
Hence, we just have \(n+\)\(n \choose 2\) \(+ \)\(n \choose 2\), which is exactly what we wanted in the first place.
I hope I answered part (a) correctly!
Thanks! :)
+1926 (b) For question b, we basically do the same exact thing as stated above.
First, let's review the cases for \(a=b=c \).
There are obviously n such triplets.
Next, let's look at when exactly two are the same. You have 3 choices for which number is repeated and then n choices for the repeated number, and then n-1 for the distinct number. This gets us 3n(n-1).
Lastly, we have 3 different numbers. There are \(6\)\(n \choose 3\) ways because there are 3 distinct numbers out of n and 3! = 6 ways to do this.
Thus, when we add them together, we get \(n + 3n(n - 1) + 6 \binom{n}{3}.\)!
Thanks! :)
