Mmedv2 роки тому

Біноміальний коефіцієнт

Сполученням з $n$ елементів по $k$ називається набір з $k$ елементів, вибраних із заданих $n$ елементів. При цьому набори, які відрізняються тільки порядком слідування елементів (але не складом), вважаються однаковими. Саме завдяки цій властивості сполучення відрізняються від розміщень.

Наприклад, розглянемо множину з $5$ елементів: ${1, 2, 3, 4, 5}$ \{1, 2, 3, 4, 5\}. Набори ${2, 1, 3}$ \{2, 1, 3\} і ${3, 2, 1}$ \{3, 2, 1\} є однаковими як сполучення (хоча різні як розміщення), оскільки складені з тих самих елементів ${1, 2, 3}$ \{1, 2, 3\}.

Формула для обчислення кількості сполучень з $n$ по $k$ дорівнює

C_{n}^{k} = \frac{n !}{k ! \cdot ( n - k )!}

C_n^{k} = {n! \over k! \cdot (n - k)!}

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

Коли ми вибираємо нуль елементів із множини з $n$ елементів, ми фактично робимо “пустий” вибір. Порожня множина, в цьому контексті, вважається допустимим сполученням. Уявіть, що у вас є коробка з $n$ кулями, і ви хочете вибрати $0$ з них. Навіть якщо ви нічого не вибираєте, це все одно є допустимим варіантом вибору. Таким чином, $C_{n}^{0}$ C_n^{0} означає кількість способів вибрати $0$ елементів з $n$ , що дорівнює $1$ .

Ми можемо розглядати це як один єдиний спосіб не вибирати жоден елемент з множини, що і дає результат $1$ .

C_{n}^{0} = \frac{n !}{0 ! \cdot ( n - 0 )!} = \frac{n !}{1 ! \cdot n !} = 1

C_n^{0} = {n! \over 0! \cdot (n - 0)!} = {n! \over 1! \cdot n!} = 1

Коли ми вибираємо один елемент із множини з $n$ елементів, у нас є $n$ варіантів вибору: ми можемо вибрати будь-який з $n$ елементів. Наприклад, якщо у нас є множина з чисел від $1$ до $5$ ( ${1, 2, 3, 4, 5}$ \{1, 2, 3, 4, 5\}), то ми можемо вибрати одне число з цієї множини, і у нас є $5$ варіантів для цього вибору.

Значення $C_{n}^{1}$ C_n^{1} дорівнює $n$ , тому що є $n$ способів вибрати один елемент з множини з $n$ елементів.

C_{n}^{1} = \frac{n !}{1 ! \cdot ( n - 1 )!} = n

C_n^{1} = {n! \over 1! \cdot (n - 1)!} = n

При виборі $2$ елементів із $n$ — елементної множини, ми формуємо комбінації пар. Для побудови такої пари ми спочатку вибираємо один елемент, а потім другий.

Перший елемент можна вибрати з $n$ елементів.
Після вибору першого елемента, у нас залишається $n -1$ елемент для вибору другого елемента (оскільки ми не можемо вибрати повторно той самий елемент).

Таким чином, загальна кількість комбінацій пар елементів, які можна вибрати з $n$ — елементної множини, дорівнює добутку числа способів вибрати перший і другий елементи: $n \cdot (n -1)$ n \cdot (n – 1).

Проте, кожна пара врахована двічі, оскільки порядок елементів у парі не має значення. Наприклад, $(p, q)$ і $(q, p)$ вважаються однією і тією ж парою. Щоб врахувати це, слід поділити загальну кількість комбінацій на $2$ . Таким чином, $C_{n}^{2}$ C_n^{2} дорівнює $n \cdot (n -1) /2$ n \cdot (n – 1) / 2.

C_{n}^{2} = \frac{n !}{2 ! \cdot ( n - 2 )!} = \frac{n \cdot ( n - 1 )}{2}

C_n^{2} = {n! \over 2! \cdot (n - 2)!} = {n \cdot (n - 1) \over 2}

Властивість симетрії: $C_{n}^{k} = C_{n}^{n - k}$ C_n^{k} = C_n^{n - k}.

