DMAT_AS2

assignment2.pdf

Problem 1

Let $\mathcal{F}$ be a forest. Define a relation by $a\sim b$ if a path exists between $a$ and $b$. $\sim$ is an equivalence relation:

• $a\sim a$ for all $a\in \mathcal{F}$
• $a\sim b⟹b\sim a$
• $a\sim b$ and $b\sim c$ $⟹$ $a\sim c$, where the path from $a$ to $c$ is the concatenation of the paths form $a$ to $b$ and from $b$ to $c$.

Let ${\mathcal{F}}_{\sim }$ be the partition of $\mathcal{F}$ induced by $\sim$. Let $[a]\in {\mathcal{F}}_{\sim }$. Clearly, $[a]$ is connected. $[a]$ inherits the property of having no cycles from $\mathcal{F}$. Thus, $[a]$ is a tree. Thus, we can conclude that a forest is a disjoint union of trees.

Now, to the question at hand. Fix $a\in [n]$. Let $T_a$ denote the tree containing $a$. Note that the cases $|T_a|=1,2,\dots ,n$ are disjoint and exhaustive. If $F_k^{\prime }$ is the number of forests in which $|T_a|=k$, we can write

$$F(n)=\sum _{k=1}^n{F}_k^{\prime }.$$

Now,

$$\begin{array}{rl}{F}_k^{\prime }=& (\text{ways to pick remaining }k-1\text{ vertices for the tree})\times \\ & (\text{number of labeled trees on }k\text{ vertices})\times \\ & (\text{number of labeled forests on }n-k\text{ vertices}).\\ =& \left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)k^{k-2}F(n-k).\end{array}$$

Thus, we have

$$F(n)=\sum _{k=1}^n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)k^{k-2}F(n-k).$$

---

Problem 2

To prove:

$$\begin{array}{rl}{n}^n& =\sum _{k=0}^{n-1}\left(\genfrac{}{}{0ex}{}{n}{k}\right)k^k(n-k{)}^{n-k-1}.\end{array}$$

We know that $n^n$ counts the number of labeled $n$ vertebrates. Let $S_t$ denote the number of $n$ vertebrates with a rooted tree of size $t$ at their head. Clearly, every $n$ vertebrate belongs to exactly one such class, so summing over all possible values of $t$ should yield the total count, $n^n$.

To calculate $S_t$, we have to first pick $t$ vertices and create a rooted tree $T$ on $t$ vertices. The number of ways to do this is $\left(\genfrac{}{}{0ex}{}{n}{t}\right)t^{t-1}$. To get a $n$ vertebrate which has $T$ rooted at its head, we first get a $n-k$ vertebrate $V$ with head $h$ and tail $l$, and attach the root $r$ of $T$ to the head of $V$. This gives us an $n$ vertebrate with head $r$ and tail $l$.

$$S_t=\left(\genfrac{}{}{0ex}{}{n}{t}\right)t^{t-1}(n-t{)}^{n-t}.$$

Thus, the total number of $n$ vertebrates will be

$$\begin{array}{rlr}{n}^n& =\sum _{t=1}^n{S}_t& \\ & =\sum _{t=1}^n\left(\genfrac{}{}{0ex}{}{n}{t}\right)t^{t-1}(n-t{)}^{n-t}& \\ & =\sum _{t=1}^n\left(\genfrac{}{}{0ex}{}{n}{n-t}\right)t^{t-1}(n-t{)}^{n-t}& \\ & =\sum _{k=0}^{n-1}\left(\genfrac{}{}{0ex}{}{n}{k}\right)(n-k{)}^{n-k-1}{k}^k& \text{let }n-t=k\end{array}$$

---

Problem 3

Part a

Let $X=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]$. Then,

$$\left(\begin{array}{c}{F}_{n+1}\\ F_n\end{array}\right)=X^n\left(\begin{array}{c}1\\ 0\end{array}\right).$$

It follows that

$$\left[\begin{array}{cc}{F}_n& F_{n+1}\\ F_{n-1}& F_n\end{array}\right]=X^{n-1}\left[\begin{array}{cc}1& 1\\ 0& 1\end{array}\right]$$

Taking the determinant of both sides, we get

$$\begin{array}{r}{F}_n^2-F_{n+1}{F}_{n-1}=|X{|}^{n-1}=(-1{)}^{n-1}.\end{array}$$

Part b

Let $W_n$ denote the number of interest. It is easy to see that $W_1=1$ and $W_2=3$. Assuming we know $W_1,\dots ,W_{n-1}$, let us calculate $W_n$. Consider the subsets of $[n]$ which do not include $n$. Such a subset can either

• not include $n-1$, not include $1$
• not include $n-1$, include $1$
• include $n-1$, not include $1$
• include $n-1$, include $1$.

