## 数学代写|组合数学代写Combinatorial mathematics代考|MATH4575

statistics-lab™ 为您的留学生涯保驾护航 在代写组合数学Combinatorial mathematics方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写组合数学Combinatorial mathematics代写方面经验极为丰富，各种代写组合数学Combinatorial mathematics相关的作业也就用不着说。

• Statistical Inference 统计推断
• Statistical Computing 统计计算
• (Generalized) Linear Models 广义线性模型
• Statistical Machine Learning 统计机器学习
• Longitudinal Data Analysis 纵向数据分析
• Foundations of Data Science 数据科学基础

## 数学代写|组合数学代写Combinatorial mathematics代考|Tiling by Linear Polyominoes

In this section we first solve the following problem.
Problem 4.1. Find all $m \times n$ rectangles that can be tiled with linear $\boldsymbol{k}$-ominoes (i.e., $1 \times k$ rectangular tiles).

Exercise 4.1. Prove that $m$ or $n$ is a multiple of $k$ then an $m \times n$ rectangle can be tiled by linear $k$-ominoes.

Theorem 4.1. (D.A. Klarner [Kl], A. Soifer [S3]) If neither of $m, n$ is a multiple of $k$ then the $m \times n$ rectangle is not tileable with linear $k$-ominoes.

First Proof. [S3] Assume that neither $m$ nor $n$ is a multiple of $k$, but that the board can be tiled with linear $k$-ominoes. Let us

color the board diagonally in $k$ colors with a cyclic permutation of colors (see Figures $4.1$ and 4.2).

This coloring (diagonal cyclic k-coloring) has a remarkable property: no matter how a linear $k$-omino is placed on the colored rectangle, horizontally or vertically, it will cover exactly one square of each of the $k$ colors.

Since by assumption the rectangle can be tiled using linear $k$ ominoes, and every $k$-omino covers an equal number of squares of every color, the rectangle must contain an equal number of squares of each of the $k$ colors. It is not difficult to prove (do!) that for any natural numbers $m$ and $k$ there are non-negative integers $q$ and $r_1$, such that $0 \leq r_1 \leq \frac{k}{2}$ and
$$m=k q+r_1$$

or
$$m=k q-r_1 .$$
Accordingly, we will consider two cases:
Case 1: $m=k q+r_1$. We cut the given rectangle into two rectangles that are $k q \times n$ and $r_1 \times n$. Since the $k q \times n$ rectangle can be tiled using linear $k$-ominoes, it contains an equal number of squares of each color. The given rectangle contains an equal number of squares of every color as well; therefore, the $r_1 \times n$ rectangle has the same property.

## 数学代写|组合数学代写Combinatorial mathematics代考|Tiling by Linear Polyominoes

It is easy to prove (do!) that $a_1 \equiv a_2(\bmod n)$ if and only if $a_1-a_2$ is a multiple of $n$.
Assume that neither of $m, n$ is a multiple of $k$, i.e.,
\begin{aligned} & m=k q_1+r_1 ; \quad 0<r_1<k, \ & n=k q_2+r_2 ; \quad 0<r_2<k, \ & \end{aligned}
but the $m \times n$ rectangle is tiled by linear $k$-ominoes.
Let us color the columns of the rectangle with one of each of the $k$ colors with cyclic permutation of colors (see Figures $4.1$ and 4.3) and denote by $S_1, S_2, \ldots, S_n$ the number of squares of the rectangle colored with the 1 st, 2 nd $, \ldots, k$-th colors respectively.

This coloring (column cyclic $\boldsymbol{k}$-coloring) has a nice property: if a linear $k$-omino is placed on the board vertically, it covers $k$ squares of the same color; if it is placed on the board horizontally, it covers exactly one square of every color. By assumption the rectangle is tiled by linear $k$-ominoes, therefore
$$S_1 \equiv S_2 \equiv \ldots \equiv S_k(\bmod k) .$$
On the other hand, notice that we have one column more of the $r_2$-th color than of the $\left(r_2+1\right)$ st color, i.e.,
$$S_{r_2}-S_{r_2+1}=m$$

Since $m$ is not divisible by $k$, this implies that the congruence
$$S_{r_2} \equiv S_{r_2+1}(\bmod k)$$
is false. The contradiction between $()$ and $( *)$ proves that the divisibility of $m$ or $n$ by $k$ is a necessary condition for the $m \times n$ rectangle to be tileable by linear $k$-ominoes. It is also sufficient (Exercise 4.1).

The above two solutions first appeared in Russian in Kvant [S3] written by the author while he was an undergraduate student. Much later these solutions appeared in English in [S1] and consequently [S9]. You may get the impression that this problem can only be solved with the aid of coloring. In fact, [S3] contained a third proof that required no coloring. It also contained a more complex problem, where to the unlimited collection of $1 \times k$ tiles the author added one, just one, monomino. Let us look at this problem.

# 组合数学代写

## 数学代写|组合数学代写Combinatorial mathematics代考|Tiling by Linear Polyominoes

$$m=k q+r_1$$

$$m=k q-r_1 .$$

## 数学代写|组合数学代写Combinatorial mathematics代考|Tiling by Linear Polyominoes

$$m=k q_1+r_1 ; \quad 0<r_1<k, \quad n=k q_2+r_2 ; \quad 0<r_2<k,$$

$$S_1 \equiv S_2 \equiv \ldots \equiv S_k(\bmod k) .$$

$$S_{r_2}-S_{r_2+1}=m$$

$$S_{r_2} \equiv S_{r_2+1}(\bmod k)$$

## 有限元方法代写

tatistics-lab作为专业的留学生服务机构，多年来已为美国、英国、加拿大、澳洲等留学热门地的学生提供专业的学术服务，包括但不限于Essay代写，Assignment代写，Dissertation代写，Report代写，小组作业代写，Proposal代写，Paper代写，Presentation代写，计算机作业代写，论文修改和润色，网课代做，exam代考等等。写作范围涵盖高中，本科，研究生等海外留学全阶段，辐射金融，经济学，会计学，审计学，管理学等全球99%专业科目。写作团队既有专业英语母语作者，也有海外名校硕博留学生，每位写作老师都拥有过硬的语言能力，专业的学科背景和学术写作经验。我们承诺100%原创，100%专业，100%准时，100%满意。

