Біноміальна сума#11488

Біноміальна сума (Розбір)

Перепишемо задану суму у вигляді:

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

Сума в дужках дорівнює $2^{n}$ 2^n. Якщо у формулі бінома Ньютона

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

покласти $a = b = 1$ a = b = 1, то отримаємо співвідношення: $(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}}, або

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

Обчислимо залишкову суму:

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}

Таким чином, відповідь дорівнює $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 = 3$ n = 3. При безпосередньому обчисленні:

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

При обчисленні за формулою: $5 \cdot 2^{2} = 20$ 5 \cdot 2^2 = 20.

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

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

scanf("%lld", &n);

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

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

Реалізація алгоритму – функція

Оголосимо масив для запам'ятовування результатів: $d p [n] [k] = C_{n}^{k}$ dp[n][k] = C_n^k.

int dp[31][31];

Функія Cnk обчислює значення біноміального коефіцієнта $C_{n}^{k}$ C_n^k.

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

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

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

Обчислюємо вказану суму.

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

Виводимо відповідь.

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

Python реалізація – функція comb

import math

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

n = int(input())

Обчислюємо вказану суму. Для обчислення біноміального коефіцієнта використовуємо вбудовану функцію comb.

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

Виводимо відповідь.

print(res)

Python реалізація – функція

Функія Cnk обчислює значення біноміального коефіцієнта $C_{n}^{k}$ C_n^k.

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]

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

n = int(input())

Ініціалізуємо всі елементи двовимірного списку dp значенням $- 1$ . Список використовуємо для запам'ятовування результатів: $d p [n] [k] = C_{n}^{k}$ dp[n][k] = C_n^k.

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

Обчислюємо вказану суму.

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

Виводимо відповідь.

print(res)

Python реалізація – формула

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

n = int(input())

Обчислюємо відповідь $r es$ за формулою.

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

Виводимо відповідь.

print(res)