Let g(n,k) be the number of partitions of n into exactly k parts, in which no part is a 1. Show that \(g(n,k) = g(n-2,k-1) + g(n-k,k).\)

Guest Nov 18, 2019

#1**0 **

Let f(n,k) be the number of partitions of n with k parts.

Consider a partition of n with k parts. By definition, there are g(n,k) is the number of partitions with n with k parts with no 1s. For a partition of n with k parts, we can add i 1s, to get a partition of n with k parts, so g(n,k) = f(n,k) + i.

Consider a partition of n with k - 1 parts. By definition, there are g(n,k - 1) is the number of partitions with n with k - 1 parts with no 1s. For a partition of n with k - 1 parts, we add (i - 1) 1s, to get a partition of n with k - 1 parts, so g(n,k) = f(n,k) + i - 1.

Consider a partition of n - k with k parts. By definition, there are g(n - k,k) is the number of partitions with n - k with k parts with no 1s. For a partition of n with k parts, we add i 1s, to get a partition of n - k with k parts, so g(n - k,k) = f(n,k) + i.

So the equation g(n,k) = g(n,k - 1) + g(n - k,k) becomes f(n,k) + i = f(n,k - 1) + (i - 1) + f(n - k,k) + i, or g(n,k) = g(n,k - 1) + g(n - k,k) + (i - 1).

Guest Nov 18, 2019