I got Mathematica to work out the permutations and export them to a text file, and then copied the contents into Excel which counted the number of valid seating arrangements.
Mathematica could have done that last bit too, but I didn't know how. If bobbym was still here I'd've asked him, and he would've taught me how immediately!
Mathematica code: Export["seating.txt", Permutations[{c,c,c,c,c,r,r,r,r,r,m,m,m,m,m},{15}]]
Excel:
- Pasted the permutions list from the text file into A1, which Excel automatically populated into A1:A756756.
- Entered this formula into B1: =IF(AND(MID(A1,2,1)<>"c",MID(A1,5,1)<>"c",MID(A1,8,1)<>"c",MID(A1,11,1)<>"c",MID(A1,14,1)<>"c",MID(A1,17,1)<>"r",MID(A1,20,1)<>"r",MID(A1,23,1)<>"r",MID(A1,26,1)<>"r",MID(A1,29,1)<>"r",MID(A1,32,1)<>"m",MID(A1,35,1)<>"m",MID(A1,38,1)<>"m",MID(A1,41,1)<>"m",MID(A1,44,1)<>"m"),1,"")
- Double-clicked on the copy handle to automatically copy the formula down Column B alongside all the permutations in Column A.
- Entered this formula into C1: =SUM(B:B)
C1 output = 2252.
All quite quick, now that you clarified the problem, which shrank it to a manageable size for my method.
EDIT: This Mathematica code will give the answer 2252 (a post on mathematica.stackexchange gave me a clue):
Length[DeleteCases[Permutations[{c,c,c,c,c,r,r,r,r,r,m,m,m,m,m},{15}],{___,c,___,_,_,_,_,_,_,_,_,_,_}|{_,_,_,_,_,___,r,___,_,_,_,_,_}|{_,_,_,_,_,_,_,_,_,_,___,m,___}]]
It can be run online at Wolfram Programming Lab, if you don't have Mathematica. Just paste my code over the "2+2" code that appears in program 1 on the opening page, then press the orange/white 'Run input' arrow (or click somewhere in the code and press Shift+Enter).
]]>756756 permutations - 754504 constraints = 2252 different ways.
]]>I'd say, from the figures that are still embedded indelibly in my brain after spending so much time on your problem, that 2252 is a fair bit short of the mark.
Your puzzle, without any 'who can't sit where' constraints, has (3x5)! - ie, 1,307,674,368,000 - permutations of different seating arrangements.
Reducing the numbers in each group, I get:
(3 groups of 2)! = 720 different arrangements, of which 640 are eliminated by the seating constraint, leaving 80 valid arrangements;
(3 groups of 3)! = 362880 different arrangements, of which 350784 are eliminated by the seating constraint, leaving 12096 valid arrangements.
I got Mathematica to print the permutations, which I pasted into a text editor and did the eliminations there.
The next reduced group, that of 3 groups of 4 people, would give an even larger number of valid arrangements, and your 3 groups of 5 people puzzle would result in something much larger than the 3x4...which thickhead has probably found (not that I can confirm it).
]]>I've actually spent quite some hours on this, but I just don't have enough knowledge or understanding in this area to get anywhere with it. Having quit school after flunking 4th-year high school makes it well-nigh impossible for me to tackle something like this mathematically...which a problem of this size really needs.
Anyway, I ignored that and tried to solve it by reducing the OP's 5x3 group to the groups 2x3, 3x3 and 4x3, got each of the 3 groups' permutations, sifted out their incorrect seatings and obtained solutions for those groups (the 4x3 took a lot of effort!!). My plan was to play 'spot the pattern' with that info, but despite seeing lots of factorial content I just couldn't see a common factorial (or other) pattern in those groups that I could use to solve the 5x3 group.
I eventually decided that I'd spent far too much time taking the long route to nowhere, and gave up...and to make sure I didn't return to it (I find it hard to give up on something that I think I have a chance of solving, mind you!), I threw all of my work away.
Sorry, but your solution goes waaay over my head, and so I didn't comment.
]]>