11271. Сумма квадратов Cnk

 

По заданному неотрицательному целому числу n найдите сумму биномиальных коэффициентов

 

Вход. Одно неотрицательное целое число n (n ≤ 60).

 

Выход. Выведите значение суммы.

 

Пример входа

Пример выхода

3

20

 

 

РЕШЕНИЕ

комбинаторика

 

Анализ алгоритма

Рассмотрим 2n объектов a1, …, a2n и найдем количество способов выбрать n объектов из 2n.

Разобьём множество на две части: {a1, a2, …, an, an+1, …, a2n}. Чтобы выбрать n объектов из 2n, нам нужно выбрать k (k ≤ n) объектов из левой половины (то есть из множества {a1, a2, …, an }) и n – k объектов из правой (из множества {an+1, an+2, …, a2n }). Количество способов сделать такую выборку в соответствии с правилом умножения равно  = . Поскольку k может принимать значения от 0 до n, то  равно количеству способов выбрать n объектов из 2n, то есть . Таким образом

 =

 

Пример

Для n = 3 ответ равен  = 12 + 32 + 32 + 12 = 20.

В то же время  =  =  = 20.

 

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

Функция Cnk вычисляет значение биномиального коэффициента .

 

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;

}

 

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

 

scanf("%lld", &n);

 

Вычисляем и выводим ответ.

 

res = Cnk(2*n, n);

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

 

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();

  }

}

 

Python реализация

Функция Cnk вычисляет значение биномиального коэффициента .

 

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

 

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

 

n = int(input())

 

Вычисляем и выводим ответ.

 

res = Cnk(2 * n, n)

print(res)

 

Python реализация – comb

Читаем входное значение n.

 

n = int(input())

 

Вычисляем и выводим ответ.

 

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

print(res)