## CS13002 Programming and Data Structures | ## Section: 5/E, Spring 2006 |

## Assignment 4

Let

nbe a positive integer. Suppose thatnpersons 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 thesenpersons is said to benonbelligerentif the subcollection does not contain any two consecutive persons, i.e., personsiandi+1 for some value ofi. The empty subcollection is also treated as nonbelligerent. LetLdenote the number of of nonbelligerent subcollections of_{n}npersons on a line. These collections together withLfor some small values of_{n}nare given in the next table.

nNonbelligerent collections on a line L_{n}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

in order to compute the value ofrecursive functionL. The function should take two arguments:_{n}nand the last personlchosen so far. The next choice must be one froml+2,...,n. For each such choicem, passnandmto 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 themain()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

nare now adjacent to one another. LetCdenote the number of nonbelligerent subcollections of_{n}npersons in a circle. The following table summarizes some small values.

nNonbelligerent collections on a circle C_{n}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

for computing the value ofrecursive functionC. Here break the computation in two parts according as whether the first person is chosen or not. In addition to_{n}nand the last personlchosen 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

Land_{n}Cfor_{n}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

Land_{n}C._{n}