+0  
 
0
3
2
avatar+295 

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

 May 23, 2024
 #1
avatar+1204 
+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! :)

 May 23, 2024
 #2
avatar+1204 
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! :)

 May 23, 2024

4 Online Users

avatar
avatar
avatar
avatar