I came across a problem in a book on Combinatorics
In how many ways can 5 gentleman and 3 ladies be seated such that no two ladies sit next to each other?
The book's answer was 5!. Clearly not very believable, I decided to warm myself up and try and find an answer.
My first answer was
8! - 2.7! - 6.6!
Something did not seem right, so I decided to use brute force. I wrote quick python code to list 8! permutations (all of them) and discard positions with two ladies together (yes, I permuted classes with numbers and types). The answer was 14400. Clearly I missed something and the computer cannot be wrong - well brute force is usually slow but right :)
A little more thought and use of common sense got me to the right answer
8! - (3 C 2)*2*7! + 6.6! (via inclusion/exclusion principle)
I am so excited to use brute force to check my answers - do you?
In how many ways can 5 gentleman and 3 ladies be seated such that no two ladies sit next to each other?
The book's answer was 5!. Clearly not very believable, I decided to warm myself up and try and find an answer.
My first answer was
8! - 2.7! - 6.6!
Something did not seem right, so I decided to use brute force. I wrote quick python code to list 8! permutations (all of them) and discard positions with two ladies together (yes, I permuted classes with numbers and types). The answer was 14400. Clearly I missed something and the computer cannot be wrong - well brute force is usually slow but right :)
A little more thought and use of common sense got me to the right answer
8! - (3 C 2)*2*7! + 6.6! (via inclusion/exclusion principle)
I am so excited to use brute force to check my answers - do you?
No comments:
Post a Comment