Сума квадратів Cnk#11271

Сума квадратів Cnk (Розбір)

Розглянемо множину з $2 n$ різних об'єктів $a_{1}, ..., a_{2 n}$ a_1, ..., a_{2n} і підрахуємо, скількома способами можна вибрати з неї $n$ об'єктів.

З одного боку, за визначенням біноміального коефіцієнта це число дорівнює $C_{2 n}^{n}$ C_{2n}^n.

З іншого боку, розіб'ємо множину на дві половини по $n$ об'єктів:

{a_{1}, a_{2}, ..., a_{n}} і {a_{n + 1}, ..., a_{2 n}}

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

Будь-який набір з $n$ об'єктів однозначно визначається тим, скільки об'єктів $k (0 \leq k \leq n)$ k~(0 \le k \le n) взято з лівої половини: тоді з правої половини взято рівно $n - k$ n - k об'єктів. Для фіксованого $k$ вибрати $k$ об'єктів з лівої половини можна $C_{n}^{k}$ C_n^k способами, а $n - k$ n - k об'єктів з правої — $C_{n}^{n - k}$ C_n^{n-k} способами. За правилом множення кількість наборів з даним $k$ дорівнює

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

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

оскільки за властивістю симетрії $C_{n}^{n - k} = C_{n}^{k}$ C_n^{n-k} = C_n^k.

При різних $k$ виходять множини наборів, що не перетинаються, а $k$ пробігає всі значення від $0$ до $n$ . За правилом додавання загальна кількість способів дорівнює

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

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

Прирівнюючи два результати підрахунку, отримуємо тотожність (окремий випадок тотожності Вандермонда):

(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

Приклад

Для $n = 3$ n = 3 відповідь дорівнює $(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

В той же час $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.

Реалізація алгоритму

Функція Cnk обчислює значення біноміального коефіцієнта $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++

Основна частина програми. Читаємо вхідне значення $n$ .

scanf("%lld", &n);

Обчислюємо та виводимо відповідь.

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

Java реалізація

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 реалізація

Функція Cnk обчислює значення біноміального коефіцієнта $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

Основна частина програми. Читаємо вхідне значення $n$ .

n = int(input())

Обчислюємо та виводимо відповідь.

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

Python реалізація – comb

Читаємо вхідне значення $n$ .

n = int(input())

Обчислюємо та виводимо відповідь.

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