In How Many Ways Can n (Straight) Men and n (Straight) Women Get Married, if Each Person Has Exactly k Spouses

By Shalosh B. EKHAD and Doron ZEILBERGER


.pdf   .ps   .tex  
Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger
First Written: Dec. 29, 2006. This version: Jan. 11, 2007.

What's so nice about this work is that ONE program does both the symbol-crunching and the number-crunching. Of course, to do serious number-crunching, you might have to go to C, after doing code-generation in Maple, but we can still go pretty far just with Maple.


Important: This article is accompanied by Maple packages
  • Bipartite that computes recurrence operators for computing enumerating sequences for the number of n by n zero-one matrices (and more generally, with entries between 0 and r) each of whose rows and columns add up to k, for fixed k, and then proceeds to use it for actually computing the first few (or many) terms of these sequences.
  • LatinRectangles, that does the same for n by k Latin Rectangles (for fixed k). (Warning: Already for k=4 it is hopeless!).


Sample Output for Bipartite
The input yields the output.


Sample Output for LatinRectangles
  • To find the first 20 terms of the enumerating sequence for 1 by n Latin Rectangles, divided by n!, The input yields the output.
  • To find the first 20 terms of the enumerating sequence for 2 by n Latin Rectangles, divided by n!, The input yields the output.
  • To find the first 20 terms of the enumerating sequence for 3 by n Latin Rectangles, divided by n!, The input yields the output.
  • To find the first 9 terms of the enumerating sequence for 4 by n Latin Rectangles, divided by n!, The input yields the output.

Personal Journal of Shalosh B. Ekhad and Doron Zeilberger

Doron Zeilberger's Home Page