Explicit Polynomial Expressions in, k, for the Number of Permutations of length k+i, Containing an increasing sequence of length k for i from 1 to, 5 By Shalosh B. Ekhad Theorem Number, 0, Let , V(0)(k), be the number of permutations of length, k, that include at least one increasing subsequence of length , k, then V(0)(k) = 1 Proof: trivial (you do it!) Theorem Number, 1, Let , V(1)(k), be the number of permutations of length, k + 1, that include at least one increasing subsequence of length , k, then 2 V(1)(k) = k + 1 and in Maple notation: V(1)(k) = k^2+1 Proof: The family tree of our class of permutation can be seen to be [[1, [k - 1, 1]], [k, [k - 1, 0]], [k - 1, [k, 0]]] This implies the recurrence V(1)(k) = V(1)(k - 1) + k V(0)(k - 1) + V(0)(k) k - V(0)(k) and the statement follows by induction. QED Theorem Number, 2, Let , V(2)(k), be the number of permutations of length, k + 2, that include at least one increasing subsequence of length , k, then 4 3 2 V(2)(k) = 1/2 k + k + 1/2 k + k + 3 and in Maple notation: V(2)(k) = 1/2*k^4+k^3+1/2*k^2+k+3 Proof: The family tree of our class of permutation can be seen to be [[1, [k - 1, 2]], [k + 1, [k - 1, 1]], [1, 2 [[1, [k - 1, 1]], [k, [k - 1, 0]], [k - k, [k - 2, 0]], [k - 2, [k, 0]]]], [k - 1, [k, 1]]] This implies the recurrence V(2)(k) = V(2)(k - 1) + V(1)(k - 1) k + 2 V(1)(k - 1) + k V(0)(k - 1) 2 + V(0)(k - 2) k - V(0)(k - 2) k + V(0)(k) k - 2 V(0)(k) + V(1)(k) k - V(1)(k) and the statement follows by induction. QED Theorem Number, 3, Let , V(3)(k), be the number of permutations of length, k + 3, that include at least one increasing subsequence of length , k, then 4 3 2 6 5 V(3)(k) = 5/3 k + 2/3 k + 19/6 k + 31/3 k + 1/6 k + k + 11 and in Maple notation: V(3)(k) = 5/3*k^4+2/3*k^3+19/6*k^2+31/3*k+1/6*k^6+k^5+11 Proof: The family tree of our class of permutation can be seen to be [[1, [k - 1, 3]], [k + 2, [k - 1, 2]], [1, [[1, [k - 1, 2]], 2 [k + 1, [k - 1, 1]], [k + k, [k - 2, 1]], [1, [[1, [[1, [k - 2, 1]], 2 [k - 1, [k - 2, 0]], [k - 3 k + 2, [k - 3, 0]], [k - 3, [k - 1, 0]]]], %1, 3 2 %1, [k - 3 k + 2 k, [k - 3, 0]], [k - 3, [k, 0]]]], [k - 2, [[1, [k - 1, 1]], [k, [k - 1, 0]], %1, [k - 2, [k, 0]]]]]], [1, [ [1, [k - 1, 2]], [k + 1, [k - 1, 1]], [1, [[1, [k - 1, 1]], [k, [k - 1, 0]], %1, [k - 2, [k, 0]]]], [1, [[1, [ 2 [1, [k - 2, 1]], [k - 1, [k - 2, 0]], [k - 3 k + 2, [k - 3, 0]], 3 2 [k - 3, [k - 1, 0]]]], %1, %1, [k - 3 k + 2 k, [k - 3, 0]], [k - 3, [k, 0]]]], [k - 2, [k, 1]]]], [k - 1, [k, 2]]] 2 %1 := [k - k, [k - 2, 0]] This implies the recurrence 2 3 2 V(3)(k) = k V(0)(k - 1) + V(0)(k - 2) k + V(0)(k) k + V(2)(k) k 2 + 3 V(1)(k - 1) k + 2 V(0)(k - 2) k - V(0)(k - 2) k + V(1)(k) k 2 2 + V(2)(k - 1) k + V(1)(k - 2) k + V(1)(k - 2) k - 4 V(0)(k - 3) k 3 - 2 V(0)(k - 3) k + 2 V(0)(k - 3) k + k V(0)(k - 1) - V(0)(k) k + 4 V(0)(k - 3) + V(3)(k - 1) + 2 V(1)(k - 2) + 4 V(2)(k - 1) - 2 V(0)(k - 2) - 2 V(1)(k) + V(1)(k - 1) - 6 V(0)(k - 1) - V(2)(k) - 4 V(0)(k) and the statement follows by induction. QED Theorem Number, 4, Let , V(4)(k), be the number of permutations of length, k + 4, that include at least one increasing subsequence of length , k, then V(4)(k) = 25 6 5 8 7 29 4 3 2 -- k + 19/6 k + 1/24 k + 1/2 k + -- k + 9 k + 247/6 k + 395/6 k + 47 12 24 and in Maple notation: V(4)(k) = 25/12*k^6+19/6*k^5+1/24*k^8+1/2*k^7+29/24*k^4+9*k^3+247/6*k^2+395/6*k +47 Proof: The family tree of our class of permutation can be seen to be [[1, [k - 1, 4]], [k + 3, [k - 1, 3]], [1, [[1, [k - 1, 3]], 2 [k + 2, [k - 1, 2]], [k + 3 k + 2, [k - 2, 2]], [1, [[1, 2 [[1, [k - 2, 2]], [k, [k - 2, 1]], [k - k, [k - 3, 1]], %3, [k - 3, %6]]], 3 %11, %11, [k - k, [k - 3, 1]], %4, [k - 3, %7]]], [1, [%8, [k + 1, %6], %11, [1, %7], %4, [k - 3, %9]]], [k - 2, %12]]], [1, [[1, [k - 1, 3]], [k + 2, [k - 1, 2]], [1, %12], [1, [[1, 2 [[1, [k - 2, 2]], [k, [k - 2, 1]], [k - k, [k - 3, 1]], %3, [k - 3, %6]]], 3 %11, %11, [k - k, [k - 3, 1]], %4, [k - 3, %7]]], [1, [%8, [k + 1, %6], [1, %7], [1, %7], %4, [k - 3, [k, 1]]]], [k - 2, [[1, [k - 1, 2]], %10, [1, %9], [1, %7], [k - 2, [k, 1]]]]]], [1, [ [1, [k - 1, 3]], [k + 2, [k - 1, 2]], [1, %12], [1, [[1, [k - 1, 2]], %10, [1, %9], [1, %7], [k - 2, [k, 1]]]], [1, [%8, [k + 1, %6], [1, %7], [1, %7], %4, [k - 3, [k, 1]]]], [k - 2, [k, 2]]]], [k - 1, [k, 3]]] 3 2 %1 := [k - 3 k + 2 k, [k - 3, 0]] 2 %2 := [k - 3 k + 2, [k - 3, 0]] %3 := [1, [[1, [[1, [k - 3, 1]], [k - 2, [k - 3, 0]], 2 [k - 5 k + 6, [k - 4, 0]], [k - 4, [k - 2, 0]]]], %2, %2, 3 2 [k - 6 k + 11 k - 6, [k - 4, 0]], [k - 4, [k - 1, 0]]]] %4 := [ 4 3 2 1, [%3, %1, %1, %1, [k - 6 k + 11 k - 6 k, [k - 4, 0]], [k - 4, [k, 0]]] ] 2 %5 := [k - k, [k - 2, 0]] %6 := [[1, [k - 2, 1]], [k - 1, [k - 2, 0]], %2, [k - 3, [k - 1, 0]]] %7 := [[1, %6], %5, %5, %1, [k - 3, [k, 0]]] %8 := [1, [[1, [k - 2, 2]], [k, [k - 2, 1]], [1, %6], %3, [k - 3, [k - 1, 1]]]] %9 := [[1, [k - 1, 1]], [k, [k - 1, 0]], %5, [k - 2, [k, 0]]] %10 := [k + 1, [k - 1, 1]] 2 %11 := [k + k, [k - 2, 1]] %12 := [[1, [k - 1, 2]], %10, %11, [1, %7], [k - 2, %9]] This implies the recurrence 3 2 3 3 V(4)(k) = V(0)(k) k + 3 V(1)(k - 1) k + V(1)(k - 2) k + k V(0)(k - 1) 4 4 2 + V(0)(k - 2) k + 4 V(0)(k - 3) k + 5 V(0)(k - 4) k + 30 V(0)(k - 4) k 3 3 4 - 20 V(0)(k - 4) k + 2 V(1)(k - 3) k + 5 V(0)(k - 4) k 2 3 2 + 9 k V(0)(k - 1) + 7 V(0)(k - 2) k + 2 V(0)(k) k + V(2)(k) k 2 2 + V(3)(k - 1) k + V(2)(k - 2) k + 3 V(2)(k - 2) k + 2 V(1)(k - 3) k 2 - 4 V(1)(k - 3) k + 4 V(1)(k - 1) k - 7 V(0)(k - 2) k + 7 V(0)(k - 2) k 2 - V(1)(k) k + 5 V(2)(k - 1) k + 6 V(1)(k - 2) k + 19 V(1)(k - 2) k 2 3 - 40 V(0)(k - 3) k + 10 V(0)(k - 3) k - 23 k V(0)(k - 1) - 13 V(0)(k) k + V(3)(k) k + 16 V(0)(k - 3) - V(3)(k) + 6 V(3)(k - 1) - 2 V(1)(k - 2) + 5 V(2)(k - 1) - 38 V(0)(k - 2) - 4 V(1)(k) - 14 V(1)(k - 1) 2 - 34 V(0)(k - 1) - 2 V(2)(k) - 6 V(0)(k) + V(1)(k) k + 7 V(2)(k - 2) + 10 V(1)(k - 3) + V(4)(k - 1) and the statement follows by induction. QED Theorem Number, 5, Let , V(5)(k), be the number of permutations of length, k + 5, that include at least one increasing subsequence of length , k, then 10 9 823 6 67 5 31 8 7 653 4 V(5)(k) = 1/120 k + 1/6 k + --- k + -- k + -- k + 14/3 k + --- k 120 30 24 24 3 10459 2 3981 + 959/6 k + ----- k + ---- k + 239 30 10 and in Maple notation: V(5)(k) = 1/120*k^10+1/6*k^9+823/120*k^6+67/30*k^5+31/24*k^8+14/3*k^7+653/24*k^ 4+959/6*k^3+10459/30*k^2+3981/10*k+239 Proof: The family tree of our class of permutation can be seen to be [[1, [k - 1, 5]], [k + 4, [k - 1, 4]], [1, [[1, [k - 1, 4]], %37, 2 [k + 5 k + 6, [k - 2, 3]], [1, [ 2 [1, [[1, [k - 2, 3]], %26, [k + k, [k - 3, 2]], %38, %41, [k - 3, %25]]], 3 2 %35, %35, [k + 3 k + 2 k, [k - 3, 2]], %39, 2 2 [1, [%41, [k + k, %9], [k + k, %9], %32, [1, %11], %6, [k - 4, %18]]], [k - 3, %33]]], [1, [%40, [k + 2, %25], %35, [1, %33], %39, [ 2 1, [%14, [k + 1, %10], [k + k, %9], [1, %11], [1, %11], %6, [k - 4, %21]]] , [k - 3, %23]]], [1, [%27, [k + 2, %19], %35, [1, %33], [1, %23], [ 2 1, [%14, [k + 1, %10], [k + k, %9], [1, %11], [1, %11], %6, [k - 4, %21]]] , [k - 3, %30]]], [k - 2, %36]]], [1, [[1, [k - 1, 4]], %37, [1, %36], [1, 2 [[1, [[1, [k - 2, 3]], %26, [k + k, [k - 3, 2]], %38, %41, [k - 3, %25]]], 3 2 %35, %35, [k + 3 k + 2 k, [k - 3, 2]], %39, 2 2 [1, [%41, [k + k, %9], [k + k, %9], %32, [1, %11], %6, [k - 4, %18]]], [k - 3, %33]]], [1, [%40, [k + 2, %25], [1, %33], [1, %33], %39, %15, [k - 3, %20]]], [1, [%27, [k + 2, %19], [1, %23], [1, %33], [1, %20], %15, [k - 3, %29]]], [k - 2, %34]]], [1, [[1, [k - 1, 4]], %37, [1, %36], [1, %34], [1, [%40, [k + 2, %25], [1, %33], [1, %33], %39, %15, [k - 3, %20]]], [ 1, [%27, [k + 2, %19], [1, %23], [1, %20], [1, %20], %15, [k - 3, [k, 2]]]] , [k - 2, [[1, [k - 1, 3]], %31, [1, %30], [1, %29], [1, %20], [k - 2, [k, 2]]]]]], [ 1, [[1, [k - 1, 4]], %37, [1, %36], [1, %34], [1, [[1, [k - 1, 3]], %31, [1, %30], [1, %29], [1, %20], [k - 2, [k, 2]]]], [1, [%27, [k + 2, %19], [1, %23], [1, %20], [1, %20], %15, [k - 3, [k, 2]]] ], [k - 2, [k, 3]]]], [k - 1, [k, 4]]] 4 3 2 %1 := [k - 6 k + 11 k - 6 k, [k - 4, 0]] 3 2 %2 := [k - 6 k + 11 k - 6, [k - 4, 0]] 2 %3 := [k - 5 k + 6, [k - 4, 0]] %4 := [1, [[1, [[1, [k - 4, 1]], [k - 3, [k - 4, 0]], 2 [k - 7 k + 12, [k - 5, 0]], [k - 5, [k - 3, 0]]]], %3, %3, 3 2 [k - 9 k + 26 k - 24, [k - 5, 0]], [k - 5, [k - 2, 0]]]] 4 3 2 %5 := [1, [%4, %2, %2, %2, [k - 10 k + 35 k - 50 k + 24, [k - 5, 0]], [k - 5, [k - 1, 0]]]] 5 4 3 2 %6 := [1, [%5, %1, %1, %1, %1, [k - 10 k + 35 k - 50 k + 24 k, [k - 5, 0]], [k - 5, [k, 0]]]] 3 2 %7 := k - 3 k + 2 k 2 %8 := [k - 3 k + 2, [k - 3, 0]] %9 := [[1, [k - 3, 1]], [k - 2, [k - 3, 0]], %3, [k - 4, [k - 2, 0]]] %10 := [[1, %9], %8, %8, %2, [k - 4, [k - 1, 0]]] %11 := [[1, %10], [%7, [k - 3, 0]], [%7, [k - 3, 0]], [%7, [k - 3, 0]], %1, [k - 4, [k, 0]]] %12 := [k - 1, [k - 3, 1]] %13 := [1, [[1, [k - 3, 2]], %12, [1, %9], %4, [k - 4, [k - 2, 1]]]] %14 := [1, [%13, [k, %9], [1, %10], [1, %10], %5, [k - 4, [k - 1, 1]]]] %15 := [1, [%14, [k + 1, %10], [1, %11], [1, %11], [1, %11], %6, [k - 4, [k, 1]]]] 2 %16 := [k - k, [k - 2, 0]] %17 := [[1, [k - 2, 1]], [k - 1, [k - 2, 0]], %8, [k - 3, [k - 1, 0]]] %18 := [[1, %17], %16, %16, [%7, [k - 3, 0]], [k - 3, [k, 0]]] %19 := [[1, [k - 2, 2]], [k, [k - 2, 1]], [1, %17], [1, %10], [k - 3, [k - 1, 1]]] %20 := [[1, %19], [k + 1, %17], [1, %18], [1, %18], [1, %11], [k - 3, [k, 1]]] %21 := [[1, [k - 1, 1]], [k, [k - 1, 0]], %16, [k - 2, [k, 0]]] 2 %22 := [k + k, [k - 2, 1]] %23 := [[1, %19], [k + 1, %17], %22, [1, %18], [1, %11], [k - 3, %21]] 2 %24 := [k - k, [k - 3, 1]] %25 := [[1, [k - 2, 2]], [k, [k - 2, 1]], %24, [1, %10], [k - 3, %17]] %26 := [k + 1, [k - 2, 2]] %27 := [1, [[1, [k - 2, 3]], %26, [1, %25], [1, %19], %14, [k - 3, [k - 1, 2]]]] %28 := [k + 1, [k - 1, 1]] %29 := [[1, [k - 1, 2]], %28, [1, %21], [1, %18], [k - 2, [k, 1]]] %30 := [[1, [k - 1, 2]], %28, %22, [1, %18], [k - 2, %21]] %31 := [k + 2, [k - 1, 2]] 3 %32 := [k - k, [k - 3, 1]] %33 := [[1, %25], %22, %22, %32, [1, %11], [k - 3, %18]] %34 := [[1, [k - 1, 3]], %31, [1, %30], [1, %33], [1, %20], [k - 2, %29]] 2 %35 := [k + 3 k + 2, [k - 2, 2]] %36 := [[1, [k - 1, 3]], %31, %35, [1, %33], [1, %23], [k - 2, %30]] %37 := [k + 3, [k - 1, 3]] %38 := [1, [ 2 [1, [[1, [k - 3, 2]], %12, [k - 3 k + 2, [k - 4, 1]], %4, [k - 4, %9]]], %24, %24, [%7, [k - 4, 1]], %5, [k - 4, %10]]] %39 := [1, 4 3 2 [%38, %32, %32, %32, [k - 2 k - k + 2 k, [k - 4, 1]], %6, [k - 4, %11]]] %40 := [1, [[1, [k - 2, 3]], %26, [1, %25], %38, %14, [k - 3, %19]]] %41 := [1, [%13, [k, %9], %24, [1, %10], %5, [k - 4, %17]]] This implies the recurrence 2 3 4 3 V(5)(k) = V(4)(k) k + V(2)(k) k + V(1)(k) k + V(0)(k) k + 3 V(1)(k - 1) k 4 4 5 3 + V(1)(k - 2) k + k V(0)(k - 1) + V(0)(k - 2) k + V(2)(k - 2) k 2 5 4 + 5 V(2)(k - 1) k + 6 V(0)(k - 3) k + 4 V(1)(k - 3) k 5 4 5 + 15 V(0)(k - 4) k + 5 V(1)(k - 4) k + 14 V(0)(k - 5) k 3 4 3 2 + 2 V(2)(k - 3) k - 98 V(0)(k - 5) k + 7 V(0)(k) k + 20 V(1)(k - 1) k 3 3 4 + 13 V(1)(k - 2) k + 24 k V(0)(k - 1) + 14 V(0)(k - 2) k 4 2 + 52 V(0)(k - 3) k + 41 V(0)(k - 4) k + 800 V(0)(k - 4) k 3 3 4 - 315 V(0)(k - 4) k + 28 V(1)(k - 3) k + 29 V(0)(k - 4) k 2 3 2 - 12 k V(0)(k - 1) + 8 V(0)(k - 2) k - 17 V(0)(k) k - V(2)(k) k 2 + 7 V(3)(k - 1) k + 10 V(2)(k - 2) k + 54 V(2)(k - 2) k 2 + 26 V(1)(k - 3) k + 64 V(1)(k - 3) k - 42 V(1)(k - 1) k 2 - 2 V(0)(k - 2) k - 307 V(0)(k - 2) k - 13 V(1)(k) k + 12 V(2)(k - 1) k 2 2 + 55 V(1)(k - 2) k + 39 V(1)(k - 2) k - 122 V(0)(k - 3) k 3 + 200 V(0)(k - 3) k - 92 V(0)(k - 3) k - 259 k V(0)(k - 1) - 63 V(0)(k) k 2 2 - 25 V(1)(k - 4) k + 210 V(0)(k - 5) k - 434 V(0)(k - 5) k 3 2 + 140 V(0)(k - 5) k + V(3)(k) k + V(4)(k - 1) k + V(3)(k - 2) k 2 + 5 V(3)(k - 2) k + 8 V(2)(k - 3) k + 6 V(2)(k - 3) k - 410 V(0)(k - 3) - 2 V(3)(k) + 12 V(3)(k - 1) - 138 V(1)(k - 2) - 22 V(2)(k - 1) - 252 V(0)(k - 2) - 6 V(1)(k) - 81 V(1)(k - 1) - 68 V(0)(k - 1) 2 - 4 V(2)(k) + 8 V(0)(k) + 2 V(1)(k) k + 90 V(1)(k - 4) + 168 V(0)(k - 5) + 35 V(2)(k - 2) - 36 V(1)(k - 3) - 258 V(0)(k - 4) - V(4)(k) + 8 V(4)(k - 1) + V(5)(k - 1) + 15 V(3)(k - 2) + 28 V(2)(k - 3) and the statement follows by induction. QED This ends this article, that took, 3351.041, seconds to generate.