## MATLAB代写

MATLAB 是一种用于技术计算的高性能语言。它将计算、可视化和编程集成在一个易于使用的环境中，其中问题和解决方案以熟悉的数学符号表示。典型用途包括：数学和计算算法开发建模、仿真和原型制作数据分析、探索和可视化科学和工程图形应用程序开发，包括图形用户界面构建MATLAB 是一个交互式系统，其基本数据元素是一个不需要维度的数组。这使您可以解决许多技术计算问题，尤其是那些具有矩阵和向量公式的问题，而只需用 C 或 Fortran 等标量非交互式语言编写程序所需的时间的一小部分。MATLAB 名称代表矩阵实验室。MATLAB 最初的编写目的是提供对由 LINPACK 和 EISPACK 项目开发的矩阵软件的轻松访问，这两个项目共同代表了矩阵计算软件的最新技术。MATLAB 经过多年的发展，得到了许多用户的投入。在大学环境中，它是数学、工程和科学入门和高级课程的标准教学工具。在工业领域，MATLAB 是高效研究、开发和分析的首选工具。MATLAB 具有一系列称为工具箱的特定于应用程序的解决方案。对于大多数 MATLAB 用户来说非常重要，工具箱允许您学习应用专业技术。工具箱是 MATLAB 函数（M 文件）的综合集合，可扩展 MATLAB 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。

## 数学代写|组合数学代写Combinatorial mathematics代考|MATH418

statistics-lab™ 为您的留学生涯保驾护航 在代写组合数学Combinatorial mathematics方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写组合数学Combinatorial mathematics代写方面经验极为丰富，各种代写组合数学Combinatorial mathematics相关的作业也就用不着说。

• Statistical Inference 统计推断
• Statistical Computing 统计计算
• (Generalized) Linear Models 广义线性模型
• Statistical Machine Learning 统计机器学习
• Longitudinal Data Analysis 纵向数据分析
• Foundations of Data Science 数据科学基础

## 数学代写|组合数学代写Combinatorial mathematics代考|Solutions to Exercises

2.1. The area of an $\mathrm{L}$-tromino (see Figure 1.6) is equal to 3 . The area of the $4 \times 5$ rectangle is equal to 20 . Hence, in order to tile this rectangle by L-trominoes, it is necessary to use $\frac{20}{3}$ L-trominoes, which is impossible.

Generally, if an $a \times b$ rectangle can be tiled by L-trominoes, then $a b$ is divisible by 3 . This is a necessary condition for the existence of such a tiling.
2.2. Due to Exercise $2.1$, if an $a \times a$ square can be tiled by Ltrominoes, then $a$ is divisible by 3 . The $6 \times 6$ square can be decomposed into $2 \times 3$ blocks (Figure $2.3$ ), and consequently, the $6 \times 6$ square can be tiled by L-trominoes (see Figure 2.2). So, it remains to be seen whether the $3 \times 3$ square can be tiled by L-trominoes. The answer is “no.” Indeed, all the ways to cover the upper-left corner are shown in Figure 2.4.

In Figure 2.4(a), it is impossible to cover the upper right corner. In Figure 2.4(b), it is impossible to cover the lower left corner. Finally, in Figure 2.4(c), the only ways to cover the upper right corner is shown

in Figure 2.5. But then the three bottom squares remain uncovered. Thus the investigation of all possibilities shows that the $3 \times 3$ square cannot be tiled by L-trominoes. Consequently, the $6 \times 6$ square is the smallest tileable square.
2.3. If $b$ is divisible by 3 , then a $2 \times b$ rectangle can be decomposed into $2 \times 3$ blocks (see Figure 2.6) and, consequently, this rectangle can be tiled by L-trominoes. The reasoning in the solution to Exercise $2.1$ shows that there are no other possibilities. So, the $2 \times b$ rectangle can be tiled by L-trominoes if and only if $b$ is divisible by 3 .

## 数学代写|组合数学代写Combinatorial mathematics代考|Tetrominoes and Chromatic Reasoning

There exist five types of tetrominoes (Figure 3.1). We will call them O-, Z-, L-, T-, and I-tetrominoes. In this section we consider the problem of tiling a rectangle by O-, Z-, L-, and T-tetrominoes. For I-tetrominoes, the problem will be generalized and solved in the next section. In order to solve these problems we will often use “color” reasoning that was mentioned in Section 1.

Exercise 3.1. Prove that the $m \times n$ rectangle can be tiled with Otetrominoes if and only if $m, n$ are even.

Exercise 3.2. Prove that no rectangle can be tiled with Z-tetrominoes. The above exercises do not require the use of “color” reasoning. But such reasoning will be very useful for other types of tetrominoes.
Exercise 3.3. Prove that if all squares of an $a \times b$ chess-board are colored in two colors black and white (Figure 3.2), then the difference between the number of black squares and the number of white squares is equal to either 0 or $\pm 1$.

Exercise 3.4. Prove that if an $m \times n$ rectangle is colored in two colors, black and white, by columns (Figure 3.3), then the difference between the number of black squares and the number of white squares is equal to either 0 or $\pm m$.

Fxercise 3.5. Prove that if an $a \times b$ rectangle is tiled with I.tetrominoes, then the number of tiles is even.

This exercise shows that the area of a rectangle tiled by $\mathrm{L}$ tetrominoes must be divisible by 8 .

It is obvious that the $2 \times 4$ rectangle can be tiled by two Ltetrominoes (Figure 3.4). The following problem arises naturally: What other rectangles can be tiled by tetrominoes of this type? Can you solve this problem on your own? If not, try to solve the following exercises to pave the way for a successful train of thought.

# 组合数学代写

## 数学代写|组合数学代写Combinatorial mathematics代考|Solutions to Exercises

