Purchase Solution

Challenge problems based on combinatorics theory

Not what you're looking for?

Ask Custom Question

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).

Purchase this Solution

Solution Summary

Solving challenging problems from combinatorics theory

Solution provided by:
Education
  • BSc, University of Bucharest
  • MSc, Ovidius
  • MSc, Stony Brook
  • PhD (IP), Stony Brook
Recent Feedback
  • "Thank you "
  • "Thank You Chris this draft really helped me understand correlation."
  • "Thanks for the prompt return. Going into the last meeting tonight before submission. "
  • "Thank you for your promptness and great work. This will serve as a great guideline to assist with the completion of our project."
  • "Thanks for the product. It is an excellent guideline for the group. "
Purchase this Solution


Free BrainMass Quizzes
Multiplying Complex Numbers

This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.

Solving quadratic inequalities

This quiz test you on how well you are familiar with solving quadratic inequalities.

Know Your Linear Equations

Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.

Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.

Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts