We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive pseudonymised information about your use of our website. cookie policy and privacy policy.
 
+0  
 
0
42
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

30 Online Users

avatar
avatar
avatar