MCHAIRS - Editorial

combinatorics
editorial
mchairs
nov13
simple

#1

PROBLEM LINK:

Practice
Contest

DIFFICULTY:

SIMPLE

PREREQUISITES:

Combination, Sum of Binomial Coefficients

PROBLEM:

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


#2

Σ(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.

Can someone explain that to me…


#3

Hi thanks for the solution.

Would you say that this is the best (fastest) way to find out a^b? If not, then which is and why did you prefer this method?


#4

Hi,

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.

Regards,
Vijay


#5

it is the definition of Combination
nCr = number of ways of selecting r objects from n objects

permutation is the arrangement


#6

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.


#7

“Σ(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.”

Can someone explain that to me…


#8

It basically says:

nC0 + nC1 + nC2 + … (all the way up to)…+ nC(n-1) + nCn = 2^n.

You can read this for the explanation:
http://mathforum.org/library/drmath/view/56597.html


#9

@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.


#10

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?