Assignment-daixieTM为您提供伯明翰大学University of Birmingham Algebra & Combinatorics 06 25659代数与组合代写代考和辅导服务！
Instructions:
Combinatorics is a branch of mathematics that deals with the study of discrete structures and objects, such as finite sets, permutations, combinations, and graphs. It is concerned with the enumeration, classification, and analysis of these objects, as well as the development of methods and techniques for solving problems related to them.
Combinatorics has applications in various fields, including computer science, statistical physics, genetics, and cryptography. In computer science, combinatorial algorithms are used for optimization problems, network flow analysis, and data mining. In statistical physics, combinatorial methods are used to study the behavior of particles and other physical systems. In genetics, combinatorial methods are used to study the structure and function of DNA and RNA molecules.
The study of combinatorics can be divided into several subfields, including enumeration, graph theory, design theory, and coding theory. Enumeration involves the counting of discrete objects and structures, while graph theory deals with the study of graphs and their properties. Design theory is concerned with the construction of combinatorial structures that satisfy certain properties, such as balanced incomplete block designs and Latin squares. Coding theory involves the study of error-correcting codes and their applications in data transmission and storage.
Overall, combinatorics is an important area of mathematics with many practical applications, and its study is essential for understanding and solving problems in a variety of fields.
In class, we sketched a proof of the formula for the Catalan number $C_n=\frac{1}{2 n+1}\left(\begin{array}{c}2 n+1 \\ n\end{array}\right)$ using cyclic shifts of sequences of \pm 1 ‘s. The proof is based on the following two claims. Prove these claims. Let $\left(e_1, \ldots, e_{2 n+1}\right)$ be a sequence such that such that $e_i \in\{1,-1\}$, $\#\left\{i \mid e_i=1\right\}=n$, and $\#\left\{i \mid e_i=-1\right\}=n+1$. (1) All $2 n+1$ cyclic shifts $\left(e_i, \ldots, e_{2 n+1}, e_1, \ldots, e_{i-1}\right)$, for $i=1, \ldots, 2 n+$ 1 , are different from each other.
(1) Suppose, for the sake of contradiction, that there exist two cyclic shifts $\left(e_i, \ldots, e_{2 n+1}, e_1, \ldots, e_{i-1}\right)$ and $\left(e_j, \ldots, e_{2 n+1}, e_1, \ldots, e_{j-1}\right)$ that are the same, where $1 \leq i < j \leq 2n+1$. Then we have $e_i = e_j$, $e_{i+1} = e_{j+1}$, $\dots$, $e_{j-1} = e_{i-1}$, $e_{j} = e_{i}$, $e_{j+1} = e_{i+1}$, $\dots$, $e_{2n+1} = e_{j-i+1}$, $e_1 = e_{j-i+2}$, $\dots$, $e_{i-1} = e_{2n+1-j+i}$. Since $e_i = e_j$, we have $#\left{i \mid e_i=1\right}=#\left{i \mid e_i=-1\right}$ and $#\left{i \mid e_i=1\right}=n$. Thus, we have $#\left{i \mid e_i=-1\right}=n+1$. It follows that $e_{2n+1-j+i}=-1$, which implies $j-i=1$. But this contradicts $i<j$. Therefore, all $2n+1$ cyclic shifts are different.
(2) Exactly one cyclic shift $\left(e_1^{\prime}, \ldots, e_{2 n+1}^{\prime}\right)$ among these $2 n+1$ shifts satisfies $e_1^{\prime}+\cdots+e_j^{\prime} \geq 0$, for $j=1, \ldots, 2 n$.
(2) Define $S_k=e_1+e_2+\cdots+e_k$ for $k=1,\ldots,2n+1$. Note that $S_1= e_1$ and $S_{2n+1}=0$, and $S_k$ changes by $\pm 1$ when we move from $k$ to $k+1$. Thus, $S_k$ is equal to the number of $1$’s minus the number of $-1$’s in the first $k$ terms of the sequence. Since $#\left{i \mid e_i=1\right}=n$ and $#\left{i \mid e_i=-1\right}=n+1$, we have $S_k \geq 0$ for $k=1,\ldots,2n$. Moreover, $S_{2n+1}=0$ implies that there exists exactly one $k \in {1,\ldots,2n+1}$ such that $S_k=0$. This means that $S_k \geq 0$ for $k=1,\ldots,2n$ and $S_{2n+1}>0$, or $S_k \leq 0$ for $k=1,\ldots,2n$ and $S_{2n+1}<0$. Without loss of generality, assume that $S_k \geq 0$ for $k=1,\ldots,2n$ and $S_{2n+1}>0$. Then we have $S_k \geq 0$ for $k=1,\ldots,j-1$ and $S_k \leq 0$ for $k=j,\ldots,2n$, where $j$ is the smallest index such that $S_j<0$.
Consider the random walk of a man on the integer line $\mathbb{Z}$ such that, at each step, that the probability to go from position $i$ to position $i+1$ is $p$, and the probability to go from $i$ to $i-1$ is $1-p$. The man “falls off the cliff” if he reaches the position 0. Suppose that the man starts at the initial position $i_0 \geq 1$. Find the probability that he falls off the cliff.
Let $P_i$ be the probability that the man falls off the cliff starting from position $i$. We want to find $P_{i_0}$.
Note that if the man is currently at position $i \geq 1$, then he can either move one step to the right with probability $p$, or one step to the left with probability $1-p$. This means that the probability of falling off the cliff starting from position $i$ is equal to the weighted sum of the probabilities of falling off the cliff starting from positions $i+1$ and $i-1$:
$P_i=p P_{i+1}+(1-p) P_{i-1}$.
This is a linear recurrence relation with constant coefficients. Its characteristic equation is $r^2 – (1-p)/p r – 1 = 0$, whose roots are $r_1 = p/(1-p)$ and $r_2 = -1$. Therefore, the general solution to the recurrence relation is
$P_i=A\left(\frac{p}{1-p}\right)^i+B(-1)^i$,
where $A$ and $B$ are constants that depend on the initial conditions.
To determine the constants, note that $P_0 = 1$, since if the man is already at position 0, he has already fallen off the cliff. Therefore, we have $B = 1$. Moreover, if $i_0 > 0$, then $P_{i_0} = 0$, since the man has not yet fallen off the cliff. Therefore, we have
$P_{i_0}=A\left(\frac{p}{1-p}\right)^{i_0}+1=0$,
which implies that
$A=-\left(\frac{p}{1-p}\right)^{i_0}$
Thus, the probability that the man falls off the cliff starting from position $i_0$ is
$P_{i_0}=-\left(\frac{p}{1-p}\right)^{i_0}+1-(-1)^{i_0}$.
Note that if $i_0 = 1$, then $P_{i_0} = 1-p$, which makes sense, since the man has to take at least one step to the left to fall off the cliff, and the probability of doing so is $1-p$.
