Hej allesammans,
Följande problem kommer nog vara roliga att klura lite på. Det första problemet är ett klassiskt problem som bland annat dyker upp inom dynamisk programmering. Så om ni funderar på att programmera i framtiden så har ni definitivt en head start ;). I det sista problemet har jag tyvärr lagt in partitioner igen (hehe) men konceptet bör inte vara allt för konstigt. Där får ni också se en koppling mellan binomialkoefficienter och sterlingtalet \(S(n,2 )\). Det går även att ge en explicit formel för det mer generella \(S(n,m)\) men det är ett mycket svårare problem.
Uppgift 1 (Rekursion och induktion):
- - - - - - - - - - - - - - - - - - - - - - - - - -
Du står längst ner vid en trappuppgång med \(n\) trappsteg och du vill räkna antalet sätt du kan ta dig från botten till toppen genom att antingen ta \(1\) eller \(2\) steg i taget. T.ex. om det var \(3\) trappsteg så skulle följande möjligheter existera
\( 1 \rightarrow 1 \rightarrow 1\)
\( 1 \rightarrow 2\)
\( 2\rightarrow 1\).
Ge en rekursiv formel för antalet sätt att ta sig från botten till toppen givet \(n\geq 1\) trappsteg och bevisa den m.h.a. matematisk induktion.
Uppgift 2 (Olikheter) :
- - - - - - - - - - - - - - - - - - - - - -
a) Visa att för \(a,b,c \in \mathbb{R}\) så gäller det att
\(|a-c| \leq |a-b| + |b-c|\).
b) Låt \(a_{1} , ..., a_{n}\) och \(b_{1}, ..., b_{n}\) vara sekvenser av reella tal. Visa att
\((\sum_{i=1}^{n} log(a_{i})b_{i}^2)^2 \leq (\sum_{i=1}^{n} (log(a_{i}))^2) (\sum_{i=1}^{n} b_{i}^4) \)
Uppgift 3 (Kombinatorik och partitioner):
- - - - - - - - - - - - - - - - - - - - - -
Låt \(X\) vara en mängd med \(n \geq 2\) element. En partition av \(X\) i \(2\) delar innebär att vi delar upp \(X\) i \(2\) styckna icke tomma, icke namngivna och disjunkta delar \(Y_{1}\) och \(Y_{2}\) där unionen av \(Y_{1}\) och \(Y_{2}\) ger oss tillbaka \(X\). \(S(n,2)\) är antalet möjliga partitioner av \(X\) i \(2\) delar. Visa att
\(S(n , 2 ) = \frac{1}{2} \sum_{k=1}^{n-1} \binom{n}{k}\)
och sedan att
\(S(n ,2) = 2^{n-1} -1\).
(T.ex. om \(X =\{A,B,C\}\) så finns följande möjligheter \(\{A\}, \{B,C\}\) och \(\{B\} , \{A,C\}\) och \(\{C\} ,\{A,B\}\)).
Som vanligt kan ni kontakta mig via emil.eriksson@math.su.se vid eventuella frågor eller funderingar. Allt gott och ta hand om er!
Med Vänliga Hälsningar,
Emil