I've annoyed myself by getting stuck attempting to work out a silly maths problem relating to permutations. It's an extension of the 'how many odd socks do I have to pull out of a drawer before I find a pair' problem. Only my theoretical sock-wearer has three legs. And a penchant for odd socks.
Let's say I'm Jake the Peg
. I have s
socks in a drawer. There are n
different types of sock. On average, how many socks must I remove from the drawer before I get three odd ones?
I've worked this out from scratch using a drawer containing only 5 socks. Obviously, if all 5 socks are different (s=n=5), then there are 5!
different ways of pulling the 5 socks from the drawer, and every single one of those leads to me having an odd triplet after only 3 socks.
If I only have 4 types of sock (i.e. in the drawer of 5, there's 1 pair and 3 odd ones), again, there are 120 ways of pulling all 5 socks out of the drawer, but this time there are only 60 unique sequences [I managed to work out from first principles that the number of unique ways of withdrawing the socks is s!/(s-n+1)!
, not that that seems to help me at all ]. 84 of these sequences lead me to have an odd triplet after the first three socks. 36 of these lead me to have an odd triplet after the first four socks. At no stage do I need to withdraw all 5. So now the average number of socks I need to withdraw to get an odd triplet is (3x84 + 4*36)/120 = 3.3.
If I now only have 3 types of sock (i.e. in the drawer of 5, there are three black ones, a 'Worlds Best Dad' and a Homer Simpson), there are 20 unique ways of removing them all, and, if I've counted right, 37 ways of getting an odd triplet after 3 socks; 35 ways of getting an odd triplet after 4 socks; 48 ways of only getting an odd triplet after removing all 5 socks from the drawer. This leads to an average of 4.09.
My tiny brain is now too overheated to take this further. There must be a connection between these numbers, but I can't get a handle on a pattern, and am too daunted by the prospect of writing out all the variations of 720 sequences for a drawer of 6 socks to do it by brute force. Can anyone please put me out of my misery and point me towards a general formula for this, to solve the average number of socks necessary to achieve an odd triplet given s
socks and n