Assignment 3

---

[ Submission site  |  Show solution  |  Hide solution ]

---

Part 1 [Credit: 70%]

Let n be a positive integer. A partition of n is a way of writing n as a sum of positive integers. For example, all the partitions of 5 are:

   1+1+1+1+1
   1+1+1+2
   1+1+3
   1+2+2
   1+4
   2+3
   5

Permuting the summands in a partition does not give a new partition. For example, the partition 1+2+2 is treated the same as 2+1+2 and also as 2+2+1.

In this part, you are asked to compute the number of partitions of n. Write a recursive function to this effect. In order to avoid repetitions, we choose the summands in a non-decreasing order. That is, if 1 and 2 are already chosen as the previous summands, the next summand cannot be less than 2. Pass two arguments to your recursive function. The first stands for the amount left to be balanced by summands and the second stands for the largest summand chosen so far. Recursion stops when the first argument becomes 0. Here is a possible prototype for the function.

   unsigned long countP ( unsigned long balance , unsigned long minchoice );

Part 2 [Credit: 20%]

Repeat Part 1 with the added constraint that no summand is repeated in the partition. For example, only three out of the seven partitions of 5 correspond to no repetitions:

   1+4
   2+3
   5

Modify the recursive function of Part 1 slightly so as to generate the count of partitions without repetitions. A prototype for this function would be:

   unsigned long countPNoRep ( unsigned long balance , unsigned long minchoice );

Part 3 [Credit: 10%]

In this part, you are asked to compute the number of partitions having an odd number of summands. For example, four out of the seven patitions of 5 contain odd numbers of summands:

   1+1+1+1+1
   1+1+3
   1+2+2
   5

Modify the recursive function of Part 1 in order to count the number of partitions of n into odd number of summands. Pass a third argument to the function in order to pass the information about how many summands have been chosen so far. When the balance (first argument) becomes zero, check whether an odd number of summands have been chosen so far. If so, that choice contributes to the total count, else not. A possible prototype is:

   unsigned long countPOdd ( unsigned long balance , unsigned long minchoice , unsigned int nsummands );

Finally, here is a recommended main() function for your program.

   int main ()
   {
      unsigned long n;

      printf("Enter n: "); scanf("%lu", &n);

      printf("Count of all partitions                 = %lu\n", countP(n,1));
      printf("Count of partitions without repetitions = %lu\n", countPNoRep(n,1));
      printf("Count of partitions in odd no. of parts = %lu\n", countPOdd(n,1,0));
   }

Report the output of your program on the following values of n.

   6
   10
   25
   50
   100

Sample output

   Enter n: 5
   Count of all partitions                 = 7
   Count of partitions without repetitions = 3
   Count of partitions in odd no. of parts = 4

   Enter n: 40
   Count of all partitions                 = 37338
   Count of partitions without repetitions = 1113
   Count of partitions in odd no. of parts = 18646

   Enter n: 80
   Count of all partitions                 = 15796476
   Count of partitions without repetitions = 77312
   Count of partitions in odd no. of parts = 7897846

---

Solution

   #include <stdio.h>

   unsigned long countP ( unsigned long n , unsigned long m )
   {
      unsigned long i, s;

      if (n == 0) return 1;
      s = 0;
      for (i = m; i <= n; ++i) s += countP(n-i,i);
      return s;
   }

   unsigned long countPNoRep ( unsigned long n , unsigned long m )
   {
      unsigned long i, s;

      if (n == 0) return 1;
      s = 0;
      for (i = m; i <= n; ++i) s += countPNoRep(n-i,i+1);
      return s;
   }

   unsigned long countPOdd ( unsigned long n , unsigned long m , unsigned int t )
   {
      unsigned long i, s;

      if (n == 0) return ((t % 2) ? 1 : 0);
      s = 0;
      for (i = m; i <= n; ++i) s += countPOdd(n-i,i,t+1);
      return s;
   }

   int main ()
   {
      unsigned long n;

      printf("Enter n: "); scanf("%lu", &n); printf("%lu\n", n);

      printf("Count of all partitions                 = %lu\n", countP(n,1));
      printf("Count of partitions without repetitions = %lu\n", countPNoRep(n,1));
      printf("Count of partitions in odd no. of parts = %lu\n", countPOdd(n,1,0));
      printf("\n");
   }

Output

   Enter n: 6
   Count of all partitions                 = 11
   Count of partitions without repetitions = 4
   Count of partitions in odd no. of parts = 5

   Enter n: 10
   Count of all partitions                 = 42
   Count of partitions without repetitions = 10
   Count of partitions in odd no. of parts = 20

   Enter n: 25
   Count of all partitions                 = 1958
   Count of partitions without repetitions = 142
   Count of partitions in odd no. of parts = 985

   Enter n: 50
   Count of all partitions                 = 204226
   Count of partitions without repetitions = 3658
   Count of partitions in odd no. of parts = 102064

   Enter n: 100
   Count of all partitions                 = 190569292
   Count of partitions without repetitions = 444793
   Count of partitions in odd no. of parts = 95283359

---

[ Submission site  |  Show solution  |  Hide solution ]

---

Back  |  Home