Assignment 4

Let n be a positive integer. Suppose that n persons are sitting on a straight line. Let us number the persons as 1,2,...,n in the order they appear on the line. The persons are very quarrelsome and fight whenever they are close to one another. A subcollection of these n persons is said to be nonbelligerent if the subcollection does not contain any two consecutive persons, i.e., persons i and i+1 for some value of i. The empty subcollection is also treated as nonbelligerent. Let L_n denote the number of of nonbelligerent subcollections of n persons on a line. These collections together with L_n for some small values of n are given in the next table.

n	Nonbelligerent collections on a line	Ln
1	Empty,{1}	2
2	Empty,{1},{2}	3
3	Empty,{1},{2},{3},{1,3}	5
4	Empty,{1},{2},{3},{4},{1,3},{2,4},{1,4}	8
5	Empty,{1},{2},{3},{4},{5},{1,3},{2,4},{3,5},{1,4},{2,5},{1,5},{1,3,5}	13

Write a recursive function in order to compute the value of L_n. The function should take two arguments: n and the last person l chosen so far. The next choice must be one from l+2,...,n. For each such choice m, pass n and m to a recursive call. Another possibility is that no other person is chosen in the collection at all. Take a sum of the counts from all possibilities and return the sum. The outermost call of the recursive function in the main() function must pass a suitable value for the second parameter.

Next suppose that the persons are sitting on a circle, so that persons 1 and n are now adjacent to one another. Let C_n denote the number of nonbelligerent subcollections of n persons in a circle. The following table summarizes some small values.

n	Nonbelligerent collections on a circle	Cn
1	Empty,{1}	2
2	Empty,{1},{2}	3
3	Empty,{1},{2},{3}	4
4	Empty,{1},{2},{3},{4},{1,3},{2,4}	7
5	Empty,{1},{2},{3},{4},{5},{1,3},{2,4},{3,5},{1,4},{2,5}	11

Write a second recursive function for computing the value of C_n. Here break the computation in two parts according as whether the first person is chosen or not. In addition to n and the last person l chosen so far, you should also pass an indicator (flag) about the choice of the first person.

You are not asked to find out the nonbelligerent collections themselves (Solve Assignment 5 for that). You are asked only to compute their counts. These counts can be obtained in a variety of ways. Here I urge you strongly (almost force you) to follow the recursive strategy outlined above. This will help you in understanding recursive behavior of functions. Following other algorithms may defeat this basic purpose.

Report the values of L_n and C_n for n=20,25,30,35.

Sample output

Enter number of persons : 10
Number of nonbelligerent collections in a line   = 144
Number of nonbelligerent collections in a circle = 123

Enter number of persons : 15
Number of nonbelligerent collections in a line   = 1597
Number of nonbelligerent collections in a circle = 1364

Mathematical challenge: (Not for submission)

Find closed-form formulas for L_n and C_n.

---

[Submission site] [Lab home] [Course home]