Argh. You would have to go and ask one that ISN'T an easy one, wouldn't you? (From memory, this has to do with the phi funciton and binomials are involved) Ah yes, it's the bbbles one restated. Let's restate it again.
The reasoning is somewhat similar, however.
Start simply.
We've got some socks, and some... uh, kittens don't wear socks. Foxes. We've all heard of fox in socks. (Could be ponies, if you preferred)
Ok, this one really needsw to be done by induction. Pascals triangle.
Call nPTm 'the number of different unique ways to put n socks onto m foxes'.
1PT1 is, obviously, 1. 1 sock on 1 fox.
2PT1 and 1PT2 are, equally obviously, 1. 2 socks on one fox and '1 socked fox and a spare fox'
That's interesting. Where do we go from here?
2PT2 is 2. There are three arrangements - a double socked fox and a spare fox, and 2 singly socked foxes.
Hmmm. Where can we go with this? Oh yes. Induction.
Given some way of socking the foxes - we can do two things.
We can add a sock, or we can add a fox.
Adding a fox is easy.
At first it stays unsocked. The arrangement is new and unique, we can't possibly rearrange the existing foxes to get that result. We know that all of the previous arrangements don't double count anything (1PT1 etc. doesn't, and it's our rule). And the number of arrangements is thus the number we had that way before we added the fox.
So: nPTm += nPT(m-1) new arrangements.
But that fox need not stay unsocked. It could steal a sock from one of the other foxes, forming a whole load of new arrangements.
We don't mind which fox it steals from - because we know how many arrangements we can make with one less sock.
You've got all of the arrangements of the other foxes (less the sock the new guy just stole) - but with an extra socked fox tacked onto the end. Again - it must be unique because we know the old arrangement was unique, and the new arrangement has more foxes.
So we get: (n-1)PT(m-1) more arrangements!
But wait - some of those are not unique - they are shared with the 'zero fox' ones we already saw.
So we get the induction formula: nPTm = nPT(m-1) + (n-1)PT(m-1)
We don't even need to worry about going in the direction of adding socks - our sock stealing fox has given it to us for free! (And you'll also notice that it's symmetrical - it could be socks choosing to wear foxes instead and all the maths would be the same)
Luckily, some clever folks have all gone and worked this out for us. It's called 'Pascals Triangle' and the formula is:
Right - so. That let's us divide ONE colour among the bags. Now for two.
Well, this works out quite similarly. Except we need better notation.
Lets have PP(f,r,b) mean 'f foxes, r red socks and b blue socks'
Ok. PP(1,1,1) is simple - 1 fox, both socks.
In fact PP(1,x,y) is simple - no matter how many different socks you have, there's only one fox to put them on. So one arrangement.
So let's see what happens with two foxes.
PP(2,1,0) = 1. A fox with a red sock and a fox without.
PP(2,0,1) = 1. Same, but a blue sock.
PP(2,1,1) = 2. Seeing a pattern yet? We've got a fox with both socks, and another arrangement with a red socked fox and a blue socked fox.
So. Given a number of unique arrangements, PP(f,r,b) - what happens if we add a fox? (To make PP(f+1,r,b) )
Well, clearly it could stay sockless. PP(f,r,b) arrangements with an extra lonely sockless fox.
If could steal a red sock. PP(f,r-1,b)
It could steal a blue sock. PP(f,r,b-1)