+0

# help with counting

0
24
1
+1348

Help how do I count

Let n be a positive integer.  Let k be a positive integer.

(a) Using a counting argument, show that C(n - 1, k - 1) + C(n - 1, k) = C(n,k).

(b) Using a counting argument, show that C(n,0) + C(n,1) + C(n,2) + ... + C(n,n) = 2^n.

(c) Using a counting argument, show that C(n,0) + C(n + 1,1) + C(n + 2,2) + C(n + 3,3) + ... + C(n + k,k) = C(n + k + 1,k)

(d) Using a counting argument, show that C(m,0) C(n,r) + C(m,1) C(n,r - 1) + ... + C(m,r) C(n,0) = C(m + n,r).

(e) There are n^2 ordered pairs (a,b) of positive integers, where 1 \le a, b \le n.  Using a counting argument, show that this number is also equal to
(n + 1)^2 - 2n - 1

(f) There are n^3 ordered triples (a,b,c) of positive integers, where 1 \le a, b, c \le n.  Using a counting argument, show that this number is also equal to
(n + 1)^3 - 3n^2 - 3n - 1

Oct 6, 2023

#1
+27
0

(b) Suppose we have \(n\) people and we want to make a committee of arbitary size. The amount of ways we can choose a committee of 0 people is \(\dbinom{n}{0}\). The amount of ways we can choose a committee of 1 person is \(\dbinom{n}{1}\). In general, the amount of ways we can choose a committee of k people is \(\dbinom{n}{k}\). Then, the total would be

\(\dbinom{n}{0} + \dbinom{n}{1} + \dbinom{n}{2} + \cdots + \dbinom{n}{n}\)

ways. However, notice that this is also equivalent to choosing whether or not a person should be on the committee. Each person has 2 choices - be on the committee or don't. Then, there are \(2^n\) total ways. Conclusively, \(\dbinom{n}{0} + \dbinom{n}{1} + \dbinom{n}{2} + \cdots + \dbinom{n}{n}\)=\(2^n\).

Oct 8, 2023