2.1. 的面积大号-tromino（见图 1.6）等于 3 。的面积4×5矩形等于 20 。因此，为了用 L-trominoes 平铺这个矩形，有必要使用203L-trominoes，这是不可能的。

2.2. 由于运动2.1， 如果一种×一种正方形可以用 Ltrominoes 平铺，然后一种能被 3 整除。这6×6正方形可以分解为2×3块（图2.3), 因此,6×6正方形可以用 L-trominoes 平铺（见图 2.2）。因此，是否有待观察3×3正方形可以用 L-trominoes 平铺。答案是不。” 事实上，所有覆盖左上角的方法如图 2.4 所示。

2.3. 如果b能被 3 整除，那么 a2×b矩形可以分解为2×3块（见图 2.6），因此，这个矩形可以用 L-trominoes 平铺。Exercise 解决方案中的推理2.1表明没有其他可能性。所以2×b矩形可以被 L-trominoes 平铺当且仅当b能被 3 整除。

## 有限元方法代写

tatistics-lab作为专业的留学生服务机构，多年来已为美国、英国、加拿大、澳洲等留学热门地的学生提供专业的学术服务，包括但不限于Essay代写，Assignment代写，Dissertation代写，Report代写，小组作业代写，Proposal代写，Paper代写，Presentation代写，计算机作业代写，论文修改和润色，网课代做，exam代考等等。写作范围涵盖高中，本科，研究生等海外留学全阶段，辐射金融，经济学，会计学，审计学，管理学等全球99%专业科目。写作团队既有专业英语母语作者，也有海外名校硕博留学生，每位写作老师都拥有过硬的语言能力，专业的学科背景和学术写作经验。我们承诺100%原创，100%专业，100%准时，100%满意。

## MATLAB代写

MATLAB 是一种用于技术计算的高性能语言。它将计算、可视化和编程集成在一个易于使用的环境中，其中问题和解决方案以熟悉的数学符号表示。典型用途包括：数学和计算算法开发建模、仿真和原型制作数据分析、探索和可视化科学和工程图形应用程序开发，包括图形用户界面构建MATLAB 是一个交互式系统，其基本数据元素是一个不需要维度的数组。这使您可以解决许多技术计算问题，尤其是那些具有矩阵和向量公式的问题，而只需用 C 或 Fortran 等标量非交互式语言编写程序所需的时间的一小部分。MATLAB 名称代表矩阵实验室。MATLAB 最初的编写目的是提供对由 LINPACK 和 EISPACK 项目开发的矩阵软件的轻松访问，这两个项目共同代表了矩阵计算软件的最新技术。MATLAB 经过多年的发展，得到了许多用户的投入。在大学环境中，它是数学、工程和科学入门和高级课程的标准教学工具。在工业领域，MATLAB 是高效研究、开发和分析的首选工具。MATLAB 具有一系列称为工具箱的特定于应用程序的解决方案。对于大多数 MATLAB 用户来说非常重要，工具箱允许您学习应用专业技术。工具箱是 MATLAB 函数（M 文件）的综合集合，可扩展 MATLAB 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。

## 数学代写|组合数学代写Combinatorial mathematics代考|COMP418

statistics-lab™ 为您的留学生涯保驾护航 在代写组合数学Combinatorial mathematics方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写组合数学Combinatorial mathematics代写方面经验极为丰富，各种代写组合数学Combinatorial mathematics相关的作业也就用不着说。

• Statistical Inference 统计推断
• Statistical Computing 统计计算
• (Generalized) Linear Models 广义线性模型
• Statistical Machine Learning 统计机器学习
• Longitudinal Data Analysis 纵向数据分析
• Foundations of Data Science 数据科学基础

## 数学代写|组合数学代写Combinatorial mathematics代考|Tiling a Checker Rectangle

Imagine you have an $m \times n$ rectangle $R$ and lots of dominoes (a domino is a $1 \times 2$ rectangle). It is easy to find the conditions under which $R$ can be tiled by dominoes, i.e., covered by dominoes, without any dominoes overlapping or sticking out over the boundary of $R$. Indeed, $R$ can be tiled by dominoes if and only if $m n$ is even (prove it!).

The problem becomes a bit more difficult if we want to tile the same rectangle with exactly two monominoes (a monomino is a $1 \times 1$ square) and many dominoes (Figure 1.1). Where can these two monominoes be placed?

In order to answer this question we color the rectangle $R$ in a chessboard fashion in two colors (Figure 1.2).

This coloring has a very nice property: regardless of how a domino is placed on the board, horizontally or vertically, it will cover exactly one square of each color (Figure 1.2). Therefore, the two monominoes must cover squares of different colors.

The famous mathematician Ralph E. Gomory found (and apparently never published himself ) a beautiful way to prove the converse, that no matter where the two monominoes are placed on the $m \times n$ board (where $m n$ is even and both $m$ and $n$ are greater than 1), as long as they are on different colors, the rest of the board can be tiled by dominoes.

Here is his proof. Supposing $n$ to be even (note at least one of the numbers $m, n$ must be even), Gomory created a labyrinth out of the board (Figure 1.3).

As you walk through this labyrinth, black and white squares alternate. Now let us cut the board along the walls of the labyrinth to get a checkered ring with alternating black and white squares (Figure 1.4).
It is clear that no matter what black and white squares we cover by monominoes, the number of squares between the monominoes (in both paths connecting them) must be even and therefore the rest of the ring can be tiled by dominoes.

## 数学代写|组合数学代写Combinatorial mathematics代考|Tiling Rectangles by Trominoes

Problems of tiling figures with tiles of an indicated shape (or cutting figures into parts of a given form) form a very interesting area of combinatorial geometry. It includes many fascinating exercises and research problems. Some of them we will consider in this section.

Here is an L-tromino (Figure 2.1). It is composed of three unit squares. (Note that there is one other tromino, the linear tromino, connecting three squares in a row. We will use this tromino in Section 4.) In this section we will address the following problem: How to tile a rectangle with L-trominoes. The first question is how to tile the $2 \times 3$ rectangle using L-trominoes. A solution is trivial (Figure 2.2).

