MAT270 discrete mathematics - 统计代写答疑辅导

分类： MAT270 discrete mathematics

数学代写|MAT270 discrete mathematics

Posted on 2023年4月3日2023年4月3日 by statistics-lab

Statistics-lab™可以为您提供tesu.edu MAT270 discrete mathematics离散数学课程的代写代考和辅导服务！

MAT270 discrete mathematics课程简介

Discrete Mathematics is designed to meet the needs not only of students majoring in computer science but of a wider audience, especially students in mathematics and science. The course provides tools for formal reasoning. Topics include counting rules, propositional and first-order logic, set theory, functions (with an emphasis on recursive functions), partial order and equivalence relations, Boolean algebra, and switching circuits. Graphs and trees are also introduced. With an emphasis on communication skills, students are required to interpret, describe, discuss, and justify conclusions based on logical reasoning. While the particular focus of the course is on reasoning related to computer programs, no knowledge of programming is required.
Advisory: It is advisable to have knowledge in a course equivalent to MAT-121: College Algebra with a grade of C or better to succeed in this course. Students are responsible for making sure that they have the necessary knowledge.

PREREQUISITES

Discrete Mathematics is a fundamental course that provides a solid foundation for computer science, mathematics, and science students. The course covers a wide range of topics, including counting rules, logic, set theory, functions, relations, Boolean algebra, and graph theory. The emphasis on formal reasoning and communication skills makes this course valuable to all students.

To succeed in this course, it is advisable to have a good understanding of college algebra, as it forms the basis of many concepts covered in the course. Students should ensure that they have the necessary prerequisite knowledge before enrolling in the course.

The course provides tools for formal reasoning, which are essential for students pursuing computer science or related fields. These tools enable students to analyze and design algorithms, write correct programs, and prove the correctness of programs.

Overall, discrete mathematics is a challenging but rewarding course that prepares students for further study in computer science, mathematics, and science. The skills and knowledge gained in this course are valuable not only in academia but also in industry and other fields.

MAT270 discrete mathematics HELP（EXAM HELP， ONLINE TUTOR）

问题 1.

Let $n \in \mathbb{N}$, and let $p$ be a prime. Show that the following statements are true
(1) $p$ appears an even number (or zero) of times in the prime factorization of $n^2$.
(2) $p$ appears an odd number of times in the prime factorization of $m=p \cdot n^2$.

We will prove both statements separately.

(1) Let $n = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ be the prime factorization of $n$. Then $n^2 = p_1^{2a_1}p_2^{2a_2}\cdots p_k^{2a_k}$, which shows that the exponent of $p$ in the prime factorization of $n^2$ is even (or zero) if $p$ is not one of the $p_i$’s, and it is twice the exponent of $p$ in the prime factorization of $n$ if $p$ is one of the $p_i$’s. In either case, the exponent of $p$ in the prime factorization of $n^2$ is even (or zero), which proves (1).

(2) Let $m = p \cdot n^2$. We need to count the number of times $p$ appears in the prime factorization of $m$. By part (1), $p$ appears an even number (or zero) of times in the prime factorization of $n^2$. Therefore, $p$ appears an odd number of times in the prime factorization of $m$ if and only if it appears an odd number of times in the prime factorization of $p$. But $p$ is prime, so it appears in the prime factorization of $p$ exactly once. Therefore, $p$ appears an odd number of times in the prime factorization of $m$, which proves (2).

问题 2.

Prove the following statements.
(1) There are no numbers $a, b$ such that $\frac{a}{b}=\sqrt{7}$.
(2) There are no numbers $a, b$ such that $\frac{a}{b}=\sqrt{23}$.
(3) Let $p$ be a prime. There are no numbers $a, b$ such that $\frac{a}{b}=\sqrt{p}$.

We will prove all three statements using a proof by contradiction.

(1) Suppose, for contradiction, that there exist integers $a$ and $b$ such that $\frac{a}{b}=\sqrt{7}$. Then $a^2=7b^2$. This implies that $a^2$ is a multiple of $7$, so $a$ must also be a multiple of $7$. Let $a=7c$. Then $49c^2=7b^2$, which simplifies to $7c^2=b^2$. This implies that $b$ is also a multiple of $7$. But this contradicts the assumption that $a$ and $b$ have no common factors, since they are both multiples of $7$. Therefore, there are no integers $a$ and $b$ such that $\frac{a}{b}=\sqrt{7}$.