Кількість способів вибрати $k$ елементів з $n$ дорівнює кількості способів не вибрати $(n - k)$ елементів з $n$ . Але не вибрати $(n - k)$ елементів з $n$ ми можемо $C_{n}^{n - k}$ C_n^{n - k} способами. Відповідно $C_{n}^{k} = C_{n}^{n - k}$ C_n^{k} = C_n^{n - k}.

Вправа. Обчислити значення наступних біноміальних коефіцієнтів:

1) $C_{5}^{2}$ C_5^{2}	3) $C_{5}^{4}$ C_5^{4}	5) $C_{8}^{1}$ C_8^{1}
2) $C_{8}^{3}$ C_8^{3}	4) $C_{7}^{5}$ C_7^{5}	6) $C_{8}^{5}$ C_8^{5}

Формула додавання: $C_{n}^{k} = C_{n - 1}^{k - 1} + C_{n - 1}^{k}$ C_n^{k} = C_{n-1}^{k-1} + C_{n-1}^{k}.

Доказ. Обчислимо значення правої частини рівняння:

C_{n - 1}^{k - 1} + C_{n - 1}^{k} = \frac{( n - 1 )!}{( k - 1 )! \cdot ( n - k )!} + \frac{( n - 1 )!}{k ! \cdot ( n - k - 1 )!} =

C_{n-1}^{k-1} + C_{n-1}^{k} = {(n - 1)! \over (k - 1)! \cdot (n - k)!} + {(n - 1)! \over k! \cdot (n - k - 1)!} =

\frac{( n - 1 )! \cdot k + ( n - 1 )! \cdot ( n - k )}{k ! \cdot ( n - k )!} = \frac{( n - 1 )! \cdot ( k + n - k )}{k ! \cdot ( n - k )!} = \frac{n !}{k ! \cdot ( n - k )!} = C_{n}^{k}

{(n - 1)! \cdot k + (n - 1)! \cdot (n - k) \over k! \cdot (n - k)!} = {(n - 1)! \cdot (k + n - k)\over k! \cdot (n - k)!} = {n! \over k! \cdot (n - k)!} = C_n^{k}

Eolymp #3260. Скільки?

Готуючись до іспиту з математичного аналізу, Петя розклав перед собою $n$ різних шпаргалок. Вони були його порятунком, адже за весь семестр Петя так жодного разу не спромігся вивчити матеріал як слід. Шпаргалок виявилося настільки багато, що вони не вміщалися в жодну кишеню. Тому Петя вирішив підрахувати максимальну кількість шпаргалок, яку він зможе взяти з собою на іспит. І тут виникло питання: а скільки взагалі існує способів вибрати потрібну кількість шпаргалок?

Вхідні дані. Містять загальну кількість шпаргалок $n (1 \leq n \leq 12)$ n~(1 \le n \le 12) і кількість шпаргалок $k (0 \leq k \leq n)$ k~(0 \le k \le n), яку Петя може взяти з собою.

Вихідні дані. Виведіть кількість способів вибрати $k$ шпаргалок з $n$ .

Відкрити задачу

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

int Cnk(int n, int k)
{
  int res = 1;
  for(int i = 1; i <= k; i++)
    res = res * (n - i + 1) / i;
  return res;
}

C++

Основна частина програми. Читаємо вхідні дані.

scanf("%d %d",&n,&k);

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

res = Cnk(n,k);
printf("%d\n",res);

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

int Cnk(int n, int k)
{
  if (n == k) return 1;
  if (k == 0) return 1;
  return Cnk(n - 1, k - 1) + Cnk(n - 1, k);
}

Основна частина програми. Читаємо вхідні дані.

scanf("%d %d",&n,&k);

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

res = Cnk(n,k);
printf("%d\n",res);

Eolymp #5329. Вечірка

Скількома способами серед $n$ ЛКШат можна вибрати $k$ таких, яким дістанеться кефір? Відповідь виведіть за модулем $9929$ .

Вхідні дані. Цілі числа $n$ і $k (0 \leq k \leq n \leq 500)$ k~(0 \le k \le n \le 500).

