For a given value N, Find the sum of all Combination(N,k) where k varies from 1 to N
QUICK EXPLANATION:
Σ(Combination(N,k)) for 0 <= k <= N is the sum of binomial coefficients in the expansion of (1+x)^N which is equal to 2^N
EXPLANATION:
When there are k chairs in the classroom, we can select k students out of N to sit on them. Number of ways of selecting k students from N is given by Combination(N,k). As number of chairs vary from 1 to N, our task is to find: Σ(Combination(N,k)) for 1 <= k <= N.
Σ(Combination(N,k)) for 0 <= k <= N is the sum of binomial coefficients in the expansion of (1+x)^N which is equal to 2^N. In our current problem, number of chairs varies from 1 to N so we should remove the case when no chair is present in the class. Hence all we have to calculate is 2^N - 1
We can use Right-to-left binary method for modular exponentiation to calculate (2^N % MOD) in log N time. Since N is not very large it is also possible to pre-calculate all values of 2^N.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here
Tester’s solution can be found here and here
I am not clear on whether it is combination or permutation. Could someone explain why selecting k students out of n is combination and not permutation.
Perhaps the question was worded in a way that could have confused you; the story about the chairs makes you think you are dealing with arranging the people on the chairs, but really you are choosing people to sit on the chairs, thus it is a combination not a permutation. Many problems have descriptions which are either intentionally or unintentionally confusing and thus you must always read the problem statement at least thrice before attempting the problem.
@thespacedude do you mean nC0 + nC1 + nC2 + … (all the way up to)…+ nC(n-1) + nCn is the fastest way? Actually you are expected to directly calculate the this value of 2^n using fast exponentiation which is done in log(N) time.
Firstly, apologies for responding so late!
Yes, I get that we are supposed to compute 2^n. But is using “fast exponentiation” to find 2^n the best way? Or is it like, problem dependent?