Kombinatorik - Bollar(olika) och lådor(lika)

Vi har 6 bollar och 4 lådor. Besvara vardera av följande frågor med ett (explicit uträknat) heltal. På hur många sätt kan vi lägga bollarna i lådorna, om:

c) Bollarna är olika och lådorna är lika?

Går det att lösa denna uppgift med hjälp av "Stirlingtalen"? Alltså:

S(n,k) = S(n - 1, k - 1) + k * S(n-1,k) om 1 < k < n

I så fall hur ska man tolka den formeln? Jag tänkte att:

$S (n - 1, k - 1) = (\begin{matrix} n - 1 \\ k - 1 \end{matrix}) = (\begin{matrix} 5 \\ 3 \end{matrix}) = \frac{n!}{k! (n - k)!} = \frac{5!}{3! * 2!} = 10$

$k * s (n - 1, k) = (\begin{matrix} 5 \\ 4 \end{matrix}) = \frac{5!}{4! * 1} = 5 * 4 = 20$

S(n,k) = S(n - 1, k - 1) + k * S(n-1,k) = 10 + 20 = 30

Rätt svar är: 342

Så något fel har jag gjort i alla fall.

Kanske tänker jag fel nu men jag tycker inte att 342 ser rätt ut.

I vilket fall i rekursionsformeln har du sterlingtal på båda sidor av likhetstecknet. Det stämmer alltså inte att S(n-1,k-1)=C(n-1,k-1).

Vidare Sterlingtalen gäller att placera olika bollar i identiska lådor, så att ingen låda blir tom.

Här har du ingen restriktion på att alla lådor måste vara icke-tomma. Hur hanterar du det?

Jag skulle säga att varje boll kan placeras i fyra olika lådor, så det blir 4⁶=4096 olika varianter, men eftersom de fyra lådorna är identiska vill jag dela med 4!=24 men då blir svaret inget heltal, så det kan inte vara rätt.

Ett träddiagram gav 199 olika varianter, om min son och jag räknade rätt.

Jag får det till 187, vilket jag är rätt säker på att det stämmer, lite nyfiken på var 342 kommer ifrån. 199 låter som att du dubbelräknat något.

Problemet med 4096/24 är att en variant som {1,2,3},{4,5,6} inte kan permuteras på 24 sätt, utan bara på två.

Om jag inte tänkt fel, alternativt om det inte finns någon förutsättning i problemet som inte förmedlats oss, så är Smaragdalenas approach god, alltså i princip enumrera dem. 6 och 4 är såpass små tal att det går. Sedan kan man lösa detta med Stirlingtal men då får man nog se till att ha ordentlig koll på deras definition, samt på hur man beräknar dem.

Sonens Haskell-program säger också 187, och jag har förstått varför det blev fel när vi fick det till 199.

Tack för förklaringen till varför det inte funkar med 4! i nämnaren.

Jag kan ju vara lite mer hjälpsam:

Svaret är s(6,1)+s(6,2)+s(6,3)+s(6,4)

Smutsmunnen skrev:
Jag kan ju vara lite mer hjälpsam:

Svaret är s(6,1)+s(6,2)+s(6,3)+s(6,4)

Ja precis tack man ska alltså upprepa denna formeln. Är det korrekt att formeln är användbar för olika "objekt" i lika "lådor"? Fick du det till 342? Jag har inte räknat på det än.

Nej, det blir inte 342 - du verkar inte ha läst igenom hela tråden.

Efter att ha klurat lite, så tror jag mig ha härlett varifrån du fått 342:

342= (S(6,4)+S(6,3)+S(6,2)+S(6,1))+(S(6,3)+S(6,2)+S(6,1))+(S(6,2)+S(6,1))+S(6,1)

Men det kan jag inte se att det stämmer. Har du fått ett facit eller så som säger 342?

Smutsmunnen skrev:
Efter att ha klurat lite, så tror jag mig ha härlett varifrån du fått 342:
342= (S(6,4)+S(6,3)+S(6,2)+S(6,1))+(S(6,3)+S(6,2)+S(6,1))+(S(6,2)+S(6,1))+S(6,1)
Men det kan jag inte se att det stämmer. Har du fått ett facit eller så som säger 342?

Ja hmm facit säger 342 på denna uppgift. Ska man inte räkna just som du har gjort där då?

Jag ser inte att det skulle vara så nej. Det känns som att någon förutsättning inte förmedlats då.

Kan du själv ge ett argument för den lösningen?

Svara

Visa senaste svar