Worki (nierozroznialne) i kule(pozycja nierozroznialna)

[author]

Otoz jest 60 kulek (rozroznialnych) i 30 workow nierozroznialnych. Pozycja kulek w workach jest nierozroznialna. Na ile sposobow mozna umiescic te kule w tych workach, jezeli kazdy worek pomiescic moze wszystkie kule i zaden worek nie moze byc pusty.
Problem dla mnie w tym tkwi jak zwalczyc ta nierozroznialnosc workow... czytalem o podobnym problemie w ksiazce Matma dajskretna i tam stwierdzono niby ze nie ma jakiegos uniwersalnego rozwiazania

Probowalem cos z funkcjami "na", ze kazdej kulce mozna by przyporzadkowac jeden z workow. Ale szkopul w tej nierozroznialnosci workow hmm... bo podzielic przez k! ilosc wszystkich suriekcji ze zbioru |A|=60 do |B|=30 to raczej hyhyhyhy...

Moze ktos z Was spotkal sie z tym problemem wczesniej i zna odpowiedz?

[półpasiec]

tak wiec pomysl z przegrodkami byl do bani, bo liczylismy jako rozne takie ustawienia
o| o o| o o o
o o |o o o |o
chociaz dla nas sa indentyczne
wniosek plynie takie ze musimy poszukac ciagow dlugosci k, sumujacych sie do n, a do tego posortowanych
jesli piszesz ze nie ma ladnego wzoru to moze rzeczywiscie nie ma, chociaz da sie je rozwiazac rekurencyjnie, ale to raczej komputer by mogl obliczyc. co nie znaczy ze twierdze ze rozwiazania dokladnego nie ma
niech \(\displaystyle{ D_{n,k,i}}\) oznacza liczbe posortowanych ciagow \(\displaystyle{ k}\) liczb, ktore sumuja sie do \(\displaystyle{ n}\), a najmniejszy skladnik ma wartosc \(\displaystyle{ i}\)
no to teraz niech pierwszy skladnik ma wartosc 1 wtedy reszte ustawiamy na \(\displaystyle{ D_{n-1,k-1,1}}\) sposobow.
ogolnie niech pierwszy skladnik ma wartosc \(\displaystyle{ j}\) wtedy reszte ustawiamy na \(\displaystyle{ D_{n-j,k-1,j}}\)
ale zauwazmy ze dla \(\displaystyle{ j>1}\) mozna \(\displaystyle{ D_{n-j,k-1,j}}\) inaczej zapisac: kazdy skladnik bedzie dlugosci j i bedzie ich k-1 wiec my i tak mamy niemobilne pierwszych (k-1)(j-1) miejsc wiec usuniemy je i bedziemy rozwazac znowu te ciagi gdzie pierwszy ma dlugosc 1 czyli \(\displaystyle{ D_{n-j,k-1,j}=D_{n-(k-1)(j-1),k-1,1}}\)
no i wystarczy to zsumowac od i=1 do ilustam

[author]

nie powiem, zeby bylo to oczywiste
A wiec rekurencja... poczytam, podumam i pewnie skumam
Dzieki za zaangażowanie w problem!