MY-ASSIGNMENTEXPERT™可以为您提供catalog Math401 Combinatorics组合学的代写代考和辅导服务！
这是密西西比大学 组合学课程的代写成功案例。
Math401课程简介
This course explores the counting methods of Math 301 in further depth. Additional topics may include Ramsey theory, combinatorial designs, graph theory, matroid theory, and other related topics.
3 Credits
PREREQUISITES
Math 301: Discrete Mathematics (Minimum grade: C)
Pre-Requisite: 24 Earned Hours
Prerequisites
The policies and regulations contained in this online University of Mississippi Catalog are in effect for the current or selected semester. The catalog is not a contract, but rather a guide for the convenience of students. The University of Mississippi reserves the right to 1) change or withdraw courses; 2) change the fees, rules, and schedules for admission, registration, instruction, and graduation; and 3) change other regulations affecting the student body at any time. Implicit in each student’s enrollment with the university is an agreement to comply with university rules and regulations, which the university may modify to exercise properly its educational responsibility.
Math401 Combinatorics HELP（EXAM HELP， ONLINE TUTOR）
Without using the formula for $M(n, k)$, prove that $M(n, k)=M(n-1, k)+M(n, k-1)$. What are the initial conditions for this recursion?
To form an unordered list of length $k$ with repeats from ${1,2, \ldots, n}$, either form a list without $n$ OR form a list with $n$. The first can be done in $M(n-1, k)$ ways. The second can be done by forming a $k-1$ element list AND then adjoining $n$ to it. This can be done in $M(n, k-1) \times 1$ ways.
Initial conditions: $M(n, 0)=1$ for $n \geq 0$ and $M(0, k)=0$ for $k>0$.
Prove that $M(n, k)$ is the number of ways to place $k$ indistinguishable balls into $n$ boxes.
Hint. If you have $n=7$ boxes and $k=8$ balls, the list $1,1,1,2,4,4,4,7$ can be interpreted as “Place three balls in box 1 , one ball in box 2 , three balls in box 4 and one ball in box $7 . “$
Let the elements of the set be “place a ball in box $i$ ” for $1 \leq i \leq n$. Select $k$ elements and do what they say. Clearly each placement arises exactly once this way.
Prove that the number of unordered $k$-lists made from $n$ different items and using each item at most twice is the coefficient of $x^k$ in $\left(1+x+x^2\right)^n$. Generalize this.
As in the text, consider a term in the sum obtained by expanding
$$
\left(1+x_1+x_1 x_1\right)\left(1+x_2+x_2 x_2\right) \cdots\left(1+x_n+x_n x_n\right)
$$
using the distributive law. The number of times $x_i$ appears in the term is the number of balls in box $i$. Thus box $i$ never has more than two balls. The total number of all kinds of $x_$ ‘s in the term is the number of balls. Replacing all $x_$ ‘s with $x$ ‘s makes the number of $x$ ‘s the number of balls in that particular placement. Suppose each box can contain up to $j$ balls. Instead of $1+x+x^2$, we now have $1+x+x^2+\cdots+x^j$.
Let $f(b, t)$ be the number of ways to put $b$ labeled balls into $t$ labeled tubes. When balls are put into tubes the order matters: because the diameter of the tube is only slightly larger than that of the balls, the balls end up stacked on top of each other in a tube.
(a) Prove by induction on $b$ that $f(b, t)=t(t+1) \cdots(t+b-1)$. (To do this, you will first need a recursion for $f(b, t)$.)
Hint. There are at least two ways to get a recursion on $b$ : (i) insert $b-1$ balls and then the last or (ii) insert the first ball and then the remaining $b-1$.
(b) Give a noninductive combinatorial proof of the formula for $f(b, t)$.
(a) We give two solutions. Both use the idea of inserting a ball into a tube in an arbitrary position. To physically do this may require some manipulation of balls already in the tube.
Insert $b-1$ balls into the tubes AND then insert the $b^{\text {th }}$ ball. There are $i+1$ possible places to insert this ball in a tube containing $i$ balls. Summing this over all $t$ tubes gives us $(b-1)+t$ possible places to insert the $b^{\text {th }}$ ball. We have proved that
$$
f(b, t)=f(b-1, t)(b+t-1) .
$$
Since $f(1, t)=t$, we can establish the formula by induction.
Alternatively, we can insert the first ball AND insert the remaining $b-1$ balls. The first ball has the effect of dividing the tube in which it is placed into two tubes: the part above it and the part below. Thus
$$
f(b, t)=t f(b-1, t+1),
$$
and we can again use induction.
(b) We give two solutions:
Construct a list of length $t+b-1$ containing each ball exactly once and containing $t-1$ copies of “between tubes.” This can be done in $\left(\begin{array}{c}t+b-1 \ t-1\end{array}\right) b$ ! ways – choose the “between tubes” and then permute the balls to place them in the remaining $b$ positions in the list.
Alternatively, imagine an ordered $b+t-1$ long list. Choose $t-1$ positions to be divisions between tubes AND choose how to place the $b$ balls in the remaining $b$ positions. This gives $\left(\begin{array}{c}b+t-1 \ t-1\end{array}\right) \times b !$
MY-ASSIGNMENTEXPERT™可以为您提供CATALOG MATH401 COMBINATORICS组合学的代写代考和辅导服务！
