[ Bude83 @ 23.09.2005. 00:01 ] @
Zadatak glasi:
Na koliko načina možemo n različitih predmeta razmjestiti u r različitih kutija, tako da tačno 3 kutije ostanu prazne? A barem tri prazne?

Riješenje:
Ja sam njuškajući po nekim knjigam, sveskam, skriptama...došao do zaključka da se ovo može predstavitikao broj svih surjekcija Nn->Nm.
=Σ(-1)^(x-j)(x nad j)*j^n (suma ide od 0 do x)
Gdje je x - broj kutija, a n - broj predmeta. U mom prvom slučaju x=r-3 i to je to.

Sada drugi dio zadatka koji kaže da barem tri kutije ostanu prazne. Znači mogu ostati 3,4,5,...,r-1 prazne kutije. Ja sam mislio da ovo napišem samo kao sumu svih ovih surjekcija. Tj. ako mi je (r-3) kutija popunjeno + (r-4) + (r-5) ... +(1). Znači predhodnu formulu da sumiram još od 1 do r-3.

Da li je ovaj moj način razmišljanja ispravan.Ako sam negdje pogriješio može li mi neko pomoći oko ovoga zadatka.
[ Farenhajt @ 20.12.2005. 19:39 ] @
Da bi tačno tri kutije ostale prazne, prvo moraš da odabereš te tri kutije koje će ostati prazne. To očito možeš uraditi na načina. Preostalim kutijama dodelićeš redne brojeve od do . Sada ti se smeštanje predmeta u kutije svodi na to da svakom predmetu dodeliš redni broj kutije u koju ćeš ga staviti - ili, kombinatorno rečeno, da broja rasporediš na mesta, pri čemu je poredak bitan, a ponavljanje dozvoljeno. Dakle, dobijaš varijacije s ponavljanjem, kojih ima . Ukupno, dakle, imaš .

Da bi bar tri kutije ostale prazne, sumiraćemo gornji izraz od kutije do kutije (uzimamo zdravo za gotovo da se predmeti moraju smestiti u bar jednu kutiju):
(gde smo uveli smenu i uzeli u obzir da je ).

[Ovu poruku je menjao Farenhajt dana 20.12.2005. u 20:40 GMT+1]