Explore BrainMass
Share

# Challenge problems based on combinatorics theory

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

Solve the following challenge problems based on combinatorics theory - partitions and ordered and unordered arrangements. See the attached file for the formatted equations/notations.

1) Natural Number Partitions (do parts a and b): When we are counting surjective functions and both the n balls and the x boxes are indistinct, we have an integer partition, which we designate . We can think of placing n identical books into x identical boxes - we are only interested in the total number of books in each box. For example,; the possibilities for the number of books in the boxes are: 1,1,5; 1,2,4; 1,3,3; and 2,2,3.

b. State a recursive equation, and give a combinatorial proof. Be sure to include the initial conditions (base cases).

c. Use your table to compute the total number of partitions of each n. Then compute the coefficients of in the following:

d. What is the connection between the coefficients of the various powers of x and the total number of partitions? Why? Note that there is not a simple explicit formula for the number of natural number partitions like there is for set partitions. This approach is called using a generating function and it's a very important approach in combinatorics.

e. Extend the equation in part c so that it accurately counts the total number of partitions up to the coefficient of . Compute and compare to your table. Use a CAS for this. The straightforward way (with some typing) in Wolfram alpha is to just type "Expand" and then your polynomial; you can use notation like x^2. However, you can also write each term as an infinite geometric series (the very big terms won't matter) and then use other commands to save typing - explore (I was able to evaluate with half a line of typing; feel free to look up CAS documentation).