Розбір

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

We’ll divide the set in half: $\{a_1,a_2,...,a_n,a_{n+1},...,a_{2n}\}$. To choose $n$ objects from $2n$, we’ll select $k(k\le 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_{2n}\})$. 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 $2n$, which is equal $C_{2n}^n$. Thus,

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)