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