Вихідні дані. Виведіть шукану кількість способів за модулем $9929$ .

Відкрити задачу

Оголосимо константи і масив $c nk$ , для якого $c nk [n] [k] = C_{n}^{k} m o d 9929$ cnk[n][k] = C_n^{k}~mod~9929.

#define MAX 510
#define MOD 9929
int cnk[MAX][MAX];

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

int c(int n, int k)
{
  if (cnk[n][k] > 0) return cnk[n][k];
  if (n - k < k) return c(n,n-k);
  if (!k) return cnk[n][k] = 1;
  return cnk[n][k] = (c(n-1,k) + c(n-1,k-1)) % MOD;
}

C++

Основна частина програми. Ініціалізуємо масив $c nk$ нуля

ми. Читаємо вхідні дані.

memset(cnk,0,sizeof(cnk));
scanf("%d %d",&n,&k);

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

printf("%d\n",c(n,k));

Біноміальні коефіцієнти з'являються в біномі Ньютона:

(x + y)^{n} = k = 0 \sum n C_{n}^{k} x^{k} y^{n - k}

(x + y)^n = \sum_{k=0}^n C_n^{k}x^{k}y^{n-k}

Розглянемо приклади:

(x + y)^{2} = C_{2}^{0} x^{2} y^{0} + C_{2}^{1} x^{1} y^{1} + C_{2}^{2} x^{0} y^{2} = x^{2} + 2 x y + y^{2},

(x + y)^2 = C_2^{0}x^{2}y^{0} + C_2^{1}x^{1}y^{1} + C_2^{2}x^{0}y^{2} = x^2 + 2xy + y^2,

(x + y)^{3} = C_{3}^{0} x^{3} y^{0} + C_{3}^{1} x^{2} y^{1} + C_{3}^{2} x^{1} y^{2} + C_{3}^{3} x^{0} y^{3} = x^{3} + 3 x^{2} y + 3 x y^{2} + y^{3}

(x + y)^3 = C_3^{0}x^{3}y^{0} + C_3^{1}x^{2}y^{1} + C_3^{2}x^{1}y^{2} + C_3^{3}x^{0}y^{3} = x^3 + 3x^2y + 3xy^2 + y^3

Eolymp #9892. C0n + ... + Cnn

За заданим невід'ємним цілим числом $n$ знайдіть суму біноміальних коефіцієнтів

C_{n}^{0} + C_{n}^{1} + ... + C_{n}^{n}

C_n^{0} + C_n^{1} + ... + C_n^{n}

Вхідні дані. Одне невід'ємне ціле число $n (n \leq 60)$ n~(n \le 60).

Вихідні дані. Виведіть значення суми.

Відкрити задачу

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

За заданим невід'ємним цілим числом $n$ знайдіть суму біноміальних коефіцієнтів

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

(C_n^{0})^2 + (C_n^{1})^2 + (C_n^{2})^2 + ... + (C_n^{n})^2

Вхідні дані. Одне невід'ємне ціле число $n (n \leq 30)$ n~(n \le 30).

Вихідні дані. Виведіть значення суми.

Відкрити задачу

Функція 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);

Eolymp #11550. x1 + x2 + ... + xk = n

За заданими значеннями $k$ і $n$ знайдіть кількість натуральних розв'язків рівняння

x_{1} + x_{2} + ... + x_{k} = n

x_1 + x_2 + ... + x_k = n

Вхідні дані. Два натуральні числа $k$ і $n (k \leq n \leq 100)$ n~(k \le n \le 100).

Вихідні дані. Виведіть кількість натуральних розв'язків для заданого рівняння. Відомо, що відповідь не перевищує $1 0^{18}$ 10^{18}.

Відкрити задачу

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

