19th Ave New York, NY 95822, USA

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

这是MAT344H1S,Introduction to Combinatorics的一次作业分析,相关内容可以参考Toronto大学那个链接。

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

证明 .


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

证明 .





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

证明 .

这个题的claim的逆命题是显然的,同时我们也可以得到,这个图不可能包含$C_t$,对任意$1\leq t\leq k-1$成立。

难度在于怎么证明一定包含$C_k$,现在我们设想一个图,这个图可以一笔画,但是不包含所有的$C_t$,$1\leq t\leq k-1$,同时他去掉k个边还可以一笔画,这k个边一定得要是联通的,否则会和k的最小性矛盾。



问题 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)


问题 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.


问题 6.

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



问题 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.


Introduction to Combinatorics Midterm assignment

上课听不懂lecturer ?


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


Math 130A代写请认准UpriviateTA

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


Related Posts

Comments (2)

Leave a comment