(2) Suppose, for contradiction, that there exist integers $a$ and $b$ such that $\frac{a}{b}=\sqrt{23}$. Then $a^2=23b^2$. This implies that $a^2$ is a multiple of $23$, so $a$ must also be a multiple of $23$. Let $a=23c$. Then $529c^2=23b^2$, which simplifies to $23c^2=b^2$. This implies that $b$ is also a multiple of $23$. But this contradicts the assumption that $a$ and $b$ have no common factors, since they are both multiples of $23$. Therefore, there are no integers $a$ and $b$ such that $\frac{a}{b}=\sqrt{23}$.

(3) Suppose, for contradiction, that there exist integers $a$ and $b$ such that $\frac{a}{b}=\sqrt{p}$ for some prime $p$. Then $a^2=pb^2$. This implies that $a^2$ is a multiple of $p$, so $a$ must also be a multiple of $p$. Let $a=pc$. Then $p^2c^2=pb^2$, which simplifies to $pc^2=b^2$. This implies that $b$ is also a multiple of $p$. But this contradicts the assumption that $a$ and $b$ have no common factors, since they are both multiples of $p$. Therefore, there are no integers $a$ and $b$ such that $\frac{a}{b}=\sqrt{p}$ for any prime $p$.

Textbooks

• An Introduction to Stochastic Modeling, Fourth Edition by Pinsky and Karlin (freely
available through the university library here)
• Essentials of Stochastic Processes, Third Edition by Durrett (freely available through
the university library here)
To reiterate, the textbooks are freely available through the university library. Note that
you must be connected to the university Wi-Fi or VPN to access the ebooks from the library
links. Furthermore, the library links take some time to populate, so do not be alarmed if
the webpage looks bare for a few seconds.

此图像的alt属性为空；文件名为%E7%B2%89%E7%AC%94%E5%AD%97%E6%B5%B7%E6%8A%A5-1024x575-10.png — MAT270 discrete mathematics

Statistics-lab™可以为您提供tesu.edu MAT270 discrete mathematics离散数学课程的代写代考和辅导服务！请认准Statistics-lab™. Statistics-lab™为您的留学生涯保驾护航。

数学代写|MAT270 discrete mathematics

Posted on 2023年3月31日2023年4月3日 by statistics-lab

Statistics-lab™可以为您提供tesu.edu MAT270 discrete mathematics离散数学课程的代写代考和辅导服务！

MAT270 discrete mathematics课程简介

PREREQUISITES

MAT270 discrete mathematics HELP（EXAM HELP， ONLINE TUTOR）

问题 1.

Let $n \in \mathbb{N}$. Show that the following statements are true
(1) $n^5 \bmod 5=n \bmod 5$.
(2) $n^7 \bmod 7=n \bmod 7$.

Proof:

(1) We can use Fermat’s Little Theorem, which states that if $p$ is a prime number and $a$ is an integer not divisible by $p$, then $a^{p-1}\equiv 1 \pmod p$. Applying this theorem with $p=5$ and $a=n$, we have $n^4\equiv 1 \pmod 5$. Multiplying both sides by $n$ gives $n^5 \equiv n \pmod 5$, which is the desired result.

(2) Similarly, we can use Fermat’s Little Theorem with $p=7$ and $a=n$, which gives $n^6\equiv 1 \pmod 7$. Multiplying both sides by $n$ gives $n^7 \equiv n \pmod 7$, which is the desired result.

Therefore, both statements are true.

问题 2.

Prove the following statements. Let $n \in \mathbb{N}, n>1$, and $a \in \mathbb{N}$
(1) If $a \bmod n=b \bmod n$, then $(-a) \bmod n=(-b) \bmod b$.
(2) If $p$ is odd prime, then $(-a)^p=-a^p$.

Proof:

(1) Since $a \bmod n=b \bmod n$, we have $n$ divides $a-b$. This means that there exists an integer $k$ such that $a-b=kn$.

Now consider $(-a) \bmod n$ and $(-b) \bmod n$. We want to show that they are equal. We have:

