MY-ASSIGNMENTEXPERT™可以为您提供caltech Math121a Combinatorics组合学的代写代考和辅导服务！
这是加州理工学院组合学课程的代写成功案例。
Math121a课程简介
Math 121 is our standard three-term course on combinatorics though we are only able to offer two terms this year. The first term covers “structural” combinatorics, the study of interesting discrete structures, both in terms of general properties as well as in terms of the existence or classification of particularly nice or extreme instances. We will spend much of the term on graphs and related topics such as Ramsey theory, with the remainder of the term spent covering other important structures Latin squares, codes, designs, finite geometries, etc.. The second term will cover more quantititative aspects of combinatorics, as well as applications to and from algebra.
Prerequisites
Grades: Grades will be assessed on the basis of homeworks, which will be given roughly biweekly. There will be no exams (or midterms). Students may discuss problems with each other but have to write down the solutions independently.
The following restrictions hold for all problems of the set: Students may ask questions to the TA (if one exists) and the professor. Resources which you may use while working on the homework include any books and non-interactive websites (i.e. no posting of the questions on internet fora). For calculations which you can do by hand, you may use a computer algebra program Mathematica, Maple, etc.; you may also fell free to use a computer to gain intuition say by solving small instances of the problems, so long as your eventual proof does not depend on such a computation. If you use significant ideas from any source, other than the books mentioned on this website, you should mention where you got them from.
Math121a Combinatorics HELP（EXAM HELP， ONLINE TUTOR）
By 2001 spelling has deteriorated considerably. The dictionary defines the spelling of “relief” to be any combination (with repetition allowed) of the letters $\mathrm{R}, \mathrm{L}, \mathrm{F}, \mathrm{I}$ and $\mathrm{E}$ subject to certain constraints listed below How many spellings are possible? The most popular spelling is the one that, in dictionary order, is five before the spelling RELIEF. What is it?
(i) The number of letters must not exceed 6 .
(ii) The word must contain at least one L.
(iii) The word must begin with an $\mathrm{R}$ and end with an $\mathrm{F}$.
(iv) There is just one $R$ and one $F$.
Stripping off the initial $\mathrm{R}$ and terminal $\mathrm{F}$, we are left with a list of at most 4 letters, at least one of which is an L. There is just 1 such list of length 1 . There are $3^2-2^2=5$ lists of length 2 , namely all those made from E, I and L minus those made from just E and I. Similarly, there are $3^3-2^3=19$ of length 3 and $3^4-2^4=65$. This gives us a total of 90 .
The letters used are $\mathrm{E}, \mathrm{F}, \mathrm{I}, \mathrm{L}$ and $\mathrm{R}$ in alphabetical order. To get the word before RELIEF, note that we cannot change just the $\mathrm{F}$ and/or the $\mathrm{E}$ to produce an earlier word. Thus we must change the I to get the preceding word. The first candidate in alphabetical order is $\mathrm{F}$, giving us RELF. Working backwards in this manner, we come to RELELF, RELEIF, RELEF and, finally, RELEEF.
Prove that the number of ordered lists without repeats that can be constructed from an $n$-set is very nearly $n$ !e. The lists can be of any length.
Hint. Recall that from Taylor’s Theorem in calculus $e^x=1+x+x^2 / 2 !+x^3 / 3 !+\cdots$.
There are $n ! /(n-k)$ ! lists of length $k$. The total number of lists (not counting the empty list) is
$$
\frac{n !}{(n-1) !}+\frac{n !}{(n-2) !}+\cdots+\frac{n !}{1 !}+\frac{n !}{0 !}=n !\left(\frac{1}{0 !}+\frac{1}{1 !}+\cdots+\frac{1}{(n-1) !}\right)=n ! \sum_{i=0}^{n-1} \frac{1^i}{i !}
$$
Since $e=e^1=\sum_{i=0}^{\infty} 1^i / i$ !, it follows that the above sum is close to $e$.
This exercise contains several related questions. In each case we would like a formula that answers the question “How many ways can $p$ people run for $k$ offices?” under the given constraints. Unless the constraints say otherwise, a person may run for no offices. At present, we have the tools to do only two parts of this exercise. The challenge in this exercise is to avoid finding wrong “solutions” to the parts that we are unable to do, as well as doing the two parts we can do now. One way you can check your “solution” is to actually list all the possible ways $p$ people can run for $k$ offices for each of the parts for some small values of $p$ and $k$. We will return to this exercise later as we develop tools for doing other parts of it.
(a) Each person must be a candidate for at most one office.
(b) Each person must be a candidate for exactly one office and each office must have at least one candidate.
(c) Each person must be a candidate for at most one office and each office must have at least one candidate.
(d) Each person can be a candidate for any number of offices (including none) and each office must have at least one candidate.
(e) Each person must be a candidate for at least one office and each office must have at least one candidate.
We can only do parts (a) and (d) at present.
(a) A person can run for one of $k$ offices or for nothing, giving $k+1$ choices per person. By the Rule of Product we get $(k+1)^p$.
(d) We can treat each office separately. There are $2^p-1$ possible slates for an office: any subset of the set of candidates except the empty one. By the Rule of Product we have $\left(2^p-1\right)^k$.
Suppose that $k$ and $n-k$ both get large as $n$ gets large. Use Stirling’s formula to show that
$$
\left(\begin{array}{l}
n \
k
\end{array}\right) \sim \frac{1}{\sqrt{2 n \pi \lambda(1-\lambda)}}\left(\frac{1}{\lambda^\lambda(1-\lambda)^{1-\lambda}}\right)^n \quad \text { where } \lambda=k / n .
$$
After recognizing that $k=n \lambda$ and $n-k=n(1-\lambda)$, it’s simply a matter of algebra.
MY-ASSIGNMENTEXPERT™可以为您提供CALTECH MATH121A COMBINATORICS组合学的代写代考和辅导服务！
