Editorial

Let’s consider $2 n$ objects $a_{1}, ..., a_{2 n}$ and find the number of ways to select $n$ objects out of $2 n$ .

We’ll divide the set in half: ${a_{1}, a_{2}, ..., a_{n}, a_{n + 1}, ..., a_{2 n}}$ . To choose $n$ objects from $2 n$ , we’ll select $k (k \leq n)$ objects from the left half (from the set ${a_{1}, a_{2}, ..., a_{n}})$ and $n - k$ objects from the right half (from the set ${a_{n + 1}, a_{n + 2}, ..., a_{2 n}})$ . The number of ways to make such a selection, according to the rule of multiplication, is equal to $C_{n}^{k} \cdot C_{n}^{n - k} = (C_{n}^{k})^{2}$ . Since $k$ can take values from $0$ to $n$ , $\sum_{k = 0}^{n} (C_{n}^{k})^{2}$ is equal to the number of ways to choose $n$ objects from $2 n$ , which is equal $C_{2 n}^{n}$ . Thus,

(C_{n}^{0})^{2} + (C_{n}^{1})^{2} + (C_{n}^{2})^{2} + ... + (C_{n}^{n})^{2} = C_{2 n}^{n}

Example

For $n = 3$ the answer is $(C_{3}^{0})^{2} + (C_{3}^{1})^{2} + (C_{3}^{2})^{2} + (C_{3}^{3})^{2} = 1^{2} + 3^{2} + 3^{2} + 1^{2} = 20$

At the same time $C_{6}^{3} = \frac{6 !}{3 ! \cdot 3 !} = \frac{4 \cdot 5 \cdot 6}{6} = 20$ .

Algorithm realization

The function Cnk computes the value of the binomial coefficient $C_{n}^{k}$ .

long long Cnk(long long n, long long k)
{
  long long res = 1;
  if (k > n - k) k = n - k;
  for (long long i = 1; i <= k; i++)
    res = res * (n - i + 1) / i;
  return res;
}

The main part of the program. Read the value of $n$ .

scanf("%lld", &n);

Compute and print the answer.

res = Cnk(2*n, n);
printf("%lld\n", res);

Java realization

import java.util.*;
 
public class Main
{
  public static long Cnk(long n, long k)
  {
    long res = 1;
    if (k > n - k) k = n - k;
    for (long i = 1; i <= k; i++)
	     res = res * (n - i + 1) / i;
    return res;
  }
	
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    long n = con.nextLong();
    long res = Cnk(2*n, n);
    System.out.println(res);
    con.close();
  }
}

Python realization

The function Cnk computes the value of the binomial coefficient $C_{n}^{k}$ .

def Cnk(n, k):
   res = 1
   if k > n - k: k = n – k
   for i in range(1, k+1):
     res = res * (n - i + 1) // i
   return res

The main part of the program. Read the value of $n$ .

n = int(input())

Compute and print the answer.

res = Cnk(2 * n, n)
print(res)

Python realization – comb

Read the value of $n$ .

n = int(input())

Compute and print the answer.

res = math.comb(2 * n, n)
print(res)