6.18 Seating a large group at multiple tables

Suppose there is a group of n people to be seated at a two tables, the first with r chairs and the second with n - r chairs. We do not care who sits in which chair, just who sits at which table. The problem is to compute the number of different ways the people could be assigned to tables. One way of assigning them is to make them all stand in a line, and then assign the first r people in the line to the first table, and the remaining n-r people to the second one. The number of ways of ordering the people into a line is n! = n * (n-1) * (n-2) * ... * 3 * 2 * 1, because there are n possible choices for the first in line and for each of these, n - 1 choices for the second person in line, and so forth. But of these orderings, any way of rearranging the first r people in line (of which there are r! ways) results in the same table assignment, and similarly, each of the s! ways of rearranging the remaining s = n - r people left in line after the first r people have been seated also results in the same table assignment. So by dividing by the two factors r! and s! to account for these repetitions of the same table assignment, we get n! / ( r! * s!) total different table assignments.

Submit a program that starts with a function definition for factorial(n), which returns the number n! Then the main program should call that function three times to compute the number n! / ( r! * s!) of different table assignments. The program should prompt the use by "Enter the number of people" for the total number n of people, "Enter the number of chairs at table 1" to get the number r, and "Enter the number of chairs at table 2" to get s. Assume for now that r + s = n. It should then print the total number of different table assignments, preceded by the words "The number of table assignments is". This printed number should be in integer without a decimal point. This time the grading is not sensitive to white space, so extra spaces and new lines are OK (but not colons). So for the first test case, the interaction should look like:

Enter the number of people

6

Enter the number of chairs at table 1

3

Enter the number of chairs at table 2

3

The number of table assignments is 20

Next, enhance the program for more than two tables. Keep prompting for the number of chairs at tables until the number equals n. If the numbers of chairs at the tables are r, s, t, ...., x, the reasoning above shows that the number of different assignments is n!/ (r! * s! * t! * ... * x!). So and example interaction would be:

Enter the number of people

6

Enter the number of chairs at table 1

2

Enter the number of chairs at table 2

2

Enter the number of chairs at table 3

2

The number of table assignments is 90

Finally, enhance the program so that if the number of chairs r + s + t + .... + x after the latest user input exceeds n, the program will print "Seating only c people at table d" where the integer d is the last table index, and the integer c = n - ( r + s + t + .... + x) is the number of people actually needing seats at the last table, and then proceed as before, using c instead of the user-entered number x in the computation. So an example interaction would be:

Enter the number of people

6

Enter the number of chairs at table 1

2

Enter the number of chairs at table 2

2

Enter the number of chairs at table 3

3

Seating only 2 people at table 3

The number of table assignments is 90