How Many?#3260

How Many? (Editorial)

To compute the binomial coefficient, you can use the following formula:

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}

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}

Declare a variable $r es$ and initialize it with a value of $1$ . Then multiply $r es$ by $n$ and divide the result by $1$ . After that multiply $r es$ by $n -1$ and divide by $2$ . Continue this process of multiplication and division $k$ times (the numerator and denominator of $C_{n}^{k}$ C_n^{k} after simplification by $(n - k)!$ contain $k$ factors).

For the recursive implementation of the binomial coefficient, use the following formula:

C_{n}^{k} = {C_{n - 1}^{k - 1} + C_{n - 1}^{k}, n > 0 1, k = n или k = 0

C_n^{k} = \begin{cases} C_{n - 1}^{k - 1} + C_{n - 1}^{k}, n > 0 \\ 1, k = n~или~k = 0 \end{cases}

Algorithm implementation

The Cnk function returns the binomial coefficient using an iterative method.

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

The main part of the program. Read the input data.

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

Compute and print the answer.

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

Algorithm implementation — recursion

The Cnk function returns the binomial coefficient using a recursive method.

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

The main part of the program. Read the input data.

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

Compute and print the answer.

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

Algorithm implementation — recursion with memorization

Declare a $d p$ array to store the values of the binomial coefficient: $d p [n] [k] = C_{n}^{k}$ dp[n][k] = C_n^{k}.

int dp[35][35];

The Cnk function returns the binomial coefficient using a recursive method. Memoization technique is used.

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

C++

The main part of the program. Read the input data.

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

Initialize the $d p$ array.

memset(dp,-1,sizeof(dp));

Compute and print the answer.

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

Java implementation — recursion

import java.util.*;

public class Main
{
  static 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);
  }

  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    int k = con.nextInt();
    
    int res = Cnk(n,k);
    System.out.println(res);
    con.close();
  }
}

Java

Java implementation — recursion with memorization

import java.util.*;

public class Main
{
  static int dp[][];
  
  static 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);
  }

  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    int k = con.nextInt();
    dp = new int[n+1][k+1];
    for(int i = 0; i <= n; i++)
      Arrays.fill(dp[i],-1);
    
    int res = Cnk(n,k);
    System.out.println(res);
    con.close();
  }
}

Java

Python implementation — comb

To compute the binomial coefficient, we shall use the built-in function $co mb (n, k) = C_{n}^{k}$ comb(n, k) = C_n^{k}.

import math;

Read the input data.

n, k = map(int, input().split())

Compute and print the answer.

res = math.comb(n, k)
print(res)

Python implementation — factorial

The $f a c t (x)$ fact(x) function computes the factorial of the number $x$ .

def fact(x):
  if x:
    return fact(x - 1) * x
  else:
    return 1

The main part of the program. Read the input data.

n, k = map(int, input().split())

Compute and print the answer.

res = fact(n) // (fact(k) * fact(n - k))
print(res)

Python implementation — recursion with memorization

The Cnk function returns the binomial coefficient using a recursive method. Memoization technique is used.

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]

The main part of the program. Read the input data.

n, k = map(int, input().split())

Declare a $d p$ list to store the values of the binomial coefficient: $d p [n] [k] = C_{n}^{k}$ dp[n][k] = C_n^{k}.

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

Compute and print the answer.

res = Cnk(n, k, dp)
print(res)