Stirlingtall av andre type

Her kan brukere av forum utfordre hverandre med morsomme oppgaver og nøtter man ønsker å dele med andre. Dette er altså ikke et sted for desperate skrik om hjelp, de kan man poste i de andre forumene, men et sted for problemløsing på tvers av trinn og fag.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

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}$
Kake med tau
Dirichlet
Dirichlet
Innlegg: 159
Registrert: 05/02-2013 14:12
Sted: Fetsund

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]
"If you really want to impress your friends and confound your enemies, you can invoke tensor products… People run in terror from the $\otimes$ symbol." - en professor ved Standford
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

Flott!
DennisChristensen
Grothendieck
Grothendieck
Innlegg: 826
Registrert: 09/02-2015 23:28
Sted: Oslo

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.$$
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

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 :D
Svar