MTH4150 Home

# MTH 4150: Midterm 2 Practice 2

Problem 1

Determine the cycle representation of the permutation $$\left(\begin{array}{cccccccc} 1&2&3&4&5&6&7&8\newline 3&8&1&4&7&2&5&6\end{array}\right)$$.

Problem 2

Assume that $$a_n=3$$ for $$n\geq 0$$. Let $$F$$ be the generating function of the sequence $$(a_n)_{n=0}^{\infty}$$. Determine $$F\left(\frac12\right)$$.

Problem 3

Let $$a_n$$ be the number of ways to distribute $$n$$ apples to $$5$$ people so that all of the following 3 conditions are satisfied:

• (i) The first person gets at least 3 apples;

• (ii) The second person gets an even number of apples;

• (iii) The third person gets a number of apples divisible by $$7$$.

Determine the generating function for the sequence $$(a_n)_{n=0}^{\infty}$$. You do not need to evaluate $$a_n$$.

Problem 4

Let $$f=(1592)(374)(68)$$ and $$g=(173)(248)(596)$$ be two permutations on the set $$\{1$$, $$2$$, $$3$$, $$4$$, $$5$$, $$6$$, $$7$$, $$8$$, $$9\}$$.

• (a) Determine $$f\circ g$$.

• (b) Determine the permutation $$h$$ for which $$f\circ h =g$$.

Problem 5

Denote by $$a_n$$ the number of sequences of length $$n$$ consisting of letters from the set $$\{A,B,C\}$$ such that no two letters $$A$$ are consecutive.

• (a) Find integers $$p$$ and $$q$$ such that for all $$n\geq 1$$ the following equality holds: $a_{n+2}=pa_{n+1}+qa_n. \quad\quad\quad(1)$

• (b) Prove that if we set $$a_0=1$$, then (1) remains to hold for $$n= 0$$.

• (c) Find a simple, closed-form expression for the generating function $$G(X)$$ of the sequence $$(a_n)_{n=0}^{\infty}$$. Do not solve for the sequence $$a_n$$.

Problem 6

Let $$a_n$$ denote the number of ways to distribute $$n$$ apples to $$10$$ people such that the first person gets an even number of apples. Let $$t_n$$ be the total number of ways to distribute $$n$$ apples to $$10$$ people.

• (a) Find the generating functions for the sequences $$(a_n)_{n=0}^{\infty}$$ and $$(t_n)_{n=0}^{\infty}$$.

• (b) Prove that $$2\cdot a_{100} > t_{100}$$.

Problem 7

• (a) Prove that for every positive integer $$n$$ and every permutation $$f$$ on $$S=\{1,2,3,\dots, n\}$$ there exists a positive integer $$k$$ such that $\underbrace{f\circ f\circ f\circ\cdots\circ f}_k=\mbox{id},$ where $$\mbox{id}$$ denotes the identity permutation.

• (b) Assume that $$f$$ is a permutation that contains exactly two cycles: one of length $$15$$ and the other of length $$20$$. Determine the smallest integer $$k\geq 1$$ such that $$\underbrace{f\circ f\circ f\circ\cdots\circ f}_k=\mbox{id}$$.