long long Cnk(long long k, long long n)
{
  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++

Основна частина програми. Читаємо вхідні дані.

scanf("%lld %lld", &k, &n);

Обчислюємо і виводимо відповідь $C_{n - 1}^{k - 1}$ C_{n-1}^{k-1}.

res = Cnk(k - 1, n - 1);
printf("%lld\n", res);

Eolymp #11551. x1+...+xk = n (2)

За заданими значеннями $k$ і $n$ знайдіть кількість невід'ємних цілих розв'язків рівняння

x_{1} + x_{2} + ... + x_{k} = n

x_1 + x_2 + ... + x_k = n

Вхідні дані. Два натуральні числа $k$ і $n (k \leq n \leq 100)$ n~(k \le n \le 100).

Вихідні дані. Виведіть кількість невід'ємних цілих розв'язків для заданого рівняння. Відомо, що відповідь не перевищує $1 0^{18}$ 10^{18}.

Відкрити задачу

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

long long Cnk(long long k, long long n)
{
  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++

Основна частина програми. Читаємо вхідні дані.

scanf("%lld %lld", &k, &n);

Обчислюємо і виводимо відповідь $C_{n + k - 1}^{k - 1}$ C_{n+k-1}^{k-1}.

res = Cnk(k - 1, n + k - 1); 
printf("%lld\n", res);

Eolymp #318. Біноміальні коефіцієнти 1

Нехай $n$ — ціле невід'ємне число. Позначимо

n! = 1 \cdot 2 \cdot ... \cdot n (0! = 1),

n! = 1 \cdot 2 \cdot ... \cdot n~(0! = 1),

C_{n}^{k} = \frac{n !}{k ! \cdot ( n - k )!} (0 \leq k \leq n)

C_n^{k} = {n! \over k! \cdot (n - k)!} (0 \le k \le n)

Для заданих $n$ і $k$ обчисліть значення $C_{n}^{k}$ C_n^{ k}.

Вхідні дані. Перша строка містить кількість тестів $t (t \leq 50)$ t~(t \le 50). Кожна з наступних $t$ строк містить два цілих числа $n$ і $k (0 \leq n < 2^{64}, 0 \leq C_{n}^{k} < 2^{64})$ k~(0 \le n < 2^{64}, 0 \le C_n^{k} < 2^{64}).

Вихідні дані. Виведіть $t$ строк, кожна з яких містить значення $C_{n}^{k}$ C_n^{k} для відповідного тесту.

Відкрити задачу

Обчислення будемо проводити з використанням $64$ -розрядних беззнакових цілих чисел (unsigned long long). Очевидно, що

C_{n}^{k} = \frac{n !}{k ! \cdot ( n - k )!} = \frac{n \cdot ( n - 1 ) \cdot ( n - 2 ) \cdot ... \cdot ( n - k + 1 )}{1 \cdot 2 \cdot 3 \cdot ... \cdot k} = \frac{n}{1} \cdot \frac{n - 1}{2} \cdot \frac{n - 2}{3} \cdot ... \cdot \frac{n - k + 1}{k}

C_n^k = {n! \over k! \cdot (n - k)!} = {n \cdot (n - 1) \cdot (n - 2) \cdot ... \cdot (n - k + 1) \over 1 \cdot 2 \cdot 3 \cdot ... \cdot k} = {n \over 1} \cdot {n - 1 \over 2} \cdot {n - 2 \over 3} \cdot ... \cdot {n - k + 1 \over k}

Присвоїмо змінній $r es$ значення $1$ , після чого будемо її множити на $\frac{n - i + 1}{i}$ {n - i + 1 \over i} для всіх $i$ від $1$ до $k$ . Кожного разу ділення на $i$ буде цілочисельним, проте при множенні можна отримати переповнення. Нехай $d = НОД (r es, i)$ d = НОД(res, i). Тоді операцію

r es = r es * (n - i + 1) / i

res = res * (n – i + 1 ) / i

перепишемо через

r es = (r es / d) * ((n - i + 1) / (i / d))

res = (res / d) * ((n – i + 1 ) / (i / d))

При такій реалізації переповнення при множенні не відбудеться (відповідь є $64$ -розрядним беззнаковим цілим числом). Зазначимо, що спочатку слід виконати ділення $(n - i + 1) / (i / d)$ (n – i + 1 ) / (i / d), а потім множення $r es / d$ на отримане частке.

Для обчислення $C_{n}^{k}$ C_n^k слід виконати $k$ ітерацій. Але що робити, якщо слід обчислити $C_{2000000000}^{1999999999}$ C_{2000000000}^{1999999999}? Відповідь не перевищить $2^{64}$ 2^{64}, тому такі вхідні дані можливі. Оскільки $C_{n}^{k} = C_{n}^{n - k}$ C_n^k = C_n^{n - k}, то при $n - k < k$ n – k < k слід покласти $k = n - k$ k = n – k.

Приклад

Розглянемо наступний приклад:

C_{6}^{3} = \frac{6}{1} \cdot \frac{5}{2} \cdot \frac{4}{3} = 15 \cdot \frac{4}{3}

C_6^3 = {6 \over 1} \cdot {5 \over 2} \cdot {4 \over 3} = 15 \cdot {4 \over 3}

Нехай $r es = 15$ res = 15, і залишилось виконати множення $r es \cdot \frac{4}{3} = 15 * \frac{4}{3}$ res \cdot {4 \over 3} = 15 * {4 \over 3}. Обчислимо $d = НОД (15, 3) = 3$ d = НОД(15, 3) = 3. Тому $15 \cdot \frac{4}{3} = (15/3) \cdot \frac{4}{3/3} = 5 \cdot \frac{4}{1} = 20$ 15 \cdot {4 \over 3} = (15 / 3) \cdot {4 \over 3 / 3} = 5 \cdot {4 \over 1} = 20.

Функція gcd обчислює найбільший спільний дільник чисел $a$ і $b$ .

unsigned long long gcd(unsigned long long a, unsigned long long b)
{
  return (!b) ? a : gcd(b,a % b);
}

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

unsigned long long Cnk(unsigned long long n, unsigned long long k)
{
  unsigned long long CnkRes = 1, t, i;
  if (k > n - k) k = n - k;
  for(i = 1; i <= k; i++)
  {
    t = gcd(CnkRes, i);
    CnkRes = (CnkRes / t) * ((n - i + 1) / (i / t));
  }
  return CnkRes;
}

C++

Основна частина програми. Читаємо вхідні дані. Послідовно обробляємо тести.

scanf("%d",&t);
while(t--)
{
  scanf("%llu %llu",&n,&k);
  res = Cnk(n,k);
  printf("%llu\n",res);
}

C++

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

Дано натуральне число $n$ . Знайдіть значення наступної суми

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}

Вхідні дані. Одне натуральне число $n (n \leq 30)$ n\:(n \le 30).

Вихідні дані. Виведіть значення шуканої суми.

Відкрити задачу

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

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 \cd от (\frac{( n - 1 )!}{0 ! \cdot ( n - 1 )!} + \frac{( n - 1 )!}{1 ! \cdot ( n - 2 )!} + ... + \frac{( n - 1 )!}{( n - 1 )! \cdot ( n - n )!}) =

n \cd от \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);

