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）
Let $B_n$ be the total number of partitions of an $n$ element set. Thus
$$
B_n=S(n, 0)+S(n, 1)+\cdots+S(n, n) .
$$
(a) Prove that
$$
B_{n+1}=\sum_{i=0}^n\left(\begin{array}{l}
n \
i
\end{array}\right) B_{n-i},
$$
where $B_0$ is defined to be 1 .
Hint. Construct the block containing $n+1$ and then construct the rest of the partition.
(b) Calculate $B_n$ for $n \leq 5$.
(a) We use the hint. Choose $i$ elements of ${1,2, \cdots, n}$ to be in the block with $n+1$ AND either do nothing else if $i=n$ OR partition the remaining elements. This gives $\left(\begin{array}{l}n \ n\end{array}\right)$ if $i=n$ and $\left(\begin{array}{c}n \ i\end{array}\right) B_{n-i}$ otherwise. If we set $B_0=1$, the second formula applies for $i=n$, too. Since $i=0$ OR $i=1$ OR $\cdots$ OR $i=n$, the result follows.
(b) We have $B_0=1$ from (a). Using the formula in (a) for $n=0,1,2,3,4$ in order, we obtain $B_1=1, B_2=2, B_3=5, B_4=15$ and $B_5=52$.
We want to count the number of $n$ digit sequences that have no adjacent zeroes. The digits must be chosen from the set ${0,1, \ldots, d-1}$. For example, with $d=3$ and $n=4$, the sequences $0,2,1,0$ and $2,1,2,2$ are valid but $1,0,0,2$ and $1,3,2,3$ are not. Let the number of such sequences be $A_n$. (The case $d=2$ is called the Fibonacci numbers.)
(a) From an $n$-sequence, remove the last digit if it is nonzero and the last two digits if the last digit is zero. By reversing this process, describe a way to build up all acceptable sequences by adding elements one or two at a time.
(b) Use (a) to obtain a recursion of the form $A_n=a A_{n-1}+b A_{n-2}$. What are $a$ and $b$ ? For what $n$ is the recursion valid? What are the initial conditions?
(c) Compute $A_n$ for $n \leq 5$ when $d=10$.
When we speak of a sequence in this exercise, we mean a sequence having no adjacent zeroes whose entries are from ${0,1, \ldots, d-1}$. A sequence of length $n$ can be built from a sequence of length $n-1$ by adding something other than zero OR it can be built from a sequence of length $n-1$ that doesn’t end in zero by adding zero. (To see this, simply note what is left when you remove the last digit from a sequence of length $n$.) The sequences of length $n-1$ not ending in zero can all be built by adding something other than zero to a sequence of length $n-2$. Putting this all together by using the Rules of Sum and Product and noting that there are $d-1$ choices for a digit which is not zero, we get $A_n=(d-1) A_{n-1}+(d-1) A_{n-2}$. Since we refer to sequences of length $n-2$, we require that $n \geq 3$. The initial values are $A_1=d$ and $A_2=d^2-1$ since the 2 -sequences consist of everything except 0,0 . (If we define $A_0=1$, we could start the recursion at $n=2$.) When $d=10$, the values of $A_i$ for $1 \leq i \leq 5$ are $10,99,981,9720$ and 96309 .
How many multisets can be formed from a set $S$ if each element can appear at most $j$ times? Your answer should be a simple formula.
For each element, there are $j+1$ choices for the number of repetitions, namely anything from 0 to $j$, inclusive. By the Rule of Product, we obtain $(j+1)^{|S|}$.
It was stated in the preceding paragraph that “there’s no simple formula for the number of $k$-multisets if each element appears at most $j$ times except for $j=1$ and $j \geq k$.” What are the formulas for $j=1$ and $j \geq k$ ?
When $j=1$, we are simply talking about subsets so the answer is $\left(\begin{array}{c}|S| \ k\end{array}\right)$. Since a $k$-multiset contains $k$ things, when $j \geq k$, there is no restriction on repetition. Thus we are simply counting unrestricted multisets of which there are $\left(\begin{array}{c}|S|+k-1 \ k\end{array}\right)=\left(\begin{array}{c}|S|+k-1 \ |S|-1\end{array}\right)$.
MY-ASSIGNMENTEXPERT™可以为您提供CATALOG MATH401 COMBINATORICS组合学的代写代考和辅导服务！
