Question

(i) T(n) denote the number of distinct ways that a postage of n cents, where n ≥ 4 and n is even, can be made by 4-cent and 6-cent stamps. Give a recursive algorithm (written in Python) to compute T(n) for n ≥ 4 and n is even. Briefly explain why the algorithm is correct but no formal proof is required. NOTE [4,6] is the same as [6,4] so T(10) = 1.
(ii) Now assume we have 10-cent stamps in addition to the previous 2 kinds. Find a recurrence relation, S(n), for the number of distinct ways that a postage of n cents, where n ≥ 4 and n is even, can be made by 4-cent, 6-cent and 10-cent stamps.

Answer 1

1. For the first case, when the allowed stamps are of 4 and 6 cents:
    The recurrence relation mathematically can be defined as follows:
T(0) = 1
T(<0) = 0
T(n) = T(n-4) + T(n-6)
where n = postage amount provided in input.
But to be more specific and remove repetitive ways, it needs to be defined with some conditions for more valid solutions:

Code in python:

# Returns the number of ways we can use
# [4,6] cent stamps to get the sum of postage
def func(stamps, m, postage ):

    # If postage = 0 then there is 1
    # solution (do not include any stamp)
    if postage == 0 :
        return 1

    # If postage< 0 then no
    # solution is possible
    if (postage < 0):
        return 0;

    # If there are no stamps and postage
    # is more than 0, then no
    # solution is possible
    if (m <=0 and postage >= 1):
        return 0

    # func is sum of ways (i)
    # including 4 or 6 (i.e. s[i]) (ii) excluding 4 or 6 (i.e. s[i])
    return func( stamps, m - 1, postage ) + func( stamps, m, postage-stamps[m-1] );

# Driver program to check above code
arr = [4,6]
m = len(arr)
print(func(arr, m, 12))

To prove the solution to be correct:

This type of recurrence is as same as that of the coin change problem solved using dynamic programming. Here by using the stamps array and a pointer to it, we ensure that once we done iterated using the current stamp amount at m position so that no two similar combinations will be there and we can proceed with the next stamp amount. To dry run the above solution:

for input of func(10):

2. As we have used a more generic solution above, hence now we can adjust the soltion code for the case of present stamps of 4,6 ans 10 cents by changing the stamps to have [4,6,10] stamps values, as changes done in driver code below :

# Driver program to check above code
# Returns the number of ways we can use
# [4,6,10] cent stamps to get the sum of postage
arr = [4,6,10]
m = len(arr)
print(func(arr, m, 12))