We now offer a sequence of exercises. You are invited to find solutions. After several attempts (successful or not) we recommend you read our solutions at the end of the section.

Exercise 2.1. Is it possible to tile a $4 \times 5$ rectangle with L-trominoes?
Exercise 2.2. Find the smallest square that can be tiled with Ltrominoes.

Exercise 2.3. Find all integers $b$ such that a $2 \times b$ rectangle can be tiled using L-trominoes.

Exercise 2.4. Find all integers $b$ such that a $3 \times b$ rectangle can be tiled by L-trominoes.

Combining solutions to Exercises $2.3$ and 2.4, we obtain the following result.

Theorem 2.1. Let $a, b$ be integers such that $2 \leq a \leq 3$ and $a \leq b$. The $a \times b$ rectangle can be tiled by $L$-trominoes if and only if ab is divisible by 6.

Equivalently: the $a \times b$ rectangle with $2 \leq a \leq 3$ and $a \leq b$ can be tiled by L-trominoes if and only if one of the numbers $a, b$ is divisible by 2 and the other is divisible by 3 .

Now a new direction of research is clear: we will consider $a \times b$ rectangles in cases when $4 \leq a \leq b$. But first we would like to share a couple of “philosophical” observations.

# 组合数学代写

## 有限元方法代写

tatistics-lab作为专业的留学生服务机构，多年来已为美国、英国、加拿大、澳洲等留学热门地的学生提供专业的学术服务，包括但不限于Essay代写，Assignment代写，Dissertation代写，Report代写，小组作业代写，Proposal代写，Paper代写，Presentation代写，计算机作业代写，论文修改和润色，网课代做，exam代考等等。写作范围涵盖高中，本科，研究生等海外留学全阶段，辐射金融，经济学，会计学，审计学，管理学等全球99%专业科目。写作团队既有专业英语母语作者，也有海外名校硕博留学生，每位写作老师都拥有过硬的语言能力，专业的学科背景和学术写作经验。我们承诺100%原创，100%专业，100%准时，100%满意。

## MATLAB代写

MATLAB 是一种用于技术计算的高性能语言。它将计算、可视化和编程集成在一个易于使用的环境中，其中问题和解决方案以熟悉的数学符号表示。典型用途包括：数学和计算算法开发建模、仿真和原型制作数据分析、探索和可视化科学和工程图形应用程序开发，包括图形用户界面构建MATLAB 是一个交互式系统，其基本数据元素是一个不需要维度的数组。这使您可以解决许多技术计算问题，尤其是那些具有矩阵和向量公式的问题，而只需用 C 或 Fortran 等标量非交互式语言编写程序所需的时间的一小部分。MATLAB 名称代表矩阵实验室。MATLAB 最初的编写目的是提供对由 LINPACK 和 EISPACK 项目开发的矩阵软件的轻松访问，这两个项目共同代表了矩阵计算软件的最新技术。MATLAB 经过多年的发展，得到了许多用户的投入。在大学环境中，它是数学、工程和科学入门和高级课程的标准教学工具。在工业领域，MATLAB 是高效研究、开发和分析的首选工具。MATLAB 具有一系列称为工具箱的特定于应用程序的解决方案。对于大多数 MATLAB 用户来说非常重要，工具箱允许您学习应用专业技术。工具箱是 MATLAB 函数（M 文件）的综合集合，可扩展 MATLAB 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。

## 数学代写|组合数学代写Combinatorial mathematics代考|MATH4575

statistics-lab™ 为您的留学生涯保驾护航 在代写组合数学Combinatorial mathematics方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写组合数学Combinatorial mathematics代写方面经验极为丰富，各种代写组合数学Combinatorial mathematics相关的作业也就用不着说。

• Statistical Inference 统计推断
• Statistical Computing 统计计算
• (Generalized) Linear Models 广义线性模型
• Statistical Machine Learning 统计机器学习
• Longitudinal Data Analysis 纵向数据分析
• Foundations of Data Science 数据科学基础

## 数学代写|组合数学代写Combinatorial mathematics代考|The Principle of Inclusion

Given a set $A$ and subsets $A_1$ and $A_2$, how many elements are in $A$ but not in either of $A_1$ and $A_2$ ? The answer, which is easily obtained from a Venn diagram, is $|A|-\left|A_1\right|-$ $\left|A_2\right|+\left|A_1 \cap A_2\right|$. The Principle of Inclusion/Exclusion (P.I.E.) is a generalization of this formula to $n$ sets. It will be convenient to introduce some notation: for $V \subseteq[n]$, denote
$$A_V:=\bigcap_{i \in V} A_i .$$
2.3.1 ThEOREM (Principle of Inclusion/Exclusion). Let $A$ be a finite set, and $A_1, \ldots, A_n$ subsets of $A$. Then
$$\left|A \backslash\left(\bigcup_{i=1}^n A_i\right)\right|=\sum_{V \subseteq[n]}(-1)^{|V|}\left|A_V\right| .$$
Proof: We take the right-hand side of (2.6) and rewrite it, thus showing it is equal to the left-hand side. Start by writing each set size as
$$|X|=\sum_{a \in X} 1 .$$
In the right-hand side of (2.6), each element $a \in A$ will now contribute to a number of terms, sometimes with a plus sign, sometimes with a minus. We consider the contribution of $a$ to each of the numbers $\left|A_V\right|$. Assume that $a$ occurs in $m$ of the sets $A_i$. Then $a \in A_V$ if and only if $a \in A_i$ for all $i \in V$. This can only happen if $V$ is a subset of the $m$ integers indexing sets containing $a$. There are precisely $\left(\begin{array}{l}m \ k\end{array}\right)$ subsets of these indices with exactly $k$ elements. It follows that the contribution of $a$ to the sum is
$$\sum_{k=0}^m(-1)^k\left(\begin{array}{l} m \ k \end{array}\right)=(1-1)^m= \begin{cases}0 & \text { if } m>0 \ 1 & \text { if } m=0\end{cases}$$
where we used the binomial theorem and the fact that $0^0=1$. It follows that $a$ contributes to the sum if and only if $a$ is in none of the subsets $A_i$, and the result follows.

