In How Many Ways Can You Reassemble Several Russian Dolls?

By Doron Zeilberger

.pdf   .ps   .tex  
Written: Sept. 16, 2009.
Dedicated to Thotsaporn and Thotsaphon Thanatipanonda
Exclusively published in the Personal Journal of Ekhad and Zeilberger and at arxiv.org.
When my brilliant student Thotsaporn "Aek" Thanatipanonda asked me about how many ways can one cover n pairs of identical twins, it rang a Bell back to 1981 (see the article). As usual, the method of teaching the computer how to do its own combinatorics, and to use "analysis" (that is really part of discrete math) to enumerate challenging combinatorial objects is even more interesting than the theorems and even the algorithm. Of course, formulas are dead, long live algorithms! But even algorithms are dead, long live meta-algorithms!!

Maple Packages

Important: This article is accompanied by Maple package

Sample Input and Output for BABUSHKAS

  • In order to view the the number of ways of reassembling one n-shelled, two identical n-shelled, and three identical n-shelled Russian Dolls for n=0..50,
    the input gives the output.

  • In order to view the ordinary generating functions (that happen to be rational functions) for the number of ways of reassembling one n-shelled, two identical n-shelled, and three identical n-shelled Russian Dolls into k dolls, for small k,
    the input gives the output.

  • In order to view the the number of ways of reassembling four identical n-shelled Russian Dolls for n=0..30,
    the input gives the output.

  • In order to view the the number of ways of reassembling five identical n-shelled Russian Dolls for n=0..20,
    the input gives the output.

  • In order to view the the number of ways of reassembling six identical n-shelled Russian Dolls for n=0..10,
    the input gives the output.

  • In order to view the the number of ways of reassembling seven identical n-shelled Russian Dolls for n=0..10,
    the input gives the output.

  • In order to view the the number of ways of reassembling eight identical n-shelled Russian Dolls for n=0..8,
    the input gives the output.

  • In order to view the the number of ways of reassembling nine identical n-shelled Russian Dolls for n=0..5,
    the input gives the output.

  • In order to find out the exact number of ways of breaking up a set of people consisting of three simple persons, four pairs of identical twins, and two identical triplets, (altogether 3+4*2+2*3=17 people),
    the input gives the output.

Personal Journal

Doron Zeilberger's List of other Papers

Doron Zeilberger's Home Page