+0  
 
0
412
2
avatar

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
avatar
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
avatar
0

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

Guest Nov 18, 2019

4 Online Users

avatar
avatar