Linear Recurrences with Polynomial Coefficients satisfied by the Probability Generating Function According to the number of Passengers sitting in the wrong seat where there there are n passengers with the FIRST one being absent-minded. By Shalosh B. Ekhad Theorem Number, 1 Let , A[1](n)(w), be the the probability generating function according to the random variable NumberOfPassengersSittingInTheWrong Seat where there are, n, passengers,the first, 1, of whom are absent-minded Then we have the following recurrence n (n + w) A[1](n) (2 n + w + 1) A[1](1 + n) ----------------- - ------------------------- + A[1](2 + n) = 0 (2 + n) (1 + n) 2 + n and in Maple notation n*(n+w)/(2+n)/(1+n)*A[1](n)-(2*n+w+1)/(2+n)*A[1](1+n)+A[1](2+n) = 0 subject to the initial conditions 2 w A[1](1)(w) = 1, A[1](2)(w) = 1/2 + ---- 2 and in Maple notation A[1](1)(w) = 1, A[1](2)(w) = 1/2+1/2*w^2 Theorem Number, 2 Let , A[2](n)(w), be the the probability generating function according to \ the random variable NumberOfPassengersSittingInTheWrong Seat where there are, 1 + n, passengers,the first, 2, of whom are absent-minded Then we have the following recurrence n (n + 2 w) (n + w) A[2](n) - --------------------------- (n + 4) (n + 3) (2 + n) 2 2 (3 n + 6 n w + 2 w + 3 n + 3 w + 1) A[2](1 + n) + ------------------------------------------------- (n + 3) (n + 4) 3 (n + w + 1) A[2](2 + n) - ------------------------- + A[2](n + 3) = 0 n + 4 and in Maple notation -n*(n+2*w)*(n+w)/(n+4)/(n+3)/(2+n)*A[2](n)+(3*n^2+6*n*w+2*w^2+3*n+3*w+1)/(n+3)/ (n+4)*A[2](1+n)-3*(n+w+1)/(n+4)*A[2](2+n)+A[2](n+3) = 0 subject to the initial conditions 2 w 2 3 A[2](1)(w) = 1/2 + ----, A[2](2)(w) = 1/2 w + 1/3 w + 1/6, 2 4 2 3 A[2](3)(w) = 1/4 w + 1/3 w + 1/3 w + 1/12 and in Maple notation A[2](1)(w) = 1/2+1/2*w^2, A[2](2)(w) = 1/2*w^2+1/3*w^3+1/6, A[2](3)(w) = 1/4*w^ 4+1/3*w^2+1/3*w^3+1/12 Theorem Number, 3 Let , A[3](n)(w), be the the probability generating function according to \ the random variable NumberOfPassengersSittingInTheWrong Seat where there are, 2 + n, passengers,the first, 3, of whom are absent-minded Then we have the following recurrence n (n + 2 w) (n + 3 w) (n + w) A[3](n) ------------------------------------- (n + 5) (n + 4) (n + 3) (n + 6) 2 2 (3 w + 1 + 2 n) (2 n + 6 n w + 2 w + 2 n + 3 w + 1) A[3](1 + n) - ----------------------------------------------------------------- (n + 5) (n + 4) (n + 6) 2 2 (6 n + 18 n w + 11 w + 12 n + 18 w + 7) A[3](2 + n) + ----------------------------------------------------- (n + 6) (n + 5) 2 (2 n + 3 w + 3) A[3](n + 3) - ----------------------------- + A[3](n + 4) = 0 n + 6 and in Maple notation n*(n+2*w)*(n+3*w)*(n+w)/(n+5)/(n+4)/(n+3)/(n+6)*A[3](n)-(3*w+1+2*n)*(2*n^2+6*n* w+2*w^2+2*n+3*w+1)/(n+5)/(n+4)/(n+6)*A[3](1+n)+(6*n^2+18*n*w+11*w^2+12*n+18*w+7 )/(n+6)/(n+5)*A[3](2+n)-2*(2*n+3*w+3)/(n+6)*A[3](n+3)+A[3](n+4) = 0 subject to the initial conditions 2 3 A[3](1)(w) = 1/2 w + 1/3 w + 1/6, 4 2 3 A[3](2)(w) = 3/8 w + 1/4 w + 1/3 w + 1/24, 4 11 5 2 3 A[3](3)(w) = 3/8 w + -- w + 1/8 w + 5/24 w + 1/60, 40 3 4 5 13 6 17 2 A[3](4)(w) = 2/15 w + 7/24 w + 1/3 w + 1/120 + -- w + --- w 80 240 and in Maple notation A[3](1)(w) = 1/2*w^2+1/3*w^3+1/6, A[3](2)(w) = 3/8*w^4+1/4*w^2+1/3*w^3+1/24, A[ 3](3)(w) = 3/8*w^4+11/40*w^5+1/8*w^2+5/24*w^3+1/60, A[3](4)(w) = 2/15*w^3+7/24* w^4+1/3*w^5+1/120+13/80*w^6+17/240*w^2 Theorem Number, 4 Let , A[4](n)(w), be the the probability generating function according to \ the random variable NumberOfPassengersSittingInTheWrong Seat where there are, n + 3, passengers,the first, 4, of whom are absent-minded Then we have the following recurrence n (n + 4 w) (n + 2 w) (n + 3 w) (n + w) A[4](n) 4 3 2 2 - ----------------------------------------------- + (5 n + 40 n w + 105 n w (n + 5) (n + 4) (n + 8) (n + 7) (n + 6) 3 4 3 2 2 3 2 + 100 n w + 24 w + 10 n + 60 n w + 105 n w + 50 w + 10 n + 40 n w 2 + 35 w + 5 n + 10 w + 1) A[4](1 + n)/((n + 5) (n + 8) (n + 7) (n + 6)) 2 2 5 (2 w + 1 + n) (2 n + 8 n w + 5 w + 4 n + 8 w + 3) A[4](2 + n) - ----------------------------------------------------------------- (n + 8) (n + 7) (n + 6) 2 2 5 (2 n + 8 n w + 7 w + 6 n + 12 w + 5) A[4](n + 3) + ---------------------------------------------------- (n + 7) (n + 8) 5 (n + 2 w + 2) A[4](n + 4) - --------------------------- + A[4](n + 5) = 0 n + 8 and in Maple notation -n*(n+4*w)*(n+2*w)*(n+3*w)*(n+w)/(n+5)/(n+4)/(n+8)/(n+7)/(n+6)*A[4](n)+(5*n^4+ 40*n^3*w+105*n^2*w^2+100*n*w^3+24*w^4+10*n^3+60*n^2*w+105*n*w^2+50*w^3+10*n^2+ 40*n*w+35*w^2+5*n+10*w+1)/(n+5)/(n+8)/(n+7)/(n+6)*A[4](1+n)-5*(2*w+1+n)*(2*n^2+ 8*n*w+5*w^2+4*n+8*w+3)/(n+8)/(n+7)/(n+6)*A[4](2+n)+5*(2*n^2+8*n*w+7*w^2+6*n+12* w+5)/(n+7)/(n+8)*A[4](n+3)-5*(n+2*w+2)/(n+8)*A[4](n+4)+A[4](n+5) = 0 subject to the initial conditions 4 2 3 A[4](1)(w) = 3/8 w + 1/4 w + 1/3 w + 1/24, 4 11 5 2 3 A[4](2)(w) = 3/8 w + -- w + 1/12 w + 1/6 w + 1/120, 30 53 6 4 11 5 2 3 A[4](3)(w) = --- w + 9/40 w + -- w + 1/30 w + 7/90 w + 1/360, 180 30 7 17 3 67 4 17 5 29 6 2 A[4](4)(w) = 1/840 + 7/36 w + --- w + --- w + -- w + -- w + 1/63 w , 420 504 63 84 1097 8 2843 7 233 3 829 4 479 5 A[4](5)(w) = ----- w + 1/1680 + ----- w + ----- w + ----- w + ---- w 10080 10080 10080 10080 2520 307 6 43 2 + ---- w + ---- w 1008 5040 and in Maple notation A[4](1)(w) = 3/8*w^4+1/4*w^2+1/3*w^3+1/24, A[4](2)(w) = 3/8*w^4+11/30*w^5+1/12* w^2+1/6*w^3+1/120, A[4](3)(w) = 53/180*w^6+9/40*w^4+11/30*w^5+1/30*w^2+7/90*w^3 +1/360, A[4](4)(w) = 1/840+7/36*w^7+17/420*w^3+67/504*w^4+17/63*w^5+29/84*w^6+1 /63*w^2, A[4](5)(w) = 1097/10080*w^8+1/1680+2843/10080*w^7+233/10080*w^3+829/ 10080*w^4+479/2520*w^5+307/1008*w^6+43/5040*w^2