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

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 .

这个题就是用韦达定理,为1是一个根的多项式具有这种形式

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

然后就可以算出来所有的满足条件的多项式有多少种,本质上变成了一个线性规划区域里面数整点的问题,一般的情况也可以用pick定理算出来有多少组解,pick定理在任何一本介绍凸体的书里面都会讲。

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 .

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

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

我们分析这k一条边的位置,根据Eulerian图的刻画定理,我们知道每个顶点出来的被去掉的图的degree都是偶数,我们的目标是证明,这个数是2,这个数不能超过2的理由是如果超过2,我们总是可以构造一个子图顶点数比k更小,然后原图去掉这个子图之后还是euler图。

所以这个图一定包含一个$C_k$.

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

如果不需要combinatorial证明的话可以直接进行一波归的递,组合证明我也不知道怎么找,不够聪明。

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.

极端情况是占满3行或者3然后多一个,一般情况可以对行用抽屉原理然后对列用Hall定理秒杀,不过Hall定理的证明要一页。。。

肯定有更简单的做法但是我一下没想到

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定理


MAT344H1S 
Introduction to Combinatorics Midterm assignment

上课听不懂lecturer ?

笔记也看不懂?

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

需要帮助,欢迎联系我们。


Math 130A代写请认准UpriviateTA

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

常微分方程代写可以参考一份常微分方程代写案例


2 Comments

数学代写|MAT344 Introduction to Combinatorics 代写 代写 | UprivateTA™代写答疑辅导 · 2021年2月26日 at 上午11:17

[…] MAT344H1S 的一次代写案例 […]

数学代写|MATH 319 Introduction to Partial Differential Equations|偏微分方程代写(baby course) 代写 | UprivateTA™代写答疑辅导 · 2021年2月26日 at 下午12:39

[…] 组合数学代写图论代写可以参考一份组合学assignment答案解析 […]

Comments are closed.