Eolymp #10668. Шляхи на сітці

У вас є аркуш паперу, і ви обираєте на ньому прямокутник розміром $n \cdot m$ n \cdot m. Назвемо цей прямокутник разом з лініями, на яких він знаходиться, сіткою. Починаючи з лівого нижнього кута сітки, ви переміщаєте олівець до правого верхнього кута, стежачи за тим, щоб він залишався на лініях і рухався тільки вправо або вгору. Результат показаний зліва:

Дійсно шедевр, чи не так? Повторюючи процедуру ще раз, ви отримаєте зображення, показане праворуч. Тепер виникає питання: скільки різних витворів мистецтва можна таким чином створити?

Вхідні дані. Два натуральні числа $n$ і $m$ .

Вихідні дані. Виведіть кількість різних витворів мистецтва, які можна створити, використовуючи описану вище процедуру. Можна стверджувати, що це число відповідає $64$ — бітовому знаковому цілому числу.

Відкрити задачу

Функція 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++

Основна частина програми. Читаємо вхідні дані.

scanf("%lld %lld", &n, &m);

Обчислюємо і виводимо відповідь $C_{n + m}^{n}$ C_{n+m}^n.

res = Cnk(n + m, n);
printf("%lld\n", res);

Eolymp #4008. Біноміальні коефіцієнти

