Let y(n) = expected number of EMPTY seats for row of n seats f = (n - y(n)) / n

y(1) = 1 y(2) = 0 y(n) = 2 * SUM(i=1 to n-2) [y(i)? / (n-1)

To see this recurrence, consider the first person to sit down. The expected total number of empty seats will the sum of the expected number of empty seats to his left and to his right -- i.e. the sum of two previous y() values. The first person can sit in any of (n-1) equiprobable locations. Hence, y(n) is the sum of left and right portions over all n-1 locations divided by n-1.

To solve this, we are going to have to get rid of the summation.

By our formula, y(n-1) = 2 * SUM(i=1 to n-3) [y(i)? / (n-2) (I) (n-2)*y(n-1) = 2 * SUM(i=1 to n-3) [y(i)?

We can also get this same summation from our formula for y(n) by moving the i=(n-2) term out of the summation.

y(n) = 2 * {SUM(i=1 to n-3) [y(i)? + y(n-2)} / (n-1) (II) y(n) = {2 * SUM(i=1 to n-3) [y(i)? + 2*y(n-2)} / (n-1)

Now substitute for the summation using (I),

(*) y(n) = {(n-2)*y(n-1) + 2*y(n-2)} / (n-1)

(n-1)*y(n) - (n-2)*y(n-1) - 2*y(n-2) = 0

A note on terminology: This recurrence would be usually be called linear with nonconstant coefficents. Linearity in difference equations usually refers to linearity in the y(n), so that given solutions y1(n) and y2(n), (a y1(n) + b y2(n)) is also a solution.)

One way of handling recurrences of this type (having coefficients which are polynomial in n) is to deal with a generating function, which is the function Y(z) of the formal variable z which has Taylor coefficients y(n): i.e.,

Y(z) = sum_{n=0}^\infty y(n) z^n

(here we set y(0)=0 for convenience). Now coefficients which are polynomials in n may be replaced by derivatives of the Y(z), giving a differential equation for Y (of order the maximal degree of the polynomials in n). Here, for example (where D = d/dz)

0 = sum_{n=0}^\infty z^n[(n+1)*y(n+2) - n*y(n+1) - 2*y(n)?

= sum_n [(n+1)*z^n*y(n+2) - n*z^n*y(n+1) - 2*z^n*y(n)? = sum_n [D[[y(n+2)*z^{n+1}? - z*D[y(n+1)*z^n? - 2*z^n*y(n)] = sum_n [D[[(1/z)*y(n+2)*z^{n+2}? - z*D[(1/z)*y(n+1)*z^{n+1}?

  • 2*z^n*y(n)]

(here I'm going to be cavalier about the summation limits;

if you check it, it actually does work out nicely)

= [D (1/z) - z D (1/z) - 2?*sum_n z^n*y(n) = (1-z) D (Y(z)/z) - 2*Y(z)

giving the first-order differential equation

Y'(z) / Y(z) = (2*z^2 - z + 1) / (z*(1-z))

for the generating function.

This is mildly ugly but can be solved. Then Taylor expansion gives the coefficients y(n). In this case, y(n) can be computed exactly with a sum over n terms; the terms are well approximated, for large n, by y(n) (n+2) exp(-2), for a filling factor (for large n) of 1 - exp(-2).

lib/DbaDatabase.php:134: Warning: dba_replace() [<a href='function.dba-replace'>function.dba-replace</a>]: You cannot perform a modification to a database without proper access