Dela in elever i grupper

Ställ upp alla elever i klassen på en rad, sätt sedan in skiljeväggar mellan dem. Det är E elever, så det finns E-1 platser att sätta väggar på. För att göra G grupper sätter du in G-1 väggar. Du har alltså att sätta in G-1 väggar på E-1 platser. På hur många sätt kan man göra det? Svaret är $\left(\begin{array}{c}E-1\\ G-1\end{array}\right)=\left(\frac{(E-1)!}{(G-1)!\times (E-G)!}\right)$. Det här problemet (eller metoden att lösa det) kallas för "stars and bars", och det finns material på wikipedia att läsa om hur man ska räkna.

Men... Jag tycker inte att det där rätt svar. Det där säger visserligen hur man löser det kombinatoriska problemet, men om Sara, Olle och Kalle är i klassen och man kan ska göra två grupper, så tycker jag att man kan göra det på tre sätt -- jag tror åtminstone att Sara, Olle och Kalle skulle hålla med -- angingen är Sara ensam, och Olle och Kalle i en grupp, eller så är Olle ensam... Ja, du fattar -- det finns tre sätt att göra en sån indelning. Svaret som uttrycken ovan ger är 2. Den tvåan betyder att man kan antingen göra första gruppen med två medlemma och andra med 1, eller första med 1 och andra med 2. Jag tycker ett mer korrekt sätt att beskriva antalet sätt man kan dela en klass i G grupper är tar hänsyn till vilka andra personer en person delar grupp med. Problemet är att jag inte kan förstå hur man ska räkna det.

Om du kommer på hur man ska göra så är jag intresserad av att veta -- har vi tur så kommer kanske @albiki och löser problemet (det är jag övertygad om att hen kan), men just nur kan jag inte lösa det jag tycker är det intressanta problemet som tar hänsyn till vilka som är medlemmar i grupperna.

Det låter som ett svårt problem om man inte läst kombinatorik (och även om man bara läst kombinatorik på gymnasiet).

Jag håller med om PeBos tolkning i diskussionen om att det inte känns som rätt svar med stars-and-bars (som ger antal sätt att dela upp i grupper av olika storlek men inte tar hänsyn till vilka som ingår i respektive grupp).

Svaret på problemet är per definition Stirlingtalen av andra slaget (https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind) som är antal sätt att dela upp E elever i G icke-tomma grupper S(E,G). Det stämmer med S(3,2) = 3.

Man kan räkna ut Stirlingtalen av andra slaget med rekursionen

$S(n+1,k) =\hspace{0.17em}kS(n,k)+S(n,k-1)$ med begynnelsevillkoren $S(0,0)\hspace{0.17em}=\hspace{0.17em}1$ och $S(n,0) =\hspace{0.17em}S(0,n)\hspace{0.17em}=\hspace{0.17em}0$ för $n>0$, som enkelt kan resoneras fram till genom att med n+1 elever kan man antingen lägga till den sista eleven i någon av de k grupper man kan få med n elever eller skapa en ny grupp med den sista eleven ensam i den gruppen.

Det finns tyvärr ingen enklare explicit formel än summationsformeln

$S(n,k) =\hspace{0.17em}\frac{1}{k!}\sum _{j=0}^k(-1{)}^{k-j}\left(\begin{array}{c}k\\ j\end{array}\right) j^n$

Summationsformeln kan man resonera sig fram till med principen om inklusion-exklusion, med $k^n$ får vi ett gruppnummer per elev men vissa grupper kan vara tomma, så om man drar bort de $k(k-1{)}^n$ där (minst) en grupp är tom och sen adderar tillbaks de vi drog bort för mycket, osv. Faktorn framför summan är att det spelar ingen roll vad vi kallar de olika grupperna.

Tack @dioid!

Kan man säga att uppgiften antingen är missförstådd av @Paradisa, eller att den är för svår? Eller är det meningen att man ska känna till, google-hitta (även det rätt svårt) eller härleda Stirling-talen av andra slaget?

Hursomhelst -- jag lärde mig något.

:)