All but the last case is counted by $W_{n-1}$. If a subset includes $n-1$ and $1$, then it must necessarily not include $n-2$ and $2$. Again, all the cases but the inclusion of $n-3$ and $3$ is counted by $W_{n-5}$. Thus, the total number of subsets which do not include $n$ is given by $W_{n-1}+W_{n-5}+W_{n-9}+\dots$.

Now we will count the subsets which do include $n$. Such subsets must necessarily not include $n-1$ and $1$. All the possibilities except the inclusion of both $n-2$ and $2$ is counted by $W_{n-3}$. Following a process similar to the previous case, we get the number of subsets which include $n$ to be $W_{n-3}+W_{n-7}+W_{n-11}+\dots$

Adding the two cases, we get

$$\begin{array}{rl}{W}_n& =W_{n-1}+W_{n-3}+W_{n-5}+\dots \\ & =W_{n-1}+W_{n-2}\end{array}$$

Thus, $W_n$ satisfies the recurrence relation $W_n=W_{n-1}+W_{n-2}$ for $n\ge 3$, and $W_1=1$ and $W_2=3$. On solving this recurrence relation, we get

$$W_n={\left(\frac{1+\sqrt{5}}{2}\right)}^n+{\left(\frac{1-\sqrt{5}}{2}\right)}^n.$$

---

Problem 4

Let $S_n$ be the set of all bijections from $[n]$ to $[n]$. For each $f\in S_n$, let $L_f$ be the least $k$ such that $f([k])=[k]$. Let $F_{n,k}=\{f\in S_n|L_f=k\}$. Clearly,

$$|S_n|=\sum _{k=1}^n{F}_{n,k}.$$

Now, for all $f\in F_{n,k}$, $f{|}_{[k]}$ is connected, and $f{|}_{[n]\setminus [k]}\in S_{n-k}$. Thus,

$$F_{n,k}=c_k(n-k)!.$$

So, we have

$$n!=|S_n|=\sum _{k=1}^n{c}_k(n-k)!.$$

---

Problem 5

Let $F$ be the infinite product ${\prod }_{n\ge 1}(1+x^n)$. Note that the only terms which contribute to the coefficient $a_n$ of $x^n$ in $F$ are $(1+x^k)$ for $k\le n$. Thus, $F$ is indeed a formal infinite product, since each coefficient can be computed using finite field operations. Now, the value of $a_k$ is precisely equal to the number of ways it can be written as a sum of distinct positive integers, since for each such decomposition there exists a corresponding unique subset of $\{(1+x^k)|1\le k\le n\}$ whose product contributes 1 to $a_n$.

---

Problem 6

Let $P_n\subset S_n$ denote the set of compliant permutations. Then, for $\pi \in P_n$, either $\pi (n)=n$, or $\pi (n)\ne n$. The former case gives us $s(n-1)$ permutations. In the latter case, $\pi (n)$ has $n-1$ possible values, and the remaining $n-2$ numbers can be permuted in $s(n-2)$ ways. Thus, $s(n)=s(n-1)+(n-1)s(n-2)$.

Let

$$g(x)=\sum _{n\ge 0}\frac{s(n)}{n!}{x}^n.$$

Then,

$$\begin{array}{rl}{g}^{\prime }(x)& =\sum _{n\ge 0}\frac{s(n+1)}{n!}{x}^n,\\ xg(x)& =\sum _{n\ge 0}\frac{ns(n-1)}{n!}{x}^n\\ ⟹g(x)+xg(x)& =\sum _{n\ge 0}\frac{s(n)+ns(n-1)}{n!}{x}^n=g^{\prime }(x).\end{array}$$

On integration, we get

$$g(x)=e^{x+x^2/2}.$$

---

Problem 7

$\pi$ is a stack-sortable permutation of $[n]$ iff for every $i<j$ such that $\pi (i)>\pi (j)$, $\pi (j)$ is popped first. This is true iff there does not exist $k$ such that $i<k<j$, $\pi (k)>\pi (i)$, since if such a $k$ existed, $\pi (i)$ would be popped before $\pi (j)$. In other words, for every $i$, all the elements in $[n]$ which are less than $\pi (i)$ and have not appeared in the permutation so far (that is, all $e$ such that $\pi (m)\ne e$, $1\le m<i$) must appear before any element larger than $\pi (i)$ can appear.

Bijection to binary trees

Notation: The permutation $\pi :I\to I$, where $I=\{i_1,i_2,\dots ,i_n\}$ is any ordered index set, is represented by $(\pi (i_1),\pi (i_2),\dots ,\pi (i_n))$.

Let ${\varphi }_n$ be a map from the set of stack-sortable permutations of a set $I$ of cardinality $n$ to the set of binary trees on $n$ vertices. Define ${\varphi }_0(())$ to be the empty tree and ${\varphi }_1((i_1))$ to be the binary tree with one vertex.