## 数学代写|组合数学代写Combinatorial mathematics代考|Generating functions

Generating functions form a powerful and versatile tool in enumerative combinatorics. In this overview course we barely scratch the surface of the field. We will mostly employ them for two purposes:

• Solve recurrence relations
• Decompose a counting problem into easier problems
We’ve seen an example of the first kind above, where we found an expression for the Fibonacci sequence. The second kind will lead to taking products of generating functions. We give another example.
2.4.1 Example. In how many ways can change worth $n$ cents be given using a combination of pennies and nickels?

Let $a_n$ denote the number of ways to give change from $n$ cents using only pennies. Let $b_n$ be the number of ways to give change from $n$ cents using only nickels. Clearly $a_n=1$ for all $n \geq 0$, and $b_n=1$ if $n$ is divisible by 5 , and 0 otherwise. Write
\begin{aligned} &A(x):=\sum_{n \geq 0} a_n x^n=1+x+x^2+\cdots=\frac{1}{1-x} . \ &B(x):=\sum_{n \geq 0} b_n x^n=1+x^5+x^{10}+\cdots=\frac{1}{1-x^5} . \end{aligned}
Now if we want to combine pennies and nickels, we could first allocate the number of pennies, say $k$, and use nickels for the remainder. So the desired answer will be $\sum_{k=0}^n a_k b_{n-k}$. If we look at the product of the generating functions, we get
$$A(x) B(x)=\sum_{n \geq 0}\left(\sum_{k=0}^n a_k b_{n-k}\right) x^n,$$
so the coefficient of $x^n$ contains exactly the right answer! Note that we can accommodate lots of extra side conditions in this method: use only an odd number of dimes, use up to twelve nickels, and so on.

This decomposition into simpler problems is usually most successful in an unlabeled context. For labeled problems often the exponential generating function is a better tool.

# 组合数学代写

## 数学代写|组合数学代写Combinatorial mathematics代考|The Principle of Inclusion

$$A_V:=\bigcap_{i \in V} A_i$$
2.3.1 ThEOREM（包含/排除原则）。让 $A$ 是一个有限集，并且 $A_1, \ldots, A_n$ 的子集 $A$. 然后
$$\left|A \backslash\left(\bigcup_{i=1}^n A_i\right)\right|=\sum_{V \subseteq[n]}(-1)^{|V|}\left|A_V\right| .$$

$$|X|=\sum_{a \in X} 1 .$$

