11271. Sum of squares Cnk

Given a non-negative integer n, find the sum of binomial coefficients

Input. One non-negative integer n (n ≤ 60).

Output. Print the value of the sum.

Sample input	Sample output
3	20

SOLUTION

combinatorics

Algorithm analysis

Let us consider 2n objects a₁, …, a_2n and find the number of ways to choose n objects from these 2n.

Divide the set into two parts of n objects each:

{a₁, a₂, …, a_n} and {a_n+1, …, a_2n}

To choose n objects from the 2n, we can select k (k ≤ n) objects from the left half and n – k objects from the right half.

According to the multiplication principle, the number of ways to make such a selection is

=

Since k can take all values from 0 to n, the sum of all possibilities is

,

which equals the number of ways to choose n objects from 2n, that is . Thus, we obtain the formula:

=

Example

For n = 3 the answer is = 1² + 3² + 3² + 1² = 20.

At the same time = = = 20.

Algorithm implementation

The Cnk function computes the value of the binomial coefficient .

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;

}

The main part of the program. Read the value of n.

scanf("%lld", &n);

Compute and print the answer.

res = Cnk(2*n, n);

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

Java implementation

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 implementation

The function Cnk computes the value of the binomial coefficient .

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

The main part of the program. Read the value of n.

n = int(input())

Compute and print the answer.

res = Cnk(2 * n, n)

print(res)

Python implementation – comb

Read the value of n.

n = int(input())

Compute and print the answer.

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

print(res)