The Average Pagenumber of a Permutation 



A book consists of n half-planes identified along their common boundary. Each half-plane is called a page; their common boundary is the spine. Consider the numbers 1,...,n placed in a randomly permuted order pi(n) along the spine. The goal is to add edges in the book joining each k to k+1 for each k. Each edge must lie in a single page. Two distinct edges can intersect only in their common endpoint. The pagenumber or book thickness, pn(pi(n)), of the permutation pi is the smallest number of pages needed to add these edges.

George Baloglou asks the following:

Question: What is the average value of pn(pi(n)) over all permutations pi of 1,..., n?

He notes that pn(pi(n)) lies between 1 and n/2, so the average also falls in this range.

I calculate quickly that the average is 1 for n = 2,3. The average is 4/3 for n = 4 where exactly 8 of the 24 permutations need two pages (I had this number wrong in an earlier version of the problem).

Saul Stahl reports (personal communication) that he has some bounds for this problem. The answer is approximately c n^{1/2} for some constant c. The reader is advised to contact Saul at stahl@kuhub.cc.ukans.edu before working on this problem.


Submitted by: Dan Archdeacon (for George Balaglou, Dept. of Math., SUNY Oswego, NY 13126)

Send comments to dan.archdeacon@uvm.edu

August, 1995