We will inductively define ${\varphi }_n$, having defined ${\varphi }_0,{\varphi }_1,\dots ,{\varphi }_{n-1}$. Let $\pi$ be a stack-sortable permutation of $[n]$. Let $k$ be the first index for which $\pi (k)>\pi (1)$. If such a $k$ does not exist, let $k=n+1$. Then, observe that ${\pi }_l=(\pi (2),\pi (3),\dots ,\pi (k-1))$ and ${\pi }_r=(\pi (k),\pi (k+1),\dots ,\pi (n))$ are both stack-sortable permutations of $I_l=\{\pi (2),\pi (3),\dots ,\pi (k-1)\}$ and $I_r=\{\pi (k),\pi (k+1),\dots ,\pi (n)\}$ respectively. Now, define ${\varphi }_n(\pi )$ to be the binary tree whose left subtree is ${\varphi }_{k-2}({\pi }_l)$ and whose right subtree is ${\varphi }_{n-k+1}({\pi }_r)$. For example, ${\varphi }_6(4,3,1,2,6,5)$ would be evaluated like so:

Surjectivity of ${\varphi }_n$
Let $I=[n]$. Consider a binary tree on $n$ vertices, $B$. Let $B_l$ and $B_r$ be its left and right subtrees. Define a permutation $\pi$ on $[n]$ by $\pi (1)\equiv |B_l|+1$, $(\pi (2),\dots ,\pi (|B_l|+1))\equiv {\varphi }_{{}_{|B_l|}}^{-1}(B_l)$, $(\pi (|B_l|+2),\dots ,\pi (n))\equiv {\varphi }_{|B_r|}^{-1}(B_r)+(|B_l|+1)$ (abuse of notation: $|B_l|+1$ is added to each slot of ${\varphi }_{|B_r|}^{-1}(B_r)$). Clearly, ${\varphi }_n(\pi )=B$. Thus, ${\varphi }_n^{-1}(B)$ is non empty for all $B$.

Injectivity of ${\varphi }_n$
Let $\pi \in {\varphi }_n^{-1}(B)$. Then, $\pi (1)$ must have $|B_l|$ elements in $[n]$ that are less than it, and $|B_r|$ elements in $[n]$ that are greater than it. This fixes $\pi (1)$ to be $|B_l|+1$. The same principle applied to the subtrees fixes all $\pi (k)$, $1\le k\le n$. Thus, ${\varphi }_n(\pi )$ is unique for all $\pi$.

Thus, the number of stack sortable permutations of $[n]$ is equal to $C_n$.

---

Problem 8

Part a

FTSOC, assume otherwise. Let $h\in G$ have an irreducible representation as a product of $N+1$ generators, $h\equiv g_{i_1}{g}_{i_2}\dots g_{i_{N+1}}$. It follows that $h_1\equiv g_{i_1}{g}_{i_2}\dots g_{i_N}$ cannot be written as a product of fewer than $N$ generators, since that would imply that $h$ can be written as a product of fewer than $N+1$ generators. Similarly, $h_k\equiv g_{i_1}\dots g_{i_{N+1-k}}$, $1\le k\le N$, cannot be written as a product of fewer than $N+1-k$ generators. It follows that $h\ne h_1\ne h_2\ne \dots \ne h_N$. But, a group of order $N$ cannot have $N+1$ distinct elements in it.

Part b

Note that it is sufficient to solve the problem for the case of the $n$ distinct integers being prime. Let $\{p_1,p_2,\dots ,p_n\}$ be $n$ distinct primes. Then, $a_1,a_2,\dots ,a_N$ is a sequence defined by $a_i=p_{s(i)}$, $1\le s(i)\le n$. For , $j<i$, let the tuple $(a_j,a_{j+1},\dots ,a_i)$ be called an interval and denoted by $(j,i)$. The product of an interval can be expressed as

$$\prod _{k=j}^i{a}_k=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\dots p_n^{{\alpha }_n}.$$

Observe that the product of an interval $(j,i)$ is a perfect square iff ${\alpha }_k\equiv 0\mathrm{mod}2$ for all $1\le k\le n$. Thus, it is beneficial to associate each interval $(i,j)$ with the vector $\varphi (i,j)\equiv ({\alpha }_1\mathrm{mod}2,\dots ,{\alpha }_n\mathrm{mod}2)$ in ${\mathbb{F}}_2^n$. Define $S_k$ like so:

$$\begin{array}{rl}& \\ & S_0\equiv 0\\ & S_1\equiv \varphi (1,1)\\ & S_2\equiv \varphi (1,2)\\ & ⋮\\ & S_N\equiv \varphi (1,N).\end{array}$$

Now, $\varphi (i,j)$ can be computed as $\varphi (1,j)-\varphi (1,i-1)=S_j-S_{i-1}$. So, the product of $(i,j)$ being a perfect square is equivalent to $S_j=S_{i-1}$. Since $|{\mathbb{F}}_2^n|=2^n$ and $N\ge 2^n$ (which implies $N+1>2^n$), we can conclude from the pigeonhole principle that at least two of the $S_k$s must be equal.