matematikk.net

For positive heltall $n,m$ der $n\geq m$ definerer vi ${n\brace m}$ som antallet forskjellige partisjoner av en mengde med $n$ elementer, i $m$ ikketomme delmengder. F.eks. er ${3\brace 2}=3$ siden det er tre måter å dele opp tre elementer i to delmengder:
$\{1\},\{2,3\}$
$\{2\},\{1,3\}$ og
$\{3\},\{1,2\}$.

Finn et uttrykk for ${n\brace 2}$

Kanskje noe sånt?

Med [tex]n[/tex] elementer er det [tex]\begin{Bmatrix} n\\2 \end{Bmatrix}[/tex] måter å partisjonere [tex]n[/tex] elementer i to mengder. Hvis vi legger til et nytt element har vi for enhver partisjonering 2 muligheter å plassere den, og vi har i tillegg én ny partisjonering: [tex](1 2 3 4 \dots n) (n+1)[/tex]. Så [tex]\begin{Bmatrix} n+1\\2 \end{Bmatrix}=2\begin{Bmatrix} n\\2 \end{Bmatrix}+1[/tex].
Løser rekursjonen [tex]a_{n+1}=2a_{n}+1[/tex]:

[tex]f(x)=\sum_{i=1}^{\infty}a_ix^i[/tex]
[tex]f(x)=a_1x+(2a_1+1)x^2+(2a_2+1)x^3+\dots[/tex]
[tex]f(x)=a_1+2xf(x)+x^2(1+x+x^2\dots)[/tex], med [tex]a_1=0[/tex]
[tex]f(x)(1-2x)=\frac{x^2}{1-x}[/tex]
[tex]f(x)=\frac{x^2}{(1-2x)(1-x)}=\sum_{i=2}^{\infty}(2^{i-1}-1)x^i[/tex]

Så [tex]\begin{Bmatrix} n\\2 \end{Bmatrix}=2^{n-1}-1[/tex]

Flott!

plutarco skrev:For positive heltall $n,m$ der $n\geq m$ definerer vi ${n\brace m}$ som antallet forskjellige partisjoner av en mengde med $n$ elementer, i $m$ ikketomme delmengder. F.eks. er ${3\brace 2}=3$ siden det er tre måter å dele opp tre elementer i to delmengder:
$\{1\},\{2,3\}$
$\{2\},\{1,3\}$ og
$\{3\},\{1,2\}$.

Finn et uttrykk for ${n\brace 2}$

Eventuelt:

Vi ønsker å dele en mengde $M$ inn i to delmengder $m_1$ og $m_2$. For hvert element $x$ i $M$ har vi to valg: Enten $x \in m_1$ eller $x \in m_2$. Dette gir $2^n$ mulige partisjoner. Vi kan riktignok ikke ha $\forall x, x \in m_1$ eller $\forall x, x \in m_2$, så vi må ekskludere disse to scenariene. Til slutt retter vi opp dobbeltellingen som har forekommet (ved å bytte navn på $m_1 \leftrightarrow m_2$ får vi ingen ny partisjon, men vi har telt dette som to forskjellige scenarier. $$\therefore {n\brace 2} = \frac{2^n - 2}{2} = 2^{n-1} - 1.$$

DennisChristensen skrev:
Eventuelt:

Vi ønsker å dele en mengde $M$ inn i to delmengder $m_1$ og $m_2$. For hvert element $x$ i $M$ har vi to valg: Enten $x \in m_1$ eller $x \in m_2$. Dette gir $2^n$ mulige partisjoner. Vi kan riktignok ikke ha $\forall x, x \in m_1$ eller $\forall x, x \in m_2$, så vi må ekskludere disse to scenariene. Til slutt retter vi opp dobbeltellingen som har forekommet (ved å bytte navn på $m_1 \leftrightarrow m_2$ får vi ingen ny partisjon, men vi har telt dette som to forskjellige scenarier. $$\therefore {n\brace 2} = \frac{2^n - 2}{2} = 2^{n-1} - 1.$$

Jepp, det var slik jeg også løste den