Discrete math combinatorial proof. Prove that for every positive integer n, ((n),(k))^2 =sum_{l=0}^{n} sum_{r=0}^{(n-l)/2}((n),(l))((n-l),(r))((n-l-r),(r))

Donna Flynn

Donna Flynn

Answered question

2022-07-17

Discrete math combinatorial proof
Prove that for every positive integer n,
k = 0 n ( n k ) 2 = l = 0 n r = 0 n l 2 ( n l ) ( n l r ) ( n l r r )
I know that k = 0 n ( n k ) 2 = ( 2 n n ) but I can't seem to find a way to connect it to the right side.

Answer & Explanation

Tamoni5e

Tamoni5e

Beginner2022-07-18Added 14 answers

Step 1
The lefthand side is the number of pairs ⟨A,B⟩ such that A and B are subsets of [ n ] = { 1 , , n }, and | A | = | B | .
Step 2
You can classify these pairs according to the number of elements that they have in common. Suppose that C = A B; then A∖C and B∖C must be disjoint subsets of [n]. Think of setting = | C | and r = | A C | = | A B | .

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Discrete math

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?