Гуннар — досить старий і забудькуватий дослідник. Зараз він пише статтю про безпеку в соціальних мережах, яка включає в себе деякі елементи комбінаторики. Він написав програму для обчислення біноміальних коефіцієнтів, щоб перевірити деякі розрахунки.

Біноміальний коефіцієнт $C_{n}^{k}$ C_n^{k} — це число

C_{n}^{k} = \frac{n !}{k ! \cdot ( n - k )!}

C_n^{k } = {n! \over k! \cdot (n - k)!}

де $n$ і $k$ — невід'ємні числа.

Гуннар використовує свою програму для обчислення $C_{n}^{k}$ C_n^{k} і отримав число $m$ як результат. На жаль, оскільки він забудькуватий, він забув числа $n$ і $k$ , які він використовував як вхідні дані. Ці два числа були результатом довгих обчислень, і вони були записані на одному з численних аркушів, що лежать на його столі. Замість того щоб шукати в паперах, він вирішив відновити числа $n$ і $k$ за отриманою відповіддю. Чи можете ви допомогти йому знайти всі такі можливі значення?

Вхідні дані. Перша строка містить кількість тестів, не більше $100$ . Кожен тест задається в одній строкі і містить ціле число $m (2 \leq m \leq 1 0^{15})$ m~(2 \le m \le 10^{15}) — результат програми Гуннара.

Вихідні дані. Для кожного тесту виведіть дві строки. Перша строка повинна містити кількість способів виразити $m$ за допомогою біноміального коефіцієнта. У другій строкі повинні розташовуватись всі пари $(n, k)$ , що задовольняють $C_{n}^{k} = m$ C_n^{k} = m. Пари слід розташувати за зростанням $n$ , а у випадку рівності за зростанням $k$ . Формат виводу пар наведено в прикладі.

Відкрити задачу

Шукані пари будемо зберігати у векторі пар $r es$ .

vector<pair<long long,long long> > res;

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

