+0

0
98
2

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).\)

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).

Nov 18, 2019
#2
0

Therefore, g(n,k) = g(n - 2,k - 1) + g(n - k,k).

Guest Nov 18, 2019