Calculating combinatorial numbers

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lgx57

14 posts

lgx57

#1 h Mar 30, 2025, 8:20 AM

Y by

Try to simplify this expression:

$\sum_{i=1}^n \sum_{j=1}^i C_{n}^i C_{n}^j$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

alexheinis

10543 posts

alexheinis

#2 h Mar 30, 2025, 8:40 AM • 1 Y

Y by MihaiT

We have $s=\sum_{k=1}^n\sum_{l=1}^k {n\choose k}{n\choose l}=\sum_{l=1}^n \sum_{k=l}^n {n\choose k}{n\choose l}=\sum_{k=1}^n \sum_{l=k}^n {n\choose k}{n\choose l}$ .
Hence $2s=\sum_{k=1}^n {n\choose k}^2+\sum_{k=1}^n \sum_{l=1}^n {n\choose k}{n\choose l}={{2n}\choose n}-1+(2^n-1)^2$ .

@generatingFraction: welcome to AOPS. To use latex just put the formulas within $-signs. It might not work for new members but it will afterwards.

This post has been edited 2 times. Last edited by alexheinis, Mar 30, 2025, 9:34 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lgx57

14 posts

lgx57

#3 h Mar 30, 2025, 9:06 AM

Y by

alexheinis wrote:

We have $s=\sum_{k=1}^n\sum_{l=1}^k {n\choose k}{n\choose l}=\sum_{l=1}^n \sum_{k=l}^n {n\choose k}{n\choose l}=\sum_{k=1}^n \sum_{l=k}^n {n\choose k}{n\choose l}$ .
Hence $2s=\sum_{k=1}^n {n\choose k}^2+\sum_{k=1}^n \sum_{l=1}^n {n\choose k}{n\choose l}={{2n}\choose n}-1+(2^n-1)^2$ .

Why is $\sum_{k=1}^n {n\choose k}^2={{2n} \choose n}-1$ ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

generatingFraction

5 posts

generatingFraction

#4 h Mar 30, 2025, 9:18 AM

Y by

You have 2n balls, calculate the numbers to choose n balls. It is the sum of choosing k in the first n balls and choosing n - k in the last n balls.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

generatingFraction

5 posts

generatingFraction

#5 h Mar 30, 2025, 9:21 AM

Y by

Also you can use generating function.
[x ^ k] (1 + x) ^ n = \binom{ n }{ k }
So \sum_{k = 1} ^ n \binom{ n }{ k } * \binom{ n }{ n - k } = [x ^ n] (1 + x) ^ {2n} = \binom{ 2n }{ n }

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

generatingFraction

5 posts

generatingFraction

#6 h Mar 30, 2025, 9:23 AM

Y by

By the way, how do your guys edit math formula ? The system showed new users can't send image.

Z K Y