The idea is to fix an element x in the set. If x is included in the subset, we have to choose k − 1 elements from n − 1 elements, or if x is not included in the subset, we have to choose k elements from n − 1 elements
There are two independent paths here, so we perform Rule of Sum
Since there is recursion involved, there is base case to terminate the recursion too. The base cases are (0n)=(nn)=1. Because there is always exactly one way to construct an empty subset and a subset that contains all the elements
Below is an implementation of formula 1 in Java
Is the code editor above not showing the correct source code?
Here is a backup, please report the issue here or comment down below, so I can look into the issue. Thanks :)
class Binom { public static void main(String[] args) { long startTime = System.currentTimeMillis(); long res = binom(50,6); long endTime = System.currentTimeMillis(); long elapsedTime = endTime - startTime; System.out.println("Elapsed time: " + elapsedTime + " milliseconds"); System.out.println(res); } public static int binom(int n, int k) { if (n == k) return 1; // C(n,n) if (k == 0) return 1; // C(n,0) return binom(n-1, k) + binom(n-1, k-1); }}
Exponential Time Complexity
For (1020), formula 1 takes a few ms, while Formula 2 only takes 0ms
Likely to have timeout error
No Overflow Issue
As long as the given n and the result are within the range of long, we will not face any overflow issue
Formula 2
(kn)=k!(n−k)!n!
n! calculates the Permutation of n-element where the order matters, so we will have more than one counting which has the same set of elements but different order. However Combination doesn’t care about the order. Thus, n! will overcount. To counter this, we introduce the Divisork! and (n−k)! to avoid overcounting and only count the combination we want
(n−k)!n! means how many ways to choose k elements from n element where the order matters
k!(n−k)!n! removes the counting that has the same set of elements
Below is an implementation of formula 2 in Java
Is the code editor above not showing the correct source code?
Here is a backup, please report the issue here or comment down below, so I can look into the issue. Thanks :)
class Binom { public static void main(String[] args) { long startTime = System.currentTimeMillis(); long res = binom(20,10); long endTime = System.currentTimeMillis(); long elapsedTime = endTime - startTime; System.out.println("Elapsed time: " + elapsedTime + " milliseconds"); System.out.println(res); } public static long binom(int n, int k) { long permutation = calFactorial(n) / calFactorial(n-k); long combination = permutation / calFactorial(k); return combination; } public static long calFactorial(long x) { long res = 1; for (int i=1; i<=x; i++) { if (Long.MAX_VALUE / i < res) { throw new ArithmeticException("Overflow during factorial calculation"); } res *= i; } return res; }}
Linear Time Complexity
For (1020), Formula 1 takes a few ms, while Formula 2 only takes 0ms
Overflow Issue
Try change the n from 20 to 21 in the editor above, you should get an overflow error. Because 21! is out of the range the long can cover
Overall probability for a specific outcome in a number of independent attempts, each attempt is either a success or failure and each has the same probability of success
P(k)=(kn)pk(1−p)n−k
P(k) calculates the overall probability for a specific outcome
k is the number of successes in the specific outcome
n is the number of independent attempt
p is the probability of success in each attempt, pk is the probability of having k successes
(kn) is the Binomial Coefficient that calculates the total number of Combination of a certain composition of success and failures, the specific outcome refers to this particular composition of success and failures
pk(1−p)n−k is the probability of having one such specific outcome