$$\sum_{k=0}^m(-1)^k(m k)=(1-1)^m={0 \quad \text { if } m>01 \quad \text { if } m=0$$

## 数学代写|组合数学代写Combinatorial mathematics代考|Generating functions

• 求解递归关系
• 将计数问题分解为更简单的问题
我们已经在上面看到了第一种示例，我们在其中找到了斐波那契数列的表达式。第二种会导致取生成函数 的乘积。我们再举一个例子。
2.4.1 示例。有多少种方式可以改变价值 $n$ 使用便士和镇的组合给出美分?
让 $a_n$ 表示找雯的方式的数量 $n$ 美分只使用便士。让 $b_n$ 是找零的方式的数量 $n$ 美分仅使用镍。清楚地 $a_n=1$ 对所 有人 $n \geq 0$ ，和 $b_n=1$ 如果 $n$ 可被 5 整除，否则为 0 。写
$$A(x):=\sum_{n \geq 0} a_n x^n=1+x+x^2+\cdots=\frac{1}{1-x} . \quad B(x):=\sum_{n \geq 0} b_n x^n=1+x^5+x^{10}+\cdots=$$
现在如果我们想合并便士和镍，我们可以先分配便士的数量，比如说 $k$ ，其余部分使用镍币。所以想要的答案将 是 $\sum_{k=0}^n a_k b_{n-k}$. 如果我们看一下生成函数的乘积，我们得到
$$A(x) B(x)=\sum_{n \geq 0}\left(\sum_{k=0}^n a_k b_{n-k}\right) x^n,$$
所以系数 $x^n$ 包含完全正确的答案! 请注意，我们可以在此方法中容纳许多额外的附加条件：仅使用奇数个 10 美 分，最多使用 12 个镇等。
这种分解为更简单问题的方法通常在末标记的上下文中最为成功。对于标记问题，指数生成函数通常是更好的工 具。

## 有限元方法代写

tatistics-lab作为专业的留学生服务机构，多年来已为美国、英国、加拿大、澳洲等留学热门地的学生提供专业的学术服务，包括但不限于Essay代写，Assignment代写，Dissertation代写，Report代写，小组作业代写，Proposal代写，Paper代写，Presentation代写，计算机作业代写，论文修改和润色，网课代做，exam代考等等。写作范围涵盖高中，本科，研究生等海外留学全阶段，辐射金融，经济学，会计学，审计学，管理学等全球99%专业科目。写作团队既有专业英语母语作者，也有海外名校硕博留学生，每位写作老师都拥有过硬的语言能力，专业的学科背景和学术写作经验。我们承诺100%原创，100%专业，100%准时，100%满意。

## MATLAB代写

MATLAB 是一种用于技术计算的高性能语言。它将计算、可视化和编程集成在一个易于使用的环境中，其中问题和解决方案以熟悉的数学符号表示。典型用途包括：数学和计算算法开发建模、仿真和原型制作数据分析、探索和可视化科学和工程图形应用程序开发，包括图形用户界面构建MATLAB 是一个交互式系统，其基本数据元素是一个不需要维度的数组。这使您可以解决许多技术计算问题，尤其是那些具有矩阵和向量公式的问题，而只需用 C 或 Fortran 等标量非交互式语言编写程序所需的时间的一小部分。MATLAB 名称代表矩阵实验室。MATLAB 最初的编写目的是提供对由 LINPACK 和 EISPACK 项目开发的矩阵软件的轻松访问，这两个项目共同代表了矩阵计算软件的最新技术。MATLAB 经过多年的发展，得到了许多用户的投入。在大学环境中，它是数学、工程和科学入门和高级课程的标准教学工具。在工业领域，MATLAB 是高效研究、开发和分析的首选工具。MATLAB 具有一系列称为工具箱的特定于应用程序的解决方案。对于大多数 MATLAB 用户来说非常重要，工具箱允许您学习应用专业技术。工具箱是 MATLAB 函数（M 文件）的综合集合，可扩展 MATLAB 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。

## 数学代写|组合数学代写Combinatorial mathematics代考|МАТН418

statistics-lab™ 为您的留学生涯保驾护航 在代写组合数学Combinatorial mathematics方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写组合数学Combinatorial mathematics代写方面经验极为丰富，各种代写组合数学Combinatorial mathematics相关的作业也就用不着说。

• Statistical Inference 统计推断
• Statistical Computing 统计计算
• (Generalized) Linear Models 广义线性模型
• Statistical Machine Learning 统计机器学习
• Longitudinal Data Analysis 纵向数据分析
• Foundations of Data Science 数据科学基础

## 数学代写|组合数学代写Combinatorial mathematics代考|Closed formula

Consider the following functions, each of which is the answer to a combinatorial counting problem:
\begin{aligned} &f_1(n)=n^{n-2} \ &f_2(n)=n ! \sum_{k=0}^n(-1)^k / k ! \ &f_3(n)=\text { the nearest integer to } n ! / e \ &f_4(n)=\frac{1}{\sqrt{5}}\left(\tau_1^n-\tau_2^n\right) \end{aligned}

A function like $f_1$ is a completely satisfactory answer, but it is understandable that few problems admit solutions like this. We often need sums in the answer, as in $f_2$. This is still fairly acceptable, especially since (as we will see soon) the terms of the sum have combinatorial meaning: they correspond to certain partial counts! Formulas $f_3$ and $f_4$ are inherently non-combinatorial, since they involve terms that are not even rational numbers (let alone integers). However, such formulas can still be insightful, and may have a less cluttered appearance (case in point: $f_2=f_3$ ).

We tend to refer to solutions that are pleasing as a solution in “closed form” or a “closed formula”. We don’t want to make that term precise, but definitely allowed are multiplication, division, addition, subtraction (each a finite number of times, independent of $n$ ), binomial coefficients with integers, exponentiation, and factorials. Sometimes (as in $f_4$ ), we are willing to accept arbitrary complex numbers.

While we don’t consider $f_2$ to be a closed formula, it is still much more enlightening, and much easier to compute than listing all objects it counts (as we will see). For more convoluted sums, it becomes harder to see the value, and in fact it is possible to write sums so complicated that evaluating them is no better than listing all objects.

Closed formulas for generating functions may involve classical functions like sin, cos, exp, log, as well as exponentiation (including arbitrary real exponents) and multiplication, division, addition, subtraction.

## 数学代写|组合数学代写Combinatorial mathematics代考|Counting by bijection: spanning trees

The most satisfying way to count is to relate the objects you’re counting to much simpler objects, or (ideally) to objects which you already know how to count. In this section we will see a classical example of this: Cayley’s Theorem for counting the number of labeled spanning trees. That is, how many spanning trees are there on a fixed vertex set $V$ ? It is clear that the nature of the elements of $V$ is not important: we may as well take $V=[n]$, so the answer only depends on the size of $V$. Denote the number by $t(n)$. As before, we start with a table. The way we generate the trees is by first (using ad-hoc methods) determining all possible shapes of trees (“unlabeled trees on $n$ vertices”), and then finding all ways to assign the elements of $V$ to their labels.

Interestingly, the numbers in the right are equal to $n^{n-2}$. Cayley proved that this is in fact true for all $n$ :
2.2.1 THEOREM (Cayley’s Theorem). The number of spanning trees on a vertex set of size $n$ is $n^{n-2}$.

We will give two proofs of this important theorem. The first is a proof by bijection. We start by creating the Prüfer code $\left(y_1, \ldots, y_{n-1}\right)$ of a tree $T$ on vertex set $V=[n]$. This is done by recursively defining sequences $\left(x_1, \ldots, x_{n-1}\right)$ and $\left(y_1, \ldots, y_{n-1}\right)$ of vertices, and $\left(T_1, \ldots, T_{n-1}\right)$ of trees, as follows:

• $T_1:=T$.
• For $1 \leq i \leq n-1$, let $x_i$ be the degree-1 vertex of $T_i$ having smallest index.
• For $1 \leq i \leq n-1$, let $y_i$ be the neighbor of $x_i$ in $T_i$.
• For $1 \leq i \leq n-2$, let $T_{i+1}:=T_i-x_i$, that is, the tree obtained by removing vertex $x_i$ and edge $\left{x_i, y_i\right}$.
2.2.2 Example. Consider the tree in Figure 2.1. The sequence $\left(x_1, \ldots, x_9\right)=(3,4,2,5,6,7,1$, $8,9)$ and the sequence $\left(y_1, \ldots, y_9\right)=(2,2,1,1,7,1,10,10,10)$.

First proof of Theorem 2.2.1: Consider a Prüfer sequence $\left(y_1, \ldots, y_{n-1}\right)$. Since each tree has at least two degree-1 vertices, vertex $n$ will never be removed. Hence $y_{n-1}=n$. Pick $k \in{1, \ldots, n-2}$. Since only degree-1 vertices are removed, it follows that the degree of vertex $v$ in tree $T_k$ is one more than the number of occurrences of $v$ among $\left(y_k, \ldots, y_{n-2}\right)$. So the degree-1 vertices in $T_k$ are precisely those vertices not occurring in
$$\left{x_1, \ldots, x_{k-1}\right} \cup\left{y_k, \ldots, y_{n-2}\right}$$

# 组合数学代写

## 数学代写|组合数学代写Combinatorial mathematics代考|Closed formula

$f_1(n)=n^{n-2} \quad f_2(n)=n ! \sum_{k=0}^n(-1)^k / k ! f_3(n)=$ the nearest integer to $n ! / e \quad f_4(n)=\frac{1}{\sqrt{5}}$

## 数学代写|组合数学代写Combinatorial mathematics代考|Counting by bijection: spanning trees

2.2.1 定理（凯莱定理）。size 顶点集上生成树的数量 $n$ 是 $n^{n-2}$.

• $T_1:=T$.
• 为了 $1 \leq i \leq n-1 ， i 上 x_i$ 是的度数为 1 的顶点 $T_i$ 具有最小的索引。
• 为了 $1 \leq i \leq n-1 ＼mathrm{~ ， 让 ~} y_i$ 做邻居 $x_i$ 在 $T_i$.
• 为了 $1 \leq i \leq n-2$ ，让 $T_{i+1}:=T_i-x_i$ ，即去掉顶点得到的树 $x_i$ 和边缘 left{x_i, y_ilright $}$.
2.2.2 示例。考虑图 $2.1$ 中的树。序列 $\left(x_1, \ldots, x_9\right)=(3,4,2,5,6,7,1,8,9)$ 和顺序 $\left(y_1, \ldots, y_9\right)=(2,2,1,1,7,1,10,10,10)$.
定理 2.2.1 的第一个证明: 考虑一个Prüfer 序列 $\left(y_1, \ldots, y_{n-1}\right)$. 由于每棵树至少有两个度数为 1 的顶点，所 以 vertexn永远不会被删除。因此 $y_{n-1}=n$. 挑选 $k \in 1, \ldots, n-2$. 由于只删除了度数为 1 的顶点，因此可 以得出顶点的度数 $v$ 在树上 $T_k$ 比出现的次数多一 $v$ 之中 $\left(y_k, \ldots, y_{n-2}\right)$. 所以度数为 1 的顶点在 $T_k$ 恰恰是那些没 有出现在

## 有限元方法代写

tatistics-lab作为专业的留学生服务机构，多年来已为美国、英国、加拿大、澳洲等留学热门地的学生提供专业的学术服务，包括但不限于Essay代写，Assignment代写，Dissertation代写，Report代写，小组作业代写，Proposal代写，Paper代写，Presentation代写，计算机作业代写，论文修改和润色，网课代做，exam代考等等。写作范围涵盖高中，本科，研究生等海外留学全阶段，辐射金融，经济学，会计学，审计学，管理学等全球99%专业科目。写作团队既有专业英语母语作者，也有海外名校硕博留学生，每位写作老师都拥有过硬的语言能力，专业的学科背景和学术写作经验。我们承诺100%原创，100%专业，100%准时，100%满意。

## MATLAB代写

MATLAB 是一种用于技术计算的高性能语言。它将计算、可视化和编程集成在一个易于使用的环境中，其中问题和解决方案以熟悉的数学符号表示。典型用途包括：数学和计算算法开发建模、仿真和原型制作数据分析、探索和可视化科学和工程图形应用程序开发，包括图形用户界面构建MATLAB 是一个交互式系统，其基本数据元素是一个不需要维度的数组。这使您可以解决许多技术计算问题，尤其是那些具有矩阵和向量公式的问题，而只需用 C 或 Fortran 等标量非交互式语言编写程序所需的时间的一小部分。MATLAB 名称代表矩阵实验室。MATLAB 最初的编写目的是提供对由 LINPACK 和 EISPACK 项目开发的矩阵软件的轻松访问，这两个项目共同代表了矩阵计算软件的最新技术。MATLAB 经过多年的发展，得到了许多用户的投入。在大学环境中，它是数学、工程和科学入门和高级课程的标准教学工具。在工业领域，MATLAB 是高效研究、开发和分析的首选工具。MATLAB 具有一系列称为工具箱的特定于应用程序的解决方案。对于大多数 MATLAB 用户来说非常重要，工具箱允许您学习应用专业技术。工具箱是 MATLAB 函数（M 文件）的综合集合，可扩展 MATLAB 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。

## 数学代写|组合数学代写Combinatorial mathematics代考|COMP418

statistics-lab™ 为您的留学生涯保驾护航 在代写组合数学Combinatorial mathematics方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写组合数学Combinatorial mathematics代写方面经验极为丰富，各种代写组合数学Combinatorial mathematics相关的作业也就用不着说。

• Statistical Inference 统计推断
• Statistical Computing 统计计算
• (Generalized) Linear Models 广义线性模型
• Statistical Machine Learning 统计机器学习
• Longitudinal Data Analysis 纵向数据分析
• Foundations of Data Science 数据科学基础

## 数学代写|组合数学代写Combinatorial mathematics代考|Some notation and terminology

If we use special notation, we normally explain it when it is first introduced. Some notation crops up often enough that we introduce it here:
$\mathbb{N} \quad$ The set of nonnegative integers ${0,1,2, \ldots}$
[n] The finite set of integers ${1,2, \ldots, n}$
$|X| \quad$ The size of the set $X$, i.e. the number of elements in it.
$\mathscr{P}(X)$ The power set of $X$, i.e. the set ${Y: Y \subseteq X}$.
Many of the structures we will study can be seen as set systems. A set system is a pair $(X, \mathscr{F})$, where $X$ is a finite set and $\mathscr{F} \subseteq \mathscr{P}(X)$. We refer to $\mathscr{F}$ as a set family. Often we are interested in families with certain properties (“all sets have the same size”), or families whose members have certain intersections (“no two sets are disjoint”), or families that are closed under certain operations (“closed under taking supersets”).
An important example, that comes with a little bit of extra terminology, is that of a graph:
.2.1 Definition. A graph $G$ is a pair $(V, E)$, where $V$ is a finite set, and $E$ is a collection of size-2 subsets of $V$.

The members of $V$ are called vertices, the members of $E$ edges. If $e={u, v}$ is an edge, then $u$ and $v$ are the endpoints. We say $u$ and $v$ are adjacent, and that $u$ and $v$ are incident with $e$. One can think of a graph as a network with set of nodes $V$. The edges then denote which nodes are connected. Graphs are often visualized by drawing the vertices as points in the plane, and the edges as lines connecting two points.
.2.2 Definition. The degree of a vertex $v$, denoted $\operatorname{deg}(v)$, is the number of edges having $v$ as endpoint. A vertex of degree 0 is called isolated.

If you have never encountered graphs before, an overview of the most basic concepts is given in Appendix A.

## 数学代写|组合数学代写Combinatorial mathematics代考|Generating function

Having the ability to compute a number does not mean we know all about it. Is the sequence monotone? How fast does it grow? For questions like these we have a very powerful tool, which at first sight may look like we are cheating: the generating function. A generating function is, initially, nothing but a formalism, a way to write down the sequence. We write down an infinite polynomial in $x$, where $f(n)$ is the coefficient of $x^n$ :
$$F(x):=\sum_{n \geq 0} f(n) x^n .$$
Again, in spite of the notation, we do (for now) not see this as a function, just as a way to write down the sequence. In particular, we do not (yet) allow substitution of anything for $x$.

An interesting thing happens if we try to turn each side of the recurrence relation into a generating function. We multiply left and right by $x^n$, and sum over all values of $n$ for which all terms are defined (in this case $n \geq 1$ ). This gives
$$\sum_{n \geq 1} f(n+1) x^n=\sum_{n \geq 1} f(n) x^n+\sum_{n \geq 1} f(n-1) x^n .$$
Next, we multiply both sides by $x$, and extract a factor of $x$ from the last sum:
$$\sum_{n \geq 1} f(n+1) x^{n+1}=x\left(\sum_{n \geq 1} f(n) x^n+x \sum_{n \geq 1} f(n-1) x^{n-1}\right)$$
A change of variables in the first and third sum gives:
$$\sum_{m \geq 2} f(m) x^m=x\left(\sum_{n \geq 1} f(n) x^n+x \sum_{m \geq 0} f(m) x^m\right)$$
Finally we add terms to the sums to make all range from 0 to infinity:
$$\sum_{m \geq 0} f(m) x^m-f(0) x^0-f(1) x^1=x\left(\sum_{n \geq 0} f(n) x^n-f(0) x^0+x \sum_{m \geq 0} f(m) x^m\right) .$$

# 组合数学代写

## 数学代写|组合数学代写Combinatorial mathematics代考|Some notation and terminology

$\mathbb{N}$ 非负整数集 $0,1,2, \ldots$
[n]有限整数集 $1,2, \ldots, n$
$|X|$ 集合的大小 $X$ ，即其中的元素个数。
$\mathscr{P}(X)$ 的幂集 $X$ ，即集合 $Y: Y \subseteq X$.

$\mathscr{F} \subseteq \mathscr{P}(X)$. 我们指的是 $\mathscr{F}$ 作为一个固定的家庭。我们通常对具有特定属性的族 (“所有集合都具有相同的大

$.2 .1$ 定义。一张图 $G$ 是一对 $(V, E)$ ， 在哪里 $V$ 是一个有限集，并且 $E$ 是 size-2 子集的集合 $V$.

$.2 .2$ 定义。顶点的度数 $v$ ，表示 $\operatorname{deg}(v)$ ，是边的数量 $v$ 作为端点。度为 0 的顶点称为孤立的。

## 数学代写|组合数学代写Combinatorial mathematics代考|Generating function

$$F(x):=\sum_{n \geq 0} f(n) x^n .$$

$$\sum_{n \geq 1} f(n+1) x^n=\sum_{n \geq 1} f(n) x^n+\sum_{n \geq 1} f(n-1) x^n .$$

$$\sum_{n \geq 1} f(n+1) x^{n+1}=x\left(\sum_{n \geq 1} f(n) x^n+x \sum_{n \geq 1} f(n-1) x^{n-1}\right)$$

$$\sum_{m \geq 2} f(m) x^m=x\left(\sum_{n \geq 1} f(n) x^n+x \sum_{m \geq 0} f(m) x^m\right)$$

$$\sum_{m \geq 0} f(m) x^m-f(0) x^0-f(1) x^1=x\left(\sum_{n \geq 0} f(n) x^n-f(0) x^0+x \sum_{m \geq 0} f(m) x^m\right)$$

## 有限元方法代写

tatistics-lab作为专业的留学生服务机构，多年来已为美国、英国、加拿大、澳洲等留学热门地的学生提供专业的学术服务，包括但不限于Essay代写，Assignment代写，Dissertation代写，Report代写，小组作业代写，Proposal代写，Paper代写，Presentation代写，计算机作业代写，论文修改和润色，网课代做，exam代考等等。写作范围涵盖高中，本科，研究生等海外留学全阶段，辐射金融，经济学，会计学，审计学，管理学等全球99%专业科目。写作团队既有专业英语母语作者，也有海外名校硕博留学生，每位写作老师都拥有过硬的语言能力，专业的学科背景和学术写作经验。我们承诺100%原创，100%专业，100%准时，100%满意。

## MATLAB代写

MATLAB 是一种用于技术计算的高性能语言。它将计算、可视化和编程集成在一个易于使用的环境中，其中问题和解决方案以熟悉的数学符号表示。典型用途包括：数学和计算算法开发建模、仿真和原型制作数据分析、探索和可视化科学和工程图形应用程序开发，包括图形用户界面构建MATLAB 是一个交互式系统，其基本数据元素是一个不需要维度的数组。这使您可以解决许多技术计算问题，尤其是那些具有矩阵和向量公式的问题，而只需用 C 或 Fortran 等标量非交互式语言编写程序所需的时间的一小部分。MATLAB 名称代表矩阵实验室。MATLAB 最初的编写目的是提供对由 LINPACK 和 EISPACK 项目开发的矩阵软件的轻松访问，这两个项目共同代表了矩阵计算软件的最新技术。MATLAB 经过多年的发展，得到了许多用户的投入。在大学环境中，它是数学、工程和科学入门和高级课程的标准教学工具。在工业领域，MATLAB 是高效研究、开发和分析的首选工具。MATLAB 具有一系列称为工具箱的特定于应用程序的解决方案。对于大多数 MATLAB 用户来说非常重要，工具箱允许您学习应用专业技术。工具箱是 MATLAB 函数（M 文件）的综合集合，可扩展 MATLAB 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。