Problem 1.

In a string, distance between two symbols is the number of symbols between them plus one. For example, in a string $x y y x, y$ is at distance 1 from another $y,$ and $x$ is at distance 3 from another $x$. Find the number of $X$ -strings, with $|X|=k,$ of length $n$, such that the minimal distance between any two identical symbols is $\mathrm{k}$.

Proof .

Problem 2.

For a given positive integer $k,$ a quadratic polynomial with bounded integer coefficients has the form $P(x)=a x^{2}+b x+c,$ where $a, b, c$ are integers in the range $[-k, k] .$ There are $2 \mathrm{k}(2 \mathrm{k}+1)^{2}$ of these $-$ note that $\mathrm{a}$ cannot be $0 .$ Show that there are $\mathrm{k}(3 \mathrm{k}+1)$ of these polvnomials which have 1 as a root, that is, with $P(1)=0$.

Proof .

$$P(x)=(x-1)(sx+t)$$

pick定理的证明也不难，只需要对simplex证明然后拼起来。

Problem 3.

Show that, if the minimal number of edges that can be removed from an Eulerian graph G so that it stays Eulerian is $k, G$ has a subgraph isomorphic to the cyclic graph $\mathrm{C}_{\mathrm{k}}$

Proof .

Problem 4.

Let $f(n)$ denote the number of ways to cover a $2 \times n$ rectangle with $n$ rectangles of size $2 \times 1$ that are blue or red. Give a combinatorial proof that
$$f(2 k+1)=2 f(k)^{2}+8 f(k) f(k-1)$$

Problem 5.

In the group stage of a tournament, 32 teams are separated into 8 groups of $4 .$ Every team plays each other team in their group twice, playing 6 games total. Games may end in a tie. Show that there will be two teams with the same win-loss-tie record.

Problem 6.

If a $6 \times 6$ matrix contains 19 zeros, show that there are 4 zeros which are all in distinct rows and columns.

Problem 7.

n people participate in a costumed party with $n$ different costumes. Each person likes exactly two costumes, and each costume is liked by exactly two people. Prove that it is possible to match each person with a costume they like.

Hall定理

##### Introduction to Combinatorics Midterm assignment

Theory 太多 …Practice题目有点hold 不住？

MAT344H1S代写，Introduction to Combinatorics代写组合数学代写请认准UprivateTA™. UprivateTA™为您的留学生涯保驾护航。