[Home]Vitenka/CombinatoricsForDummies

www.vitenka.com | ToothyWiki | Vitenka | RecentChanges | Login | Webcomic

How do I find out how many ways there are of choosing, combining, permuting or shuffling?



Short answer: See the buttons marked nCm / nPm (or similar)?  Those are exactly what you want.

Formulae



The formula for nCm is... you know, instead of dredging my local memory, why not use my global expanded memory.  Google says:

nPm = n! / (n-m)!
nCm = n! / (m!)(n-m)!

Names



Quick definitions for you.
n! is 'n factorial' = 1 * 2 * 3 * 4 * ... * n-2 * n-1 * n

nPm means 'n Permute m'.  Permutations is just a fancy word for 'orderings'.  13245 45213 (and many more) are all permutations of 12345.  But a little more interestingly - they are ALSO permutations of 123456789.  Given n things, choose m of them and see what order they came out in.

nCm means 'n combine m' - but is often said 'n Choose m' - because it means just that.  Given n things, choose m of them.  How many different results are there of doing that?

Sigma means 'sum of'  Sigma x means 'sum of all the different x's'.

And, would you believe it, 'Bag' is a valid mathematical term - and I've even used it mostly correctly.  (Not so many mathematicians put kittens into their bags, though.)

Names with Cats


You've got some cats (n) and some boxes (m).

To permute (nPm) we put the boxes in a row.  Then we leave the room and let the cats get their thing on.  Each box ends up filled with a cat, and the remaining cats sulk and leave the room.

Now we look at the boxes and say "Oh hi fred, carol, sillykit" (or whatever) look at that - three cats in a particular order.  That'll look good in the family photo.
But there's lots of orders.  And maybe blackie could have been in a box?  - nPm is the number of different orders you (or the cats) can make.

To nCm ('consider' is, perhaps, a better word than combine) do that same thing.
You put out n cats and m boxes.  You leave the room.  Some cats get into boxes.  Some cats leave.
Except instead of looking at the cats in a row - close your eyes and empty them out into a big CatPile?.
Then just look at which cats you've got.  You can't possibly work out what order they're in - they're in a big squirming CatPile?.  But you can tell whether or not blacky is in it.

Count how many different catpiles you can make - that's nCm.

Trivial values and Disclaimer


nCn is, obviously, 1.  I've got n things and I need to choose n of them - uh, that's all of them.  So there's none left over.  I can't possibly put one back and choose a different one.  There's only one way to choose everything - and thta's to choose everything.

In the examples below I'm generalising and not doing evil things with the numbers.  For example, we could see what happens if m>n.  I've got five cats and have to choose (or permute) eight?  I can't do that!  It's unpossible.  So the value for that is zero.  Nill.  Non.  As many points as france usually gives in the eurovision song contest.

Don't even think about using non integer values.  Or values less than zero.  Making partial kittens is cruel.  Having no kittens is sad, but having less than that is too sad to consider.

Maths exists for this sort of thing.  I'm not touching it with a BargePole?.  Not even a TenFootPole? made of kittens.

Now for the maths tutorial.



Think of it this way.

You have a bunch of cats (n of them, handily) and a bunch of boxes to put them in (m of those).  Imagine yourself far smarter than you really are - you're schroedinger and about to perform that famous quantum thought experiment.
Note that each box holds exactly one cat!  So Schroedinger didn't need to do his experiment after all.
All the boxes start off empty.  Then you put cats in any which way.  Then you look to see which way they were in - and count how many ways you could have done it.

nPn



The problem is much easier if n and m are the same number. 
In this case, you look at your first box.  Pick a cat.  There are n of them, so there are n ways to do that.

