Skip to content

# Khan/khan-exercises

Fetching contributors…
Cannot retrieve contributors at this time
121 lines (118 sloc) 8.67 KB
 Combinations 1
randFromArray(["shirts", "tigers", "books", "Fabergé eggs", "socks", "action figures"]) randRange(5,9) randRange(3,5) factorial(NUM_THINGS) / (factorial(NUM_THINGS-NUM_TAKEN) * factorial(NUM_TAKEN))

person(1) is packing his(1) bags for his(1) vacation. He(1) has NUM_THINGS unique THING, but only NUM_TAKEN fit in his(1) bag.

How many different groups of NUM_TAKEN THING can he(1) take?

ANSWER

person(1) has NUM_TAKEN spaces for his(1) THING, so let's fill them one by one. At first, person(1) has NUM_THINGS choices for what to put in the first space.

For the second space, he(1) only has NUM_THINGS-1 THING left, so there are only NUM_THINGS-1 choices of what to put in the second space. So far, it seems like there are NUM_THINGS \cdot NUM_THINGS-1 = NUM_THINGS * (NUM_THINGS-1) different unique choices person(1) could have made to fill the first two spaces in his(1) bag. But that's not quite right.

Why? Because if he(1) picked THING.substring(0,THING.length-1) number 3, then THING.substring(0,THING.length-1) number 1, that's the same situation as picking number 1 and then number 3. They both end up in the same bag.

So, if person(1) keeps filling the spaces in his(1) bag, making _.map(_.range(NUM_TAKEN), function(l){ return (NUM_THINGS - l);}).join("\\cdot") = \dfrac{NUM_THINGS!}{(NUM_THINGS-NUM_TAKEN)!} = factorial(NUM_THINGS)/factorial(NUM_THINGS-NUM_TAKEN) decisions altogether, we've overcounted a bunch of groups.

How much have we overcounted? Well, for every group of NUM_TAKEN, we've counted them as if the order we chose them in matters, when really it doesn't. So, the number of times we've overcounted each group is the number of ways to order NUM_TAKEN things.

There are NUM_TAKEN! = factorial(NUM_TAKEN) ways of ordering NUM_TAKEN things, so we've counted each group of NUM_TAKEN THING factorial(NUM_TAKEN) times.

So, we have to divide the number of ways we could have filled the bag in order by number of times we've overcounted our groups.

\dfrac{NUM_THINGS!}{(NUM_THINGS - NUM_TAKEN)!} \cdot \dfrac{1}{NUM_TAKEN!} is the number of groups of THING person(1) can bring.
Another way to write this is \binom{NUM_THINGS}{NUM_TAKEN} , or NUM_THINGS choose NUM_TAKEN, which is ANSWER.

randRange(5,6) randRange(2,FRIENDS-2) factorial(FRIENDS) / (factorial(FRIENDS-SLOTS) * factorial(SLOTS))

You just got a free ticket for a boat ride, and you can bring along SLOTS friends! Unfortunately, you have FRIENDS friends who want to come along.

How many different groups of friends could you take with you?

ANSWER

There are SLOTS places for your friends on the boat, so let's fill those slots one by one. For the first slot, we have FRIENDS different choices we can make (because FRIENDS different friends could be in that slot).

Once we've filled the first slot, there are FRIENDS-1 friends who could fill the second. So far, if we've filled the first two slots, and it seems like there are FRIENDS \cdot FRIENDS-1 = FRIENDS * ( FRIENDS-1) different choices we could have made. But that's not quite true.

Why? Because if we picked person(1), then person(2), that's the same thing as picking person(2), then person(1). They both get to be on the same boat.

So, if we continue filling the slots on our boat, making _.map(_.range(SLOTS), function(l){ return (FRIENDS - l);}).join("\\cdot") = \dfrac{FRIENDS!}{FRIENDS-SLOTS!} = factorial(FRIENDS)/factorial(FRIENDS-SLOTS) decisions altogether, we've overcounted a bunch of groups.

How much have we overcounted? Well, for every group of SLOTS, we've counted them as if the order we chose them in matters, when really it doesn't. So, the number of times we've overcounted each group is the number of ways to order SLOTS things.

There are SLOTS! = factorial(SLOTS) ways of ordering SLOTS things, so we've counted each group of SLOTS friends factorial(SLOTS) times.

So, we have to divide the number of ways we could have filled the boat in order by number of times we've overcounted our groups:
\dfrac{FRIENDS!}{FRIENDS-SLOTS!} \cdot \dfrac{1}{SLOTS!} is the number of groups we can bring on the boat trip.
Another way to write this is \binom{FRIENDS}{SLOTS} , or FRIENDS choose SLOTS, which is ANSWER.

Something went wrong with that request. Please try again.