home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / sci / math / 17539 < prev    next >
Encoding:
Internet Message Format  |  1992-12-31  |  1.4 KB
  1. Path: sparky!uunet!uchinews!msuinfo!indian.cps.msu.edu!sitarama
  2. From: sitarama@cps.msu.edu (Kocherlakota Sitarama)
  3. Newsgroups: sci.math
  4. Subject: Re: Two problems
  5. Date: 31 Dec 1992 05:47:42 GMT
  6. Organization: Dept. of Computer Science, Michigan State University
  7. Lines: 33
  8. Message-ID: <1hu1huINNflc@msuinfo.cl.msu.edu>
  9. References: <1992Dec28.220454.129@front.se> <israel.725681538@unixg.ubc.ca> <1992Dec30.185116.29392@maths.tcd.ie>
  10. Reply-To: sitarama@cps.msu.edu (Kocherlakota Sitarama)
  11. NNTP-Posting-Host: indian.cps.msu.edu
  12. Originator: sitarama@indian.cps.msu.edu
  13.  
  14. The second problem is a famous problem called 
  15. Problem Des' Menages
  16.  
  17. You can count the number of ways that we can arrange the couple
  18. with man not sitting next to his wife. Actually this problem is 
  19. a combinatorial problem and can be formulated as placing rooks
  20. on a chess board. And from the calculating the probability is easy.
  21.  
  22. If there are n couples the number of such seatings is given as 
  23.  
  24.     n 
  25. --------
  26. \        2n                              k
  27.  \     --------* C(2n-k,k) * (n-k) * (-1)
  28.  /      2n - k 
  29. /
  30. ---------
  31.   k = 0 
  32.  
  33.  
  34. I have a two page proof of that. But u can find, I think, find
  35. the proof any good book on comibinatorics. Such as Richard Stanlesy
  36. "Enumertive Combinatorics"
  37.  
  38.  
  39. Let me know if you need more help on this.
  40.  
  41. Swamy
  42. =======================================
  43. Sita Rama Swamy Kocherlakota
  44. Michagan State University, East Lansing
  45. =======================================
  46.  
  47.