Answers>Maths>IB>Article

When do you use 'n choose k' and where does the formula come from?

When do you use n choose k?

Say you have n objects/elements, and each one can either be selected or not selected. ‘n choose k’ gives you the number of different ways in which you can end up with k selected objects. So for example, if you have a deck of n different cards and you select k of them to take into your hand, the number of distinct hands you could end up with is n choose k. Note that the order of the cards in the hand doesn't matter - only the combination of cards distinguishes one hand from another. 

How do you get the formula?

When picking your hand out of the deck of n cards, the first card you pick could have n different values. The second one could have n - 1 values since there is now a card missing from the deck, so the total number of possible combinations for the first two cards is n x (n - 1). Continuing in this way until you have picked k cards, there will be n x (n - 1) x … x (n - k + 1) combinations for the hand, which is written as n!/(n - k)! (it’s like n factorial but with all the terms from n - k downwards cancelled out by the denominator).

But wait! By counting in this way, we have counted hands of the same cards picked in a different order as distinct combinations. To adjust for this, we need to divide our result by however many differently-ordered arrangements there are of each hand. We count in a similar way as before: for a hand of k cards, we could put any of the k cards in the first slot, and then any of the k - 1 remaining ones in the second slot, and so on… so there are k! arrangements. Hence, our final answer is n! / [(n - k)! x k!] (looks much simpler when properly written out…).

Answered by Tom B. Maths tutor

12004 Views

See similar Maths IB tutors

Related Maths IB answers

All answers ▸

What does a derivative mean and why does setting it equal to zero allow us to find the minima/maxima of a function


Prove by mathematical induction that (2C2)+(3C2)+(4C2)+...+(n-1C2) = (nC3).


The function f has a local extreme at point (1,4). If f''(x)=3x^2+2x, then find f(0)?


Three girls and four boys are seated randomly on a straight bench. Find the probability that the girls sit together and the boys sit together.


We're here to help

contact us iconContact usWhatsapp logoMessage us on Whatsapptelephone icon+44 (0) 203 773 6020
Facebook logoInstagram logoLinkedIn logo

© MyTutorWeb Ltd 2013–2024

Terms & Conditions|Privacy Policy