数学代写|Math401 Combinatorics

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）

The theorem is true when $k=2$ by the binomial theorem with $x=y_1$ and $y=y_2$. Suppose that $k>2$ and that the theorem is true for $k-1$. Using the hint and the binomial theorem with $x=y_k$ and $y=y_1+y_2+\cdots+y_{k-1}$, we have that
$$
\left(y_1+y_2+\cdots+y_k\right)^n=\sum_{j=0}^n\left(\begin{array}{l}
n \
j
\end{array}\right)\left(y_1+y_2+\cdots+y_{k-1}\right)^{n-j} y_k^j .
$$
Thus the coefficient of $y_1^{m_1} \cdots y_k^{m_k}$ in this is $\left(\begin{array}{c}n \ m_k\end{array}\right)=n ! /\left(n-m_k\right) ! m_{k} !$ times the coefficient of $y_1^{m_1} \cdots y_{k-1}^{m_{k-1}}$ in $\left(y_1+y_2+\cdots+y_{k-1}\right)^{n-m_k}$. When $n-m_k=m_1+m_2+\cdots+m_{k-1}$ the coefficient is $\left(n-m_k\right) ! / m_{1} ! m_{2} ! \cdots m_{k-1} !$ and otherwise it is zero by the induction assumption. Multiplying by $\left(\begin{array}{c}n \ m_k\end{array}\right)$, we obtain the theorem for $k$.

Let $L(n, k)$ be the number of ordered $k$-lists without repeats that can be made from an $n$-set $S$. Form such a list by choosing the first element AND then forming a $k-1$ long list using the remaining $n-1$ elements. This gives $L(n, k)=n L(n-1, k-1)$.

Single out one item $x \in S$. There are $L(n-1, k)$ lists not containing $x$. If $x$ is in the list, it can be in any of $k$ positions AND the rest of the list can be constructed in $L(n-1, k-1)$ ways. Thus
$$
L(n, k)=L(n-1, k)+k L(n-1, k-1) .
$$

The only way to partition an $n$ element set into $n$ blocks is to put each element in a block by itself, so $S(n, n)=1$. The only way to partition an $n$ element set into one block is to put all the elements in the block, so $S(n, 1)=1$.

The only way to partition an $n$ element set into $n-1$ blocks is to choose two elements to be in a block together an put the remaining $n-2$ elements in $n-2$ blocks by themselves. Thus it suffices to choose the 2 elements that appear in a block together and so $S(n, n-1)=\left(\begin{array}{l}n \ 2\end{array}\right)$.

The formula for $S(n, n-1)$ can also be proved using (1.8) and induction. The formula is correct for $n=1$ since there is no way to partition a 1-set and have no blocks. Assume true for $n-1$. Use the recurion, the formula for $S(n-1, n-1)$ and the induction assumption for $S(n-1, n-2)$ to obtain
$$
S(n, n-1)=S(n-1, n-2)+(n-1) S(n-1, n-1)=\left(\begin{array}{c}
n-1 \
2
\end{array}\right)+(n-1) 1=\left(\begin{array}{l}
n \
2
\end{array}\right),
$$
which completes the proof.

Now for $S(n, 2)$. Note that $S(n, k)$ is the number of unordered lists of length $k$ where the list entries are nonempty subsets of a given $n$-set and each element of the set appears in exactly one list entry. We will count ordered lists, which is $k$ ! times the number of unordered ones. We choose a subset for the first block (first list entry) and use the remaining set elements for the second block. Since an $n$-set has $2^n$, this would seem to give $2^n / 2$; however, we must avoid empty blocks. In the ordered case, there are two ways this could happen since either the first or second list entry could be the empty set. Thus, we must have $2^n-2$ instead of $2^n$.

Here is another way to compute $S(n, 2)$. Look at the block containing $n$. Once it is determined, the entire two block partition is determined. The block one of the $2^{n-1}$ subsets of $n-1$ with $n$ adjoined. Since something must be left to form the second block, the subset cannot be all of $n-1$. Thus there are $2^{n-1}-1$ ways to form the block containing $n$.

The formula for $S(n, 2)$ can also be proved by induction using the recursion for $S(n, k)$ and the fact that $S(n, 1)=1$, much as was done for $S(n, n-1)$.

There are $\left(\begin{array}{l}n \ k\end{array}\right)$ ways to choose the subset AND $k$ ways to choose an element in it to mark. This gives the left side of the recursion times $k$. On the other hand, there are $n$ ways to choose an element to mark from ${1,2, \ldots, n}$ AND $\left(\begin{array}{c}n-1 \ k-1\end{array}\right)$ ways to choose the remaining elements of the $k$-element subset.

MY-ASSIGNMENTEXPERT™可以为您提供CATALOG MATH401 COMBINATORICS组合学的代写代考和辅导服务！