Now, whichever cat you chose, handily, there are the same number of cats left.  n-1.
So you choose a new cat from those (you don't mind WHICH those they are, right now, you just want a cat - all that matters is how many there are)  Obviously, there are n-1 ways of doing this.
You know that none of the ways you choose are going to give the same result - because you chose a different cat in box 1.

So, great!  You've got N * (N-1) ways of choosing two cats.

And so on - to choose n cats out of n cats, you've got N * (N-1) * (N-2) * ... * 3 * 2 * 1 ways.

Which is more easily written: N!

nPm  n>m



Ok.  Now for the slightly tricker one.  We're going to do exactly the same thing - but this time with not enough boxes.  Some lucky cats get to go free.  We'll use them in the next experiment, so don't feel too nicely for them just yet.

So - let's do exactly the same thing.
N ways first box.  N-1 ways second box.  N-2 ways third box...
And so on.
But at some point, we run out of boxes.

The total number of ways is:
N * (N-1) * (N-2) * ... * 1+diff

We get that far... and then we WOULD go:
N * (N-1) * (N-2) * ... * 1+diff * diff * (diff-1) * ... * 3 * 2 * 1
- but we can't we ran out of boxes.

Ok.  Now, we know n is greater than m.  We wrote it in the title.  But how MUCH greater is it?  A little bit, or 'king of all cosmos' sized?  Let's call the difference 'n-m' in a fit of mathematical convention.

Now - aint cancelling fractions great?
Write down the expansion of N!.
Divide it by the expansion of (N-M)!.
Aint that lucky - the result is exactly the 'total number of ways' expansion written above.

And we're spent.

nCm



Ok. Now for combination.  Suddenly, we dn't care about order any more.
After we've boxed the cats we're going to sort the boxes in volume of purr or something.
If we put tabby calico and blacky in, or if we put calico then tabby then blacky in - or whatever, we'll still get the same cats out again.

So, obviously, nCm <= nPm

But how much less?  Well, that's easy.
You've got m boxes.  How many ways of arranging m boxes are there?  mPm = m!

Every single one of these ways yields the same result of cats, after we sort them.  So for every m! box orders in the permutation, there is only one combination.

So: nCm = nPm / m!


Bags



Right.  Ok, that's the basic stuff understood.

So now you wanted something slightly more complicated.

You've got a bag of starting cats - n different ones, but with multiples of each.

Call this bag X.  I'm going to say that there are xi of each cat.
So if you had, say, two tabbies, four schitzus (tell me they're not cats in thin disguises) and a calico we'd write that:
x1 = 2.  x2 = 4.  x3 = 1.
The total number of cats in the bag is, of course, the sum of these.  Sigma x.  (Which is seven, in this case)


Now - you're right in saying that the number of ways these can be lined up is (sigma x)! - and you're also right in saying that many of these orders are indistinguishable.
In general, you divide factorials, not subtract them.

Silly tips over, let's do this.

(Sigma x)! total arrangements.
But you can unshuffle the black cats and no one would notice.  So for every 2! (=2) lineups, there's only one after unshuffling the blacks.
Similarly, you can unshuffle the shitzu's (4!) - and although there's no point unshuffling the lonesome calico - luckily 1! = 1.

Well hey!  We can write this out much better:

(Sigma x )! / x1! . x2! . x3! . ... . xn!

And if you're feeling really fancy, a capital pi for geometric summation (ie. multiply atogether, rather than add together)
to give the nice and simple:

(Sigma x)! / Pi ( x! )

Careful you don't get the brackets in the wrong place.  You're factorialising all of the kittens after you add them up - but you're factoralising each species of kitten before you multiply them.


I think my kitten metaphor is now done.


DR has a question from another context which he would really like to know the answer to.
The simple version is:
  I have 12 socks; 6 red and 6 blue.  In how many ways can I divide them between 3 laundry bags?
  For example:
    ( ) ( ) (RRRRRR BBBBBB)
    (RRR ) ( BBB) (RRR BBB)
    (RRR BB) (RR BBB) (R B)
  The bags don't have individual features, though, so I don't distinguish between
    (RRR ) ( BBB) (RRR BBB)
  and
    ( BBB) (RRR ) (RRR BBB)
  for example.

  (The answer to this is [known] if you want to check your thinking...]

The more complex version is:
  If I have r red socks and b blue socks divided between d laundry bags, how many ways can I divide them?

Evil!  Evil I say!  Let me do the basics first!  --Vitenka
OK - here's how it (sorta) goes.  If the order of baskets DOES matter and the order of their contents does also, then it is pretty easy.  Add a number of items to your sock pile - these are the walls between your baskets.  (r+b+d-1)! (=nPr) as usual over this expanded bag, then divide by d! because you don't care which wall went where.
Why is that d! not (d-1)!, since you only have (d-1) walls? --DR
Yes, well caught.  --Vitenka (BetaTransformation? halfway through my thinking, didn't go back and fix)
To get to your example, you need to remove the ordering of the bags (that's easy enough - (d!) ) and then the ordering WITHIN each possible bag.  That's harder, since you need to know how MANY bags of each given size there are.
I appeal to 'the bubble problem' (see GCSE coursework)
I'm not having much luck finding which bubble problem you mean.  Is it [this one] ? --DR
No.  Look for 'nesting problem'  The problem as stated was "Bubbles may be drawn entirely outside or entirely inside other bubbles.  How many ways are there of arranging 'n' bubbles?"  --Vitenka (Which is a variant of this problem)
Hmm, still can't find anything on google.  I've had a go at doing it myself [problem] [thoughts on a solution] but haven't found the answer --DR
to point you in the direction of the phi function (Euler's totient function).
[mathematica] [primes] [planet math] [wikipedia] --DR
This is sufficient if there is one bag (and two colours).  Thinking of it as the co-efficients of a polynomial formed of (r+b)^(number in the basket) helps.
You extend this to more dimensions (bags) by having it a trinomial function
[Trinomial Triangle] --DR
and rderiving everything with pascals pyramid.
[Pascal's Pyramid] --DR
But my maths runs out a step before here - so this can only be considered as a hint.  Hope that helps.  --Vitenka
Not at all.  Thanks for the pointers. --DR



Ok, here we go again.  Sorry, the page should probably be in chapter two of a book.  I doubt I'll ever write that book, but.
The book is being written for the net.  It has cats in it.  --Vitenka



CategoryKittenTechnicalMatters
MaintainMe: Vitenka/CombinatoricsForCats?
ToDo: That evil exaple above.  An easier example I have elsewhere.

www.vitenka.com | ToothyWiki | Vitenka | RecentChanges | Login | Webcomic
This page is read-only | View other revisions | Recently used referrers
Last edited December 29, 2005 12:48 am (viewing revision 14, which is the newest) (diff)
Search: