Help me do some math?

February 12, 2015 8:25 AM

Help me do some math?

I have four buckets. I need to fill each bucket with a certain number of widgets (no more, no less) from a pile. How many possible variations exist?

BUCKET ONE:
- Holds 4 widgets.
- There are 4 widgets to choose from.

BUCKET TWO:
- Holds 3 widgets.
- There are 7 widgets to choose from.

BUCKET THREE:
- Holds 4 widgets.
- There are 13 widgets to choose from.

BUCKET FOUR:
- Holds 2 widgets.
- There are 10 widgets to choose from.

I'm sure I learned how to do this in school, but that knowledge has long since left my brain. If you could show me how you do the calculation in addition to giving the answer, I'd appreciate it!

posted by NotMyselfRightNow to Grab Bag (6 answers total)

I'm assuming from the fact you say "bucket" that there's no concept of ordering the items in the bucket.
First one is clearly just 1 - you take the 4 widgets and put them in the bucket.
Second one. You can choose the first widget 7 different ways, second one 6 ways, third one 5 ways. That gives you 7x6x5, but that's assuming there's an order. To get rid of that you have to divide by the number of ways you can order 3 things - ie 3x2x1. So the answer is 7!/(4!x3!).
The rest are similar, and if you need the total combinations for all buckets, just multiply all the answers together.
posted by crocomancer at 8:31 AM on February 12, 2015

Or if you're REALLY lazy, Googling "X choose Y" where X is the number of widgets and Y is how many widgets a bucket holds will give you the answer in each case.
posted by Behemoth at 8:32 AM on February 12, 2015 [2 favorites]

You're looking at some n choose k problems.

4 choose 4 = 1
7 choose 3 = 7! / 3!(7-3)! = 35
13 choose 4 = 13! / 4!(13-4)!= 315
10 choose 2 = 10! / 2!(10-2)!= 45

Then you just multiply them together.
1*35*315*45 = 23,625

So you've got 23,625 different possible variations.
posted by mrgoat at 8:41 AM on February 12, 2015

BUCKET ONE:
- Holds 4 widgets.
- There are 4 widgets to choose from.


Question for you: Can you choose the same widget more than once? For example, if each widget can only be chosen once, there's obviously only one way to fill Bucket One. But are you assuming that the same widget can be chosen multiple ways? The answers above are assuming that you can use the same widget only once in a particular bucket.
posted by peacheater at 9:26 AM on February 12, 2015 [1 favorite]

The derivation of these formulas is pretty straightforward. Actually sitting down with a bunch of pool balls (nicely numbered) and a bucket will help you work it through.

Bucket one: four widgets to choose, four to choose from. There's clearly only one way to do that: all the widgets go in the bucket.

Bucket two: three widgets to choose, seven to choose from: an actual problem.

Select one of the seven widgets and toss it in the bucket: seven ways to do that, and after doing any of those you have six widgets left to choose from.

Select one of those six and toss it in the bucket. Six ways to do that for each of the seven widgets that could have been your first choice; so there are 7 × 6 = 42 orders in which the first two widgets could have been tossed into the bucket. After doing any of those you have five widgets left to choose from.

Select one of those five and toss it in the bucket. Five ways to do that for each of the 7 × 6 = 42 orders in which you could have made your first two choices; so there are 7 × 6 × 5 = 210 orders in which the three widgets could have been tossed into the bucket.

Now comes the slightly subtle part.

Applying the same reasoning to bucket 1 as has just been done for bucket 2 would end up with a result of 4 × 3 × 2 × 1 = 24 orders in which those four widgets could have been tossed into the bucket. But it's completely clear that if you have four widgets to choose from, and your job is to put them all into the bucket, then all 24 of those ways achieve the same single end result: we don't actually care about the order in which they arrive in the bucket, only that they do so.

The way to express that lack of concern is to divide the number of orders in which we can select our widgets by the number of possible orders into which they can be rearranged once chosen.

The process of rearranging widgets consists of selecting one to put first, then one of the remaining widgets to put second, then one of the remaining widgets to put third, and so on until we've arranged all of them. In fact it's the very same process as choosing some widgets to put in a bucket, except that instead of stopping when you've got enough, you don't stop until there are none left to arrange.

So four widgets, such as will end up in bucket 1, can be arranged in 4 × 3 × 2 × 1 = 24 ways. And this is why there's only one way to choose four out of four widgets: there are 4 × 3 × 2 × 1 = 24 orders in which to do the initial choice of widgets, divided by 4 × 3 × 2 × 1 = 24 possible orders to rearrange them into once chosen. End result: 1.

Three widgets, such as will end up in bucket 2, can be arranged in 3 × 2 × 1 = 6 ways. There are 7 × 6 × 5 = 210 orders in which to do the choice of widgets; divide that by the number of possible ways the chosen widgets can be rearranged and you get 210 ÷ 6 = 35 possible bucketloads of three, given seven to choose from.

The mathematical shorthand for a pattern like 4 × 3 × 2 × 1 is 4! (pronounced "four factorial").

A long-winded way of working out 7 × 6 × 5 would be to work out 7 × 6 × 5 × 4 × 3 × 2 × 1, then divide the 4 × 3 × 2 × 1 back out again: in shorthand, 7! ÷ 4!

Most calculators have a ! button, which means that this long-winded way usually ends up saving keystrokes.

The 3 × 2 × 1 = 6 is just 3!

So another way to write (7 × 6 × 5) ÷ (3 × 2 × 1) is (7! ÷ 4!) ÷ 3!

Which is the same thing as 7! ÷ (4! × 3!)

Which is the same thing as 7! ÷ [(7-3)! × 3!], and this is the shape of the general pattern for bucketing widgets from piles.

So there are 13! ÷ [(13-4)! × 4!] ways to bucket four widgets from a pile of thirteen, and 10! ÷ [(10-2)! × 2!] ways to bucket two widgets from a pile of ten.
posted by flabdablet at 9:41 AM on February 12, 2015 [2 favorites]

There's a different process for doing the same job that leads to the same result:

I want to choose three of seven widgets, and to make absolutely sure I've covered every possible way to do that, I'll work as follows:

1. Label all the widgets, from A through G, so I can represent them with letters on paper.

2. Make a huge list of all the possible orders in which the letters A through G can be arranged. This list will have 7! entries, because there are (as described earlier) 7 × 6 × 5 × 4 × 3 × 2 × 1 different ways to order 7 distinguishable objects.

3. Draw a long vertical line between the third and fourth columns of that list, representing the wall of the bucket; every letter to the left of the line will then represent a widget in the bucket, and every letter to the right is a widget out of it.

4. Group together all the list entries that have the same letters to the left of the line regardless of ordering, reflecting the fact that I don't care about the order of the widgets inside the bucket. Each such group must have 3! entries, because there are 3 letters to the left of the line and there are 3! orderings of three distinct letters.

Replace each group of 3! with a single item, to make a cut-down list with 7! ÷ 3! entries.

5. Group together all the entries in the resulting list that have all letters to the right of the line in common, reflecting the fact that I don't care about the order of widgets left behind in the pile. Each such group must have (7-3)! members, because if there are 3 letters to the left of the line then there are (7-3) letters to its right and there are (7-3)! orderings of (7-3) distinct letters.

Replace each group of (7-3)! with a single item, to make a cut-down list with (7! ÷ 3!) ÷ (7-3)! entries, which is the same thing as 7! ÷ [(7-3)! × 3!] entries, and that's an exhaustive list of the ways to choose 3 items from 7.
posted by flabdablet at 5:56 AM on February 13, 2015