Discrete Mathematics B

Old exam: 2000-01-08

TENTAMEN I MATEMATIK
DISKRET MATEMATIK B FÖR DATATEKNIK
Datum: 2000-1-8
Skrivtid: 5h
Hjälpmedel: Inga
Vincent Moulton, Mitthögskolan

Lösningarna skall vara presenterade på ett sådant sätt att räkningar och
resonemang blir lätta att följa.
Ett svar utan motivering ger 0 poäng!

1. Are the following statements true or false? Explain your answer!
(a) The number of partitions S(7,3) of a 7-set into 3 parts is equal to 305.
(b) The permutation

$\begin{displaymath}\pmatrix{1&2&3&4&5&6&7&8\cr 2&1&4&5&7&6&3&8} \end{displaymath}$

is even.
(c) The remainder when 3³⁶ is divided by 17 is 5.
(d) There are three mutually non-isomorphic trees with 5 vertices.
(e) The coefficient of x⁵y²z³ in (x+y+z)¹⁰ is 1031.
(f) It is possible to find a design with parameters (7,2,3). (9p)

2. Give a combinatorial argument using sets to show that

$\begin{displaymath}{n \choose r} = {n-1 \choose r-1} + {n-1 \choose r} \end{displaymath}$

for $n,r \in \mbox{\sf I\hspace*{-0.1em}N}$ , $1 \le r \le n$ . (4p)

3. How many ways are there to arrange the letters

K E D H M Å J

(a) in a sequence?
(b) in a sequence that contains the word HEJ?
(c) in a sequence that does not contain either of the words HEJ and DÅ? (3p)

4. (a) Find the first five terms in the sequence $(a_n)_{n \ge 0}$ defined by a₀=1, a₁= 1, and

$\begin{displaymath}a_n = 3 a_{n-1} - 2 a_{n-2} + 2^n, \,\,\, n\ge 2. \end{displaymath}$

(b) Find a formula for a_n. Check your answer using (a). (4p)

5. Do a breadth-first search (BFS) and a depth-first search (DFS) on the graph which has the following adjacency list:

a	b	c	d	e	f	g	h	i
b	d	e	b	c	e	h	g	g
	c	f	e	d	c	i
		b	g	f

Is this graph connected? (4p)

6. Let $X := \{1,2,3,\dots,n\}$ , $n \ge 2$ . Consider the following algorithm:

$\bf y:= 1;$ for each non-empty subset $\bf S$ of $\bf X$ do

begin

$\bf y := y * \mbox{ least member of} \, \, S$

end;

$\bf p:= y$

(a) If n= 4, then what will the output p be?
(b) If we take * as the significant operation in the loop, then what is the efficiency of this algorithm in terms of n?
(c) If we replace the second line of the algorithm by

for each 2-subset $\bf S$ of $\bf X$ do

then what is the efficiency of this new algorithm in terms of n? (4p)

7. (a) Without using generating functions, find the number of integer solutions to

x₁ + x₂ + x₃ + x₄ + x₅ = 11

where $0 \le x_1, x_5$ , and $1 \le x_2, x_3, x_4$ .
(b) Explain why the answer you got for (a) is equal to the coefficient of x¹¹ in

$\begin{displaymath}f(x) = (1+x+x^2+ \dots)^2 (x+x^2+x^3+\dots)^3. \end{displaymath}$

$\begin{displaymath}f(x) = \frac{x^3}{(1-x)^5}. \end{displaymath}$

(d) Use the formula in (c) to find the coefficient of x¹¹ in f(x). (4p)

TENTAMEN I MATEMATIK
DISKRET MATEMATIK B FÖR DATATEKNIK
Datum: 2000-1-8
Skrivtid: 5h
Hjälpmedel: Inga
Vincent Moulton, Mitthögskolan

Lösningarna skall vara presenterade på ett sådant sätt att räkningar och
resonemang blir lätta att följa.
Ett svar utan motivering ger 0 poäng!

1. Är följande påståenden sanna eller falska? Motivera dina svar!
(a) Antalet partitioner S(7,3) av en 7-mängd i 3 delar är 305.
(b) Permutationen

$\begin{displaymath}\pmatrix{1&2&3&4&5&6&7&8\cr 2&1&4&5&7&6&3&8} \end{displaymath}$

är jämn.
(c) Resten när 3³⁶ delas med 17 är 5.
(d) Det finns tre inbördes icke-isomorfa träd med 5 hörn.
(e) Koefficienten framför x⁵y²z³ i (x+y+z)¹⁰ är 1031.
(f) Det är möjligt att hitta en design med parametrar (7,2,3). (9p)

2. Ge ett kombinatoriskt argument med mängder för att visa att

$\begin{displaymath}{n \choose r} = {n-1 \choose r-1} + {n-1 \choose r} \end{displaymath}$

för $n,r \in \mbox{\sf I\hspace*{-0.1em}N}$ , och $1 \le r \le n$ . (4p)

3. På hur många sätt kan man arrangera bokstäverna

K E D H M Å J

(a) i en följd?
(b) i en följd som inhåller ordet HEJ?
(c) i en följd som inte innehåller något av orden HEJ och DÅ? (3p)

4. (a) Hitta de första fem termerna i följden $(a_n)_{n \ge 0}$ definierad av a₀=1, a₁= 1, och

$\begin{displaymath}a_n = 3 a_{n-1} - 2 a_{n-2} + 2^n, \,\,\, n\ge 2. \end{displaymath}$

(b) Hitta en formel för a_n. Kontrollera ditt svar genom att avända (a). (4p)

5. Gör en bredd-före-djup sökning (BFS) samt en djup-före-bredd sökning (DFS) till grafen som har följande grannlista:

a	b	c	d	e	f	g	h	i
b	d	e	b	c	e	h	g	g
	c	f	e	d	c	i
		b	g	f

Är denna graf sammanhängande? (4p)

6. Låt $X := \{1,2,3,\dots,n\}$ , $n \ge 2$ . Betrakta algoritmen:

$\bf y:= 1;$ for varje icke-tom delmängd $\bf S$ av $\bf X$ do

begin

$\bf y := y * \mbox{ minsta elementet i } \, \, S$

end;

$\bf p:= y$

(a) Om n= 4, vad blir utdata p?
(b) Om * är loopens signifikanta operation, vad är algoritmens effektivitet i termer av n?
(c) Om vi byter ut algoritmens andra rad mot

for varje 2-delmängd $\bf S$ av $\bf X$ do

vad blir effektiviteten hos den nya algoritmen? (4p)

7. (a) Utan att använda genererande funktioner, hitta antalet heltalslösningar till

x₁ + x₂ + x₃ + x₄ + x₅ = 11

där $0 \le x_1, x_5$ , och $1 \le x_2, x_3, x_4$ .
(b) Förklara varför ditt svar i (a) är lika med koefficienten för x¹¹ i

$\begin{displaymath}f(x) = (1+x+x^2+ \dots)^2 (x+x^2+x^3+\dots)^3. \end{displaymath}$

$\begin{displaymath}f(x) = \frac{x^3}{(1-x)^5}. \end{displaymath}$

(d) Använd formeln i (c) för att hitta koefficienten för x¹¹ i f(x). (4p)

Vincent Moulton
© 2000, MITTHÖGSKOLAN
Institutionen för Fysik och Matematik
Mitthögskolan
SE-851 70 SUNDSVALL
Sweden
Updated 000412.