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}.\]

Lilliam0216 May 23, 2024

#1**+1 **

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! :)

NotThatSmart May 23, 2024

#2**0 **

(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! :)

NotThatSmart May 23, 2024