Binomial cəm#11488

Binomial cəm (Həll təhlili)

Verilən cəmi aşağıdakı kimi yazırıq:

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

1 \cdot C_n^0 + 2 \cdot C_n^1 + 3 \cdot C_n^2 + ... + (n + 1) \cdot C_n^n =

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

\left( C_n^0 + C_n^1 + C_n^2 + ... + C_n^n \right) + 1 \cdot C_n^1 + 2 \cdot C_n^2 + ... + n \cdot C_n^n

Möhtərizədəki cəm $2^{n}$ 2^n-ə bərabərdir. Əgər Nyutonun binomu formulunda

(a + b)^{n} = i = 0 \sum n C_{n}^{i} a^{i} b^{n - i}

(a + b)^n = \sum_{i=0}^n{C_n^ia^ib^{n-i}}

də $a = b = 1$ a = b = 1 qoysaq, o zaman $(1 + 1)^{n} = \sum_{i = 0}^{n} C_{n}^{i} 1^{i} 1^{n - i}$ (1 + 1)^n = \sum_{i=0}^n{C_n^i1^i1^{n-i}} və ya

2^{n} = i = 0 \sum n C_{n}^{i} = C_{n}^{0} + C_{n}^{1} + ... + C_{n}^{n}

2^n = \sum_{i=0}^nC_n^i = C_n^0 + C_n^1 + ... + C_n^n

Qalan cəmi hesablayırıq:

1 \cdot C_{n}^{1} + 2 \cdot C_{n}^{2} + ... + n \cdot C_{n}^{n} =

1 \cdot C_n^1 + 2 \cdot C_n^2 + ... + n \cdot C_n^n =

1 \cdot \frac{n !}{1 ! \cdot ( n - 1 )!} + 2 \cdot \frac{n !}{2 ! \cdot ( n - 2 )!} + ... + n \cdot \frac{n !}{n ! \cdot ( n - n )!} =

1 \cdot {n! \over 1! \cdot (n - 1)!} + 2 \cdot {n! \over 2! \cdot (n - 2)!} + ... + n \cdot {n! \over n! \cdot (n - n)!} =

n \cdot (\frac{( n - 1 )!}{0 ! \cdot ( n - 1 )!} + \frac{( n - 1 )!}{1 ! \cdot ( n - 2 )!} + ... + \frac{( n - 1 )!}{( n - 1 )! \cdot ( n - n )!}) =

n \cdot \left( {(n - 1)! \over 0! \cdot (n - 1)!} + {(n - 1)! \over 1! \cdot (n - 2)!} + ... + {(n - 1)! \over (n - 1)! \cdot (n - n)!} \right) =

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

n \cdot \left( C_{n-1}^0 + C_{n-1}^1 + ... + C_{n-1}^{n-1} \right) = n \cdot 2^{n - 1}

Beləliklə, cavab $2^{n} + n \cdot 2^{n - 1} = (n + 2) \cdot 2^{n - 1}$ 2^n + n \cdot 2^{n - 1} = (n + 2) \cdot 2^{n - 1}.

Nümunə

$n = 3$ n = 3 üçün cavabı hesablayaq. Birbaşa hesablama zamanı:

1 \cdot C_{3}^{0} + 2 \cdot C_{3}^{1} + 3 \cdot C_{3}^{2} + 4 \cdot C_{3}^{3} = 1 \cdot 1 + 2 \cdot 3 + 3 \cdot 3 + 4 \cdot 1 = 1 + 6 + 9 + 4 = 20

1 \cdot C_3^0 + 2 \cdot C_3^1 + 3 \cdot C_3^2 + 4 \cdot C_3^3 = 1 \cdot 1 + 2 \cdot 3 + 3 \cdot 3 + 4 \cdot 1 = 1 + 6 + 9 + 4 = 20

Formula ilə hesablandıqda: $5 \cdot 2^{2} = 20$ 5 \cdot 2^2 = 20.

Alqoritmin reallaşdırılması

Verilmiş $n$ dəyərini oxuyuruq.

scanf("%lld", &n);

Cavabı hesablayır və çap edirik.

res = (1LL << (n - 1)) * (n + 2);
printf("%lld\n", res);

Alqoritmin reallaşdırılması – funksiya

Nəticələri yadda saxlamaq üçün massiv elan edirik: $d p [n] [k] = C_{n}^{k}$ dp[n][k] = C_n^k.

int dp[31][31];

Cnk funksiyası binominal əmsalın $C_{n}^{k}$ C_n^k dəyərini hesablayır.

int Cnk(int n, int k)
{
  if (n == k) return 1;
  if (k == 0) return 1;
  if (dp[n][k] != -1) return dp[n][k];
  return dp[n][k] = (Cnk(n - 1, k - 1) + Cnk(n - 1, k)) % 9929;
}

C++

Proqramın əsas hissəsi. Verilmiş $n$ dəyərini oxuyuruq.

scanf("%d", &n);
memset(dp, -1, sizeof(dp));

Verilən cəmi hesablayırıq.

res = 0;
for (i = 0; i <= n; i++)
  res += (i + 1) * Cnk(n, i);

Cavabı çıxarırıq.

printf("%d\n", res);

Python reallaşdırılması – comb funksiyası

import math

Verilən $n$ dəyərini oxuyuruq.

n = int(input())

Verilən cəmi hesablayırıq. Binominal əmsalı hesablamaq üçün daxil edilmiş comb funksiyasından istifadə edirik.

res = 0
for i in range(n + 1):
  res += (i + 1) * math.comb(n, i)

Cavabı çıxarırıq.

print(res)

Python reallaşdırılması – funksiya

Cnk funksiyası binominal əmsalın $C_{n}^{k}$ C_n^k dəyərini hesablayır.

def Cnk(n, k, dp):
  if n == k: return 1
  if k == 0: return 1
  if dp[n][k] != -1: return dp[n][k]
  dp[n][k] = Cnk(n - 1, k - 1, dp) + Cnk(n - 1, k, dp)
  return dp[n][k]

Proqramın əsas hissəsi. Verilən $n$ dəyərini oxuyuruq.

n = int(input())

İkiölçülü siyahının bütün elementlərini $- 1$ dəyəri ilə başlatırıq. Siyahını nəticələri yadda saxlamaq üçün istifadə edirik: $d p [n] [k] = C_{n}^{k}$ dp[n][k] = C_n^k.

dp = [[-1 for _ in range(31)] for _ in range(31)]

Verilən cəmi hesablayırıq.

res = 0
for i in range(n + 1):
   res += (i + 1) * Cnk(n, i, dp)

Cavabı çıxarırıq.

print(res)

Python reallaşdırılması – formula

Verilən $n$ dəyərini oxuyuruq.

n = int(input())

Formulaya əsasən $r es$ cavabını hesablayırıq.

res = (1 << (n - 1)) * (n + 2)

Cavabı çıxarırıq.

print(res)