数学代写|MAT344 Introduction to Combinatorics Midterm assignment. Due March 1,10: 00 pm|组合数学代写|图论代写

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}$.

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$.

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}}$

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)
$$

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.

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

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.