Sum of squares Cnk#11271

Sum of squares Cnk (Editorial)

Consider a set of $2 n$ distinct objects $a_{1}, ..., a_{2 n}$ a_1, ..., a_{2n} and count the number of ways to choose n objects from it.

On the one hand, by the definition of the binomial coefficient, this number equals $C_{2 n}^{n}$ C_{2n}^n.

On the other hand, split the set into two halves of $n$ objects each:

{a_{1}, a_{2}, ..., a_{n}} an d {a_{n + 1}, ..., a_{2 n}}

\{a_1, a_2, ..., a_n\}~and~\{a_{n+1}, ..., a_{2n}\}

Any selection of $n$ objects is uniquely determined by how many objects $k (0 \leq k \leq n)$ k~(0 \le k \le n) are taken from the left half: then exactly $n - k$ n - k objects are taken from the right half. For a fixed $k$ , one can choose $k$ objects from the left half in $C_{n}^{k}$ C_n^k ways, and $n - k$ n - k objects from the right half in $C_{n}^{n - k}$ C_n^{n-k} ways. By the rule of product, the number of selections with a given $k$ is

C_{n}^{k} \cdot C_{n}^{n - k} = (C_{n}^{k})^{2},

C_n^k \cdot C_n^{n-k} = (C_n^k)^2,

since, by the symmetry property, $C_{n}^{n - k} = C_{n}^{k}$ C_n^{n-k} = C_n^k.

Different values of $k$ give disjoint sets of selections, and $k$ ranges over all values from $0$ to $n$ . By the rule of sum, the total number of ways is

k = 0 \sum n (C_{n}^{k})^{2}

\sum_{k=0}^n{(C_n^k)^2}

Equating the two counts, we obtain the identity (a special case of Vandermonde's identity):

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

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

Example

For $n = 3$ 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$ (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$ C_6^3 = {6! \over 3! \cdot 3!} = {4 \cdot 5 \cdot 6 \over 6} = 20.

Algorithm implementation

The function Cnk computes the value of the binomial coefficient $C_{n}^{k}$ 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;
}

C++

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 implementation

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();
  }
}

C++

Python implementation

The function Cnk computes the value of the binomial coefficient $C_{n}^{k}$ 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 implementation — comb

Read the value of $n$ .

n = int(input())

Compute and print the answer.

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