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}\).