Somma dei quadrati di Cnk#11271

Somma dei quadrati di Cnk (Editoriale)

Consideriamo un insieme di $2 n$ oggetti distinti $a_{1}, ..., a_{2 n}$ a_1, ..., a_{2n} e calcoliamo in quanti modi si possono scegliere da esso $n$ oggetti.

Da un lato, per definizione di coefficiente binomiale, questo numero è uguale a $C_{2 n}^{n}$ C_{2n}^n.

Dall'altro lato, dividiamo l'insieme in due metà di $n$ oggetti ciascuna:

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

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

Qualsiasi insieme di $n$ oggetti è determinato univocamente da quanti oggetti $k (0 \leq k \leq n)$ k~(0 \le k \le n) vengono presi dalla metà sinistra: allora dalla metà destra vengono presi esattamente $n - k$ n - k oggetti. Per un $k$ fissato, scegliere $k$ oggetti dalla metà sinistra si può fare in $C_{n}^{k}$ C_n^k modi, e $n - k$ n - k oggetti dalla metà destra — in $C_{n}^{n - k}$ C_n^{n-k} modi. Per la regola del prodotto, il numero di insiemi con un dato $k$ è uguale a

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

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

poiché per la proprietà di simmetria $C_{n}^{n - k} = C_{n}^{k}$ C_n^{n-k} = C_n^k.

Per valori diversi di $k$ si ottengono insiemi disgiunti di combinazioni, e $k$ percorre tutti i valori da $0$ a $n$ . Per la regola della somma, il numero totale di modi è uguale a

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

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

Uguagliando i due risultati del conteggio, otteniamo l'identità (caso particolare dell'identità di Vandermonde):

(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

Esempio

Per $n = 3$ n = 3 la risposta è uguale a $(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

Allo stesso tempo $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.

Implementazione dell'algoritmo

La funzione Cnk calcola il valore del coefficiente binomiale $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++

Parte principale del programma. Leggiamo il valore di input $n$ .

scanf("%lld", &n);

Calcoliamo e stampiamo la risposta.

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

Implementazione in 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++

Implementazione in Python

La funzione Cnk calcola il valore del coefficiente binomiale $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

Parte principale del programma. Leggiamo il valore di input $n$ .

n = int(input())

Calcoliamo e stampiamo la risposta.

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

Implementazione in Python – comb

Leggiamo il valore di input $n$ .

n = int(input())

Calcoliamo e stampiamo la risposta.

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