Kvadratların cəmi Cnk#11271

Kvadratların cəmi Cnk (Həll təhlili)

$2 n$ müxtəlif obyektdən ibarət $a_{1}, ..., a_{2 n}$ a_1, ..., a_{2n} çoxluğuna baxaq və bu çoxluqdan $n$ obyekti neçə üsulla seçmək olduğunu hesablayaq.

Bir tərəfdən, binomial əmsalın tərifinə görə bu say $C_{2 n}^{n}$ C_{2n}^n-ə bərabərdir.

Diğər tərəfdən, çoxluğu $n$ obyektdən ibarət iki hissəyə bölək:

{a_{1}, a_{2}, ..., a_{n}} v ə {a_{n + 1}, ..., a_{2 n}}

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

$n$ obyektdən ibarət istənilən dəst, sol yarıdan götürülən obyektlərin sayı $k (0 \leq k \leq n)$ k~(0 \le k \le n) ilə birmənalı şəkildə müəyyən olunur: bu zaman sağ yarıdan dəqiq $n - k$ n - k obyekt götürülür. Sabit $k$ üçün sol yarıdan $k$ obyekti $C_{n}^{k}$ C_n^k üsulla, sağ yarıdan isə $n - k$ n - k obyekti $C_{n}^{n - k}$ C_n^{n-k} üsulla seçmək olar. Vurma qaydasına görə, verilmiş $k$ üçün dəstlərin sayı

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

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

bərabərdir, çünki simmetriya xassəsinə görə $C_{n}^{n - k} = C_{n}^{k}$ C_n^{n-k} = C_n^k.

Müxtəlif $k$ qiymətlərinə kəsişməyən dəst çoxluqları uyğun gəlir, $k$ isə $0$ -dan $n$ -ə qədər bütün qiymətləri alır. Toplama qaydasına görə, ümumi üsulların sayı

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

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

bərabərdir.

İki hesablama nəticəsini bərabərləşdirərək, aşağıdakı eyniliyi (Vandermond eyniliyinin xüsusi halı) alırıq:

(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

Misal

$n = 3$ n = 3 üçün cavab $(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-ə bərabərdir.

Eyni zamanda $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.

Alqoritmin realizasiyası

Cnk funksiyası $C_{n}^{k}$ C_n^k binomial əmsalının qiymətini hesablayır.

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

Proqramın əsas hissəsi. Giriş dəyəri $n$ -i oxuyuruq.

scanf("%lld", &n);

Cavabı hesablayıb çap edirik.

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

Java realizasiyası

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 realizasiyası

Cnk funksiyası $C_{n}^{k}$ C_n^k binomial əmsalının qiymətini hesablayır.

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

Proqramın əsas hissəsi. Giriş dəyəri $n$ -i oxuyuruq.

n = int(input())

Cavabı hesablayıb çap edirik.

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

Python realizasiyası – comb

Giriş dəyəri $n$ -i oxuyuruq.

n = int(input())

Cavabı hesablayıb çap edirik.

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