long long Cnk(long long n, long long k)
{
  long long i, Res = 1;
  if (k > n - k) k = n - k;
  for(i = 1; i <= k; i++)
  {

Якщо на черговій ітерації результат перевищує $m$ (ми шукаємо розв'язок рівняння $C_{n}^{k} = m$ C_n^k = m), то зупиняємось. Таким виходом з функції ми також уникнемо переповнення.

    if (1.0 * Res * (n - i + 1) / i > m) return m + 1;
    Res = Res * (n - i + 1) / i;
  }
  return Res;
}

Основна частина програми. Читаємо вхідні дані.

scanf("%d",&tests);
while (tests--) 
{
  res.clear();
  scanf("%lld",&m);

Перебираємо значення $k$ від $0$ до тих пір поки $C_{2 k}^{k} \leq m$ C_{2k}^k ≤ m.

  for(k = 0; Cnk(2*k,k) <= m; k++)
  {

Шукаємо значення $n (2 k \leq n \leq m)$ n~(2k \le n \le m) бінарним пошуком.

    long long lo = 2*k, hi = m;
    while (lo < hi) 
    {
      long long n = (lo + hi) / 2;
      if (Cnk(n,k) < m) lo = n + 1; else hi = n;
    }

Якщо $C_{l o}^{k} = m$ C_{lo}^k = m, то розв'язок знайдено. Заносимо в результат одну або дві пари розв'язків.

    if (Cnk(lo,k) == m)
    {
      res.push_back(make_pair(lo,k));
      if (lo != 2*k)
        res.push_back(make_pair(lo,lo - k));
    }
  }

C++

Сортуємо пари.

  sort(res.begin(),res.end());

Виводимо відповідь — кількість знайдених пар і самі пари.

  printf("%d\n",res.size());
  for(i = 0; i < res.size(); i++)
    printf("(%lld,%lld) ", res[i].first,res[i].second);
  printf("\n");
}

Асимптотичні оцінки для біноміального коефіцієнта

Теорема 1. Між біноміальними коефіцієнтами має місце співвідношення:

C_{n}^{0} < C_{n}^{1} < ... < C_{n}^{⌊ n /2 ⌋} \geq C_{n}^{⌊ n /2 ⌋ + 1} > ... > C_{n}^{n}

C_n^0 < C_n^1 < ... < C_n^{\lfloor n/2 \rfloor} \ge C_n^{\lfloor n/2 \rfloor + 1} > ... > C_n^n

Теорема 2. $C_{2 n}^{n} < 4^{n}$ C_{2n}^n < 4^n. Слід із того, що $\sum_{k = 0}^{2 n} C_{2 n}^{k} = (1 + 1)^{2 n} = 2^{2 n} = 4^{n}$ \sum_{k = 0}^{2n} C_{2n}^k = (1 + 1)^{2n} = 2^{2n} = 4^n

Теорема 3. $C_{2 n}^{n} > \frac{4 ^{n}}{2 n + 1}$ C_{2n}^n > {4^n \over 2n + 1}. Слід із того, що $\sum_{k = 0}^{2 n} C_{2 n}^{k} = 4^{n}$ \sum_{k = 0}^{2n} C_{2n}^k = 4^n, а самих коефіцієнтів $2 n + 1$ 2n + 1. Тому більший з коефіцієнтів буде більшим $\frac{4 ^{n}}{2 n + 1}$ {4^n \over 2n + 1}.

Теорема 4. Формула Стірлінга. $n! \approx 2 π n (\frac{n}{e})^{n}$ n! ≈ \sqrt{2 \pi n}\left({n \over e} \right) ^ n.

Більш точне наближення має вигляд:

n! \approx 2 π n (\frac{n}{e})^{n} (1 + \frac{1}{12 n} + \frac{1}{288 n ^{2}} - \frac{139}{51849 n ^{3}} - \frac{571}{2488320 n ^{4}})

n! ≈ \sqrt{2 \pi n} \left({n \over e} \right) ^ n \left( 1 + {1 \over 12n} + {1 \over 288n^2} - {139 \over 51849n^3} - {571 \over 2488320n^4} \right)

Теорема 5.

C_{2 n}^{n} \approx \frac{4 π n ( \frac{2 n}{e} ) ^{2 n}}{( 2 π n ( \frac{n}{e} ) ^{n} ) ^{2}} = \frac{4 ^{n}}{пі n}

C_{2n}^n ≈ {\sqrt{4 \pi n}\left({2n \over e} \right) ^ {2n} \over \left( \sqrt{2 \pi n}\left({n \over e} \right) ^ n \right) ^2} = {4^n \over \sqrt{пі n}}

Теорема 6.

C_{n}^{k} = \frac{n !}{k ! ( n - k )!} = \frac{n \cdot ( n - 1 ) \cdot ( n - 2 ) \cdot ... \cdot ( n - k + 1 )}{1 \cdot 2 \cdot 3 \cdot ... \cdot k} =

C_n^k = {n! \over k!(n - k)!} = { n \cdot (n - 1) \cdot (n - 2) \cdot ... \cdot (n - k + 1) \over 1 \cdot 2 \cdot 3 \cdot ... \cdot k} =

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

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

\frac{n !}{k !} \cdot e^{l n (1 - \frac{1}{n}) + l n (1 - \frac{2}{n}) + ... + l n (1 - \frac{k - 1}{n})} \leq (скористаємося нерівністю l n (1 - x) \leq - x)

{n! \over k!} \cdot e ^{ln \left( 1 - {1 \over n} \right) + ln \left( 1 - {2 \over n} \right) + ... + ln \left( 1 - {k - 1 \over n} \right)} \le (скористаємося~нерівністю~ln(1 - x) \le -x)

\frac{n !}{k !} \cdot e^{- \frac{1}{n} - \frac{2}{n} - ... - \frac{k - 1}{n}} = \frac{n !}{k !} \cdot e^{- \frac{k \cdot ( k - 1 )}{2 n}}

{n! \over k!} \cdot e ^{-{1 \over n} - {2 \over n} - ... - {k - 1 \over n}} = {n! \over k!} \cdot e^{-{k \cdot (k - 1) \over 2n}}

Біноміальний коефіцієнт

Асимптотичні оцінки для біноміального коефіцієнта

Список використаних задач

Коментарі