$(-a) \bmod n=(-a+kn-kn) \bmod n=(-a+kn) \bmod n=-(a-kn) \bmod n=-(b-kn) \bmod n=(-b+kn) \bmod n=(-b) \bmod n$

where we have used the fact that adding or subtracting a multiple of $n$ does not change the remainder modulo $n$. Therefore, we have shown that $(-a) \bmod n=(-b) \bmod n$.

(2) We can use the binomial theorem to expand $(-a)^p$:

$(-a)^p=(-1)^p a^p$

If $p$ is odd, then $(-1)^p=-1$, so we have $(-a)^p=-a^p$, which is the desired result.

Therefore, both statements are true.

Textbooks

数学代写|MAT270 discrete mathematics

Posted on 2023年3月27日2023年3月27日 by statistics-lab

Statistics-lab™可以为您提供tesu.edu MAT270 discrete mathematics离散数学课程的代写代考和辅导服务！

MAT270 discrete mathematics课程简介

PREREQUISITES

MAT270 discrete mathematics HELP（EXAM HELP， ONLINE TUTOR）

问题 1.

At some point during the baseball season, the $n$ teams of the American League have already played several games. Suppose team $i$ has won $w_i$ games so far, and $g_{i j}=g_{j i}$ is the number of games that teams $i$ and $j$ have yet to play. No game ends in a tie, so each game yet to be played gives one point to one of the teams and zero point to the other. You would like to decide if your favorite team (Red Sox?), say team $n$, can still win. In other words, you would like to determine whether there exists an outcome of the games to be played (remember, with no ties) such that team $n$ has at least as many victories as any other team (we allow team $n$ to be tied for first place).
Your article should contain at least the following:

some motivation indicating that the problem is not as trivial as it appears,
a construction (with proof and explanations) that this problem can be cast and solved as a maximum flow problem,
a theorem (with proof and explanations) that team $n$ can win if and only if there is no set $S \subseteq{1, \cdots, n-1}$ such that
$$
w_n+\sum_{i=1}^{n-1} g_{i n}<\frac{\sum_{i \in S} w_i+\sum_{i<j, i \in S, j \in S} g_{i j}}{|S|}
$$

Motivation: At first glance, this problem might seem like a straightforward comparison of the number of wins of team $n$ with the other teams’ wins. However, the fact that there are still games to be played, and that each game can result in a point for only one team, makes this problem more complicated. It is not immediately clear how to determine whether team $n$ can still win the season. We need a more systematic approach to solve this problem.

Construction: We can model this problem as a maximum flow problem on a network. Consider a network with a source vertex $s$, a sink vertex $t$, and $n$ intermediate vertices $v_1, v_2, \ldots, v_n$. We draw an edge from $s$ to each $v_i$ with capacity $w_n-w_i$, representing the number of wins that team $n$ needs to catch up with team $i$. Similarly, we draw an edge from each $v_i$ to $t$ with capacity $\infty$, representing the number of remaining games that team $i$ needs to play. Finally, we draw an edge from each $v_i$ to each $v_j$ with capacity $g_{ij}$, representing the number of remaining games between teams $i$ and $j$.

We claim that the maximum flow in this network is equal to the number of games that team $n$ needs to win in order to have at least as many victories as any other team. To see why, consider any flow in the network. The flow on the edge from $s$ to $v_i$ represents the number of wins that team $n$ obtains against team $i$, and the flow on the edge from $v_i$ to $t$ represents the number of wins that team $i$ obtains in the remaining games. Therefore, the total number of wins of team $n$ in this flow is $\sum_{i=1}^{n-1} (w_n-w_i) – f(s,v_i)$, where $f(s,v_i)$ is the flow on the edge from $s$ to $v_i$. Similarly, the total number of wins of team $i$ in this flow is $w_i+f(v_i,t)$. Since there are no ties, the maximum possible number of wins is the total number of remaining games, which is $\frac{1}{2}\sum_{i<j} g_{ij}$. Therefore, team $n$ can win if and only if there exists a flow in the network with value at least $\sum_{i=1}^{n-1} (w_n-w_i) + \frac{1}{2}\sum_{i<j} g_{ij}$.

Theorem: Team $n$ can win if and only if there is no set $S \subseteq {1,\ldots,n-1}$ such that

w_n + \sum_{i \in S} g_{in} < \frac{\sum_{i \in S} w_i + \sum_{i<j, i \in S, j \in S} g_{ij}}{|S|}.wn+i∈S∑gin<∣S∣∑i∈Swi+∑i<j,i∈S,j∈Sgij.

Proof: Suppose that there exists a set $S$ that satisfies the inequality above. Then, we can set the flow on the edges from $s$ to $v_i$ as follows:

f(s,v_i) = \begin{cases} w_n – w_i, & i \in S \\ w_n – w_i + g_{in} – \frac{\sum_{j \in S} g_{ij}}{|S|}, & i \notin S. \end{cases}f(s,vi)={wn−wi,wn−wi+gin−∣S∣∑j∈Sgij,i∈Si∈/S.

It is easy

问题 2.

Let $n \in \mathbb{N}$, and let $p$ be a prime. Show that the following statements are true
(1) $p$ appears an even number (or zero) of times in the prime factorization of $n^2$.
(2) $p$ appears an odd number of times in the prime factorization of $m=p \cdot n^2$.

Proof: (1) We can write $n^2$ as a product of primes, i.e., $n^2 = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$, where $p_1, p_2, \dots, p_k$ are distinct primes and $a_1, a_2, \dots, a_k$ are positive integers. Thus, the prime factorization of $n^2$ contains each prime factor $p_i$ twice. Hence, $p$ appears an even number (or zero) of times in the prime factorization of $n^2$.

(2) We can write $m$ as $m = p \cdot n^2 = p \cdot p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$. Note that $p$ appears once in the prime factorization of $m$, and each $p_i$ appears an even number of times. Thus, $p$ appears an odd number of times in the prime factorization of $m$.

To see this, observe that for each $p_i$, there are two cases: either $p_i$ divides $p$ or it does not. If $p_i$ divides $p$, then $p_i$ appears once in the prime factorization of $m$. If $p_i$ does not divide $p$, then $p_i$ appears twice in the prime factorization of $n^2$, and hence $p_i^{a_i}$ appears an even number of times in the prime factorization of $m$. Therefore, the total number of times $p$ appears in the prime factorization of $m$ is odd.

Hence, the statements (1) and (2) are true.

Textbooks

数学代写|MAT270 discrete mathematics

Posted on 2023年3月16日2023年3月16日 by statistics-lab

Statistics-lab™可以为您提供tesu.edu MAT270 discrete mathematics离散数学课程的代写代考和辅导服务！

MAT270 discrete mathematics课程简介

PREREQUISITES

MAT270 discrete mathematics HELP（EXAM HELP， ONLINE TUTOR）

问题 1.

A stack of cans (see Figure 1) refers to an arrangement of $n$ (equal-sized) cans in rows such that (i) the cans in each row form a single continuous block, and (ii) any can, except the ones in the bottom row, touches exactly two cans from the row beneath it. If the bottom row contains $k$ cans, this is a $(n, k)$ stack of cans. Figure 1 shows a $(28,12)$ stack of cans.
Your article should give a formula (as a function of $k$ ) for the number $s_k$ of stack of cans with exactly $k$ cans in the bottom row (and an arbitrary total number of cans). Your article should at least contain:

A generating function for $\left(s_k\right)_{k \geq 0}$,
A closed-form formula for $s_k$ for any $k \geq 0$,
A relation between $s_k$ and another well-known sequence of numbers.
If you can find a bijective proof for $s_k$, you could also provide it. This is however not compulsory and should not replace any of the items above.

Let $S(x)$ be the generating function for the sequence ${s_k}{k\geq 0}$, i.e., $S(x)=\sum{k\geq 0} s_kx^k$. We can derive a recursive formula for $S(x)$ as follows:

Consider a $(n,k+1)$ stack of cans. If we remove the bottom row of $k+1$ cans, we are left with a $(n-k-1,k)$ stack of cans. Conversely, given any $(n-k-1,k)$ stack of cans, we can add a row of $k+1$ cans to the bottom to obtain a $(n,k+1)$ stack of cans. Therefore, we have the recurrence relation:

s_{k+1}=\sum_{n=k+1}^{\infty}s_{k}(n-k-1),sk+1=n=k+1∑∞sk(n−k−1),

where $s_k(n-k-1)$ represents the number of $(n,k+1)$ stacks of cans obtained by adding a row of $k+1$ cans to the top of a $(n-k-1,k)$ stack of cans.

Multiplying both sides of the recurrence relation by $x^{k+1}$ and summing over $k\geq 0$, we get:

\begin{aligned} \sum_{k\geq 0}s_{k+1}x^{k+1} &= \sum_{k\geq 0}\sum_{n=k+1}^{\infty}s_k(n-k-1)x^{k+1}\\ &= \sum_{n\geq 1}\sum_{k=0}^{n-1}s_k(n-k-1)x^{k+1}\\ &= \sum_{n\geq 1}\sum_{j=1}^{n-1}s_{n-j-1}jx^{n}\\ &= x\sum_{n\geq 1}\sum_{j=0}^{n-1}s_{n-j-1}jx^{n-1}\\ &= x\sum_{n\geq 0}\sum_{j=0}^{n}s_{n-j}jx^{n}\\ &= x\left(\sum_{n\geq 0}s_nx^n\right)\left(\sum_{j\geq 0}jx^j\right)\\ &= x\left(\sum_{n\geq 0}s_nx^n\right)\left(\frac{x}{(1-x)^2}\right). \end{aligned}k≥0∑sk+1xk+1=k≥0∑n=k+1∑∞sk(n−k−1)xk+1=n≥1∑k=0∑n−1sk(n−k−1)xk+1=n≥1∑j=1∑n−1sn−j−1jxn=xn≥1∑j=0∑n−1sn−j−1jxn−1=xn≥0∑j=0∑nsn−jjxn=x(n≥0∑snxn)(j≥0∑jxj)=x(n≥0∑snxn)((1−x)2x).

Therefore,

S(x)=\frac{x}{(1-x)^2}\sum_{k\geq 0}s_kx^k.S(x)=(1−x)2xk≥0∑skxk.

Solving for $\sum_{k\geq 0}s_kx^k$ in terms of $S(x)$, we obtain:

\sum_{k\geq 0}s_kx^k = x(1-x)S(x).k≥0∑skxk=x(1−x)S(x).

Since $s_0=1$, we have $\sum_{k\geq 0}s_k=1$, which implies that $S(1)=1$. Therefore, we have:

\sum_{k\geq 0}s_kx^k = \frac{x(1-x)}{(1-x)^2-x}=\frac{x}{1-2x+x^2}.k≥0∑skxk=(1−x)2−xx(1−x)=1−2x+x2x.

Using partial fraction decomposition, we can write.

问题 2.

Recall the inclusion / exclusion formula, let $A_1, A_2, \ldots, A_n$ be events, and
$$
S_k:=\sum_{1 \leq i_1<i_2<\cdots<i_k \leq n} \mathbb{P}\left(A_{i_1} \bigwedge A_{i_2} \bigwedge \ldots \bigwedge A_{i_k}\right) .
$$
The inclusion/exclusion formula gives
$$
\mathbb{P}\left(\bigvee_{i=1}^n A_i\right)=\sum_{j=1}^n(-1)^{j-1} S_j
$$
In this problem we will develop and use an extension of it.

Show that for all odd $k$ in ${1, \ldots, n}$,
$$
\mathbb{P}\left(\bigvee_{i=1}^n A_i\right) \leq \sum_{j=1}^k(-1)^{j-1} S_j,
$$
and describe how the union bound is a special case of this.
Show that for all even $k$ in ${1, \ldots, n}$,
$$
\mathbb{P}\left(\bigvee_{i=1}^n A_i\right) \geq \sum_{j=1}^k(-1)^{j-1} S_j
$$

The inclusion-exclusion principle is a powerful tool in probability theory, used to calculate the probability of the union of events. The standard form of the principle provides an exact formula for the probability of the union of $n$ events $A_1, A_2, \ldots, A_n$:

\mathbb{P}\left(\bigvee_{i=1}^n A_i\right)=\sum_{k=1}^n(-1)^{k-1} \sum_{1 \leq i_1<i_2<\cdots<i_k \leq n} \mathbb{P}\left(A_{i_1} \bigwedge A_{i_2} \bigwedge \ldots \bigwedge A_{i_k}\right) ,P(i=1⋁nAi)=k=1∑n(−1)k−11≤i1<i2<⋯<ik≤n∑P(Ai1⋀Ai2⋀…⋀Aik),

where $S_k$ is the sum over all $k$-fold intersections of events $A_i$. In this article, we will extend the inclusion-exclusion principle to provide tighter bounds on the probability of the union of events, based on the parity of the size of the intersection.

Let $A_1, A_2, \ldots, A_n$ be events, and let $S_k$ be as defined above. We will prove two separate inequalities based on the parity of $k$.

For odd $k$, we have:

\begin{align*} \mathbb{P}\left(\bigvee_{i=1}^n A_i\right) &= \sum_{k=1}^n (-1)^{k-1} S_k + (-1)^n \mathbb{P}\left(\bigwedge_{i=1}^n A_i\right) \ &\leq \sum_{k=1}^n (-1)^{k-1} S_k, \end{align*}

where the inequality follows from the fact that $\mathbb{P}\left(\bigwedge_{i=1}^n A_i\right) \geq 0$.

To see why this inequality holds, note that for odd $k$, the sum over all $k$-fold intersections in the inclusion-exclusion formula alternates in sign, starting with a positive sign. Therefore, the first $k$ terms in the sum are positive, and the remaining terms are negative. In particular, the sum up to $k$ is greater than or equal to the sum up to $k+1$, which implies the inequality.

The union bound is a special case of this inequality, where $k=1$. In this case, we have:

\mathbb{P}\left(\bigvee_{i=1}^n A_i\right) \leq \mathbb{P}\left(\bigvee_{i=1}^n A_i\right) + \mathbb{P}\left(\bigwedge_{i=1}^n \overline{A_i}\right) = 1,P(i=1⋁nAi)≤P(i=1⋁nAi)+P(i=1⋀nAi)=1,

where $\overline{A_i}$ denotes the complement of $A_i$. Therefore, the probability of the union of events is always less than or equal to 1.

Textbooks

数学代写|MAT270 discrete mathematics

Posted on 2023年3月6日2023年3月6日 by statistics-lab

Statistics-lab™可以为您提供tesu.edu MAT270 discrete mathematics离散数学课程的代写代考和辅导服务！

MAT270 discrete mathematics课程简介

PREREQUISITES

MAT270 discrete mathematics HELP（EXAM HELP， ONLINE TUTOR）

问题 1.

Read the theorem and proof below. Starting with the second sentence of the proof, identify the familiar information and the important new information in each sentence. Then revise to improve the information order and connectivity, without revising the theorem, the first sentence of the proof, or the figure caption.

Theorem: The sum of the angles in a triangle is 180 degrees.

Proof: Let ABC be a triangle. Draw a line through C parallel to AB, as shown in Figure 1. This line intersects AB at point D.

The angle sum of triangle ABC is equal to the sum of angles A, B, and C, which is also equal to the sum of angles A and D plus the sum of angles D, B, and C.

Angles A and D form a straight line, so their sum is 180 degrees. Similarly, angles D, B, and C form a straight line, so their sum is also 180 degrees. Therefore, the angle sum of triangle ABC is equal to 180 degrees.

Revised proof:

Let ABC be a triangle, and consider the line through C parallel to AB as shown in Figure 1. We label the intersection of this line with AB as point D.

To prove the theorem, we begin by noting that the angle sum of triangle ABC is equal to the sum of angles A, B, and C. This sum is also equal to the sum of angles A and D plus the sum of angles D, B, and C.

Next, we observe that angles A and D form a straight line, so their sum is 180 degrees. Likewise, angles D, B, and C also form a straight line, so their sum is also 180 degrees.

Combining these results, we conclude that the angle sum of triangle ABC is equal to 180 degrees, as required.

问题 2.

Read your solution to Pset 2 Problem 1 and look for places where changing the order of information could improve the connectivity.
(a) Revise Pset 2 Problem 1, considering the comments you received, the information order and connectivity, and anything else you see that would benefit from revision. (In particular, if you received a low grade on this problem, you should consider major revisions.)
(b) Indicate at least one instance in which you revised information order to improve connectivity. If you didn’t do so, then indicate at least one instance from the original version in which information is ordered in a way that creates connectivity.

(a) Revised Pset 2 Problem 1:

Suppose we have a collection of $n$ items, each of which can either be blue or green. We call a collection of items “balanced” if it contains an equal number of blue and green items. We wish to count the number of balanced collections.

To begin, let us consider the case where $n$ is even. We can then split the collection into two equal halves of size $n/2$, and count the number of balanced collections for each half. We can then multiply these counts to obtain the total number of balanced collections for the entire collection.

Now suppose $n$ is odd. We can still split the collection into two halves of size $(n-1)/2$ and $(n+1)/2$. We then count the number of balanced collections for each half, and multiply these counts. However, we must also account for the fact that there is one extra item, which can either be blue or green. Thus, we must add the number of balanced collections for each half where we have one more blue item, and also the number of balanced collections for each half where we have one more green item. This gives us the total number of balanced collections for the entire collection.

(b) An instance of revised information order to improve connectivity:

In the revised version, we start by defining what a balanced collection is before delving into the counting process. This helps to establish the context for the problem and make it clear what we are trying to accomplish.

Textbooks

数学代写|MAT270 discrete mathematics

Posted on 2023年3月1日2023年3月1日 by statistics-lab

Statistics-lab™可以为您提供tesu.edu MAT270 discrete mathematics离散数学课程的代写代考和辅导服务！

MAT270 discrete mathematics课程简介

PREREQUISITES

MAT270 discrete mathematics HELP（EXAM HELP， ONLINE TUTOR）

问题 1.

A stack of cans (see Figure 1) refers to an arrangement of $n$ (equal-sized) cans in rows such that (i) the cans in each row form a single continuous block, and (ii) any can, except the ones in the bottom row, touches exactly two cans from the row beneath it. If the bottom row contains $k$ cans, this is a $(n, k)$ stack of cans. Figure 1 shows a $(28,12)$ stack of cans.
Your article should give a formula (as a function of $k$ ) for the number $s_k$ of stack of cans with exactly $k$ cans in the bottom row (and an arbitrary total number of cans). Your article should at least contain:

A generating function for $\left(s_k\right)_{k \geq 0}$,
A closed-form formula for $s_k$ for any $k \geq 0$,
A relation between $s_k$ and another well-known sequence of numbers.
If you can find a bijective proof for $s_k$, you could also provide it. This is however not compulsory and should not replace any of the items above.

A stack of cans is an arrangement of $n$ cans in rows such that each row contains a single continuous block, and except for the bottom row, each can in the stack touches exactly two cans from the row below it. We call a stack with $k$ cans in the bottom row a $(n,k)$ stack. In this article, we will derive a formula for the number of $(n,k)$ stacks, denoted by $s_k$.

Let $s_n$ be the number of $(n,k)$ stacks. We can define the generating function $S(x) = \sum_{n \geq 0} s_n x^n$. Consider the first can in the bottom row of a $(n,k)$ stack. We can place this can in the leftmost or rightmost position of the bottom row, so there are $k$ choices for the position of this can. The cans above this can can be partitioned into two stacks, one to the left and one to the right. Let the sizes of these stacks be $a$ and $b$ respectively, so $a + b + 1 = n – k$. The stack to the left must have at least one can, so $a \geq 1$. The generating function $S(x)$ can then be expressed as:

S(x) = x^k \sum_{a=1}^{n-k-1} \sum_{b=0}^{n-k-1-a} s_a x^a s_b x^b.S(x)=xka=1∑n−k−1b=0∑n−k−1−asaxasbxb.

The factor of $x^k$ comes from the choice of position for the first can in the bottom row, and the limits of the summations ensure that the sizes of the left and right stacks are nonnegative and sum to $n-k-1$.

We can simplify this expression using the fact that $s_0 = 1$ (there is only one way to stack zero cans), so:

\begin{aligned} S(x) &= x^k \sum_{a=1}^{n-k-1} \sum_{b=0}^{n-k-1-a} s_a x^a s_b x^b \\ &= x^k \sum_{a=0}^{n-k-1} \sum_{b=0}^{n-k-1-a} s_a x^a s_b x^b – s_0 x^k \\ &= x^k \left(\sum_{a=0}^{n-k} s_a x^a\right)^2 – x^k. \end{aligned}S(x)=xka=1∑n−k−1b=0∑n−k−1−asaxasbxb=xka=0∑n−k−1b=0∑n−k−1−asaxasbxb−s0xk=xk(a=0∑n−ksaxa)2−xk.

Thus, we have the formula:

S(x) = \frac{x^k}{1 – \left(\sum_{a=0}^{n-k} s_a x^a\right)^2}.S(x)=1−(∑a=0n−ksaxa)2xk.

We can use partial fractions to expand the generating function $S(x)$ into a sum of simpler terms. Let $\alpha_i$ be the distinct roots of the polynomial $\sum_{a=0}^{n-k} s_a x^a$, and let $\beta_i$ be the multiplicities of these roots. Then:

S(x) = \frac{x^k}{\prod_{i=1}^m (1 – \alpha_i x)^{\beta_i}} = \sum_{i=1}^m \sum_{j=1}^{\beta_i} \frac{c_{i,j}}{(1 – \alpha_i x)^j},S(x)=∏i=1m(1−αix)βixk=i=1∑mj=1∑βi(1−αix)jci,j,

where $c_{i,j}$ are constants to be determined. Equating the coefficients of $x^n$ on both sides

问题 2.

Recall the inclusion / exclusion formula, let $A_1, A_2, \ldots, A_n$ be events, and
$$
S_k:=\sum_{1 \leq i_1<i_2<\cdots<i_k \leq n} \mathbb{P}\left(A_{i_1} \wedge A_{i_2} \wedge \ldots \wedge A_{i_k}\right) .
$$
The inclusion/exclusion formula gives
$$
\mathbb{P}\left(\bigvee_{i=1}^n A_i\right)=\sum_{j=1}^n(-1)^{j-1} S_j
$$
In this problem we will develop and use an extension of it.

Show that for all odd $k$ in ${1, \ldots, n}$,
$$
\mathbb{P}\left(\bigvee_{i=1}^n A_i\right) \leq \sum_{j=1}^k(-1)^{j-1} S_j
$$
and describe how the union bound is a special case of this.
Show that for all even $k$ in ${1, \ldots, n}$,
$$
\mathbb{P}\left(\bigvee_{i=1}^n A_i\right) \geq \sum_{j=1}^k(-1)^{j-1} S_j
$$

We begin by observing that for any $k\in{1,\ldots,n}$, we have \begin{align*} \mathbb{P}\left(\bigvee_{i=1}^n A_i\right) &= \sum_{i=1}^n\mathbb{P}(A_i) – \sum_{1\le i<j\le n}\mathbb{P}(A_i\wedge A_j) + \sum_{1\le i<j<k\le n}\mathbb{P}(A_i\wedge A_j\wedge A_k) – \cdots\ &\qquad\cdots + (-1)^{n-1}\mathbb{P}(A_1\wedge A_2\wedge\cdots\wedge A_n). \end{align*} We denote the $k$th term of this expansion by $T_k$.

Now suppose that $k$ is odd. We want to show that $\mathbb{P}(\bigvee_{i=1}^n A_i)\leq \sum_{j=1}^k(-1)^{j-1}S_j$. We have \begin{align*} \sum_{j=1}^k(-1)^{j-1}S_j &= T_1 – T_2 + T_3 – \cdots + (-1)^{k-1}T_k\ &= \mathbb{P}(A_1) – \sum_{1\le i<j\le n}\mathbb{P}(A_i\wedge A_j) + \cdots + (-1)^{k-1}\sum_{1\le i_1<i_2<\cdots<i_k\le n}\mathbb{P}(A_{i_1}\wedge A_{i_2}\wedge\cdots\wedge A_{i_k})\ &\ge \mathbb{P}(A_1) – \sum_{1\le i<j\le n}\mathbb{P}(A_i\wedge A_j) + \cdots + (-1)^{k-1}\mathbb{P}\left(\bigvee_{i=1}^n A_i\right)\ &= \sum_{j=1}^{k-1}(-1)^{j-1}S_j + (-1)^{k-1}\mathbb{P}\left(\bigvee_{i=1}^n A_i\right)\ &\ge (-1)^{k-1}\mathbb{P}\left(\bigvee_{i=1}^n A_i\right), \end{align*} where we have used the fact that $\mathbb{P}(\bigvee_{i=1}^n A_i)\geq 0$ and that $(-1)^{j-1}S_j\geq 0$ for all $j\in{1,\ldots,k}$.