Książki na półkach

[stiifii]

Mamy \(\displaystyle{ n}\) różnych książek i \(\displaystyle{ k}\) różnych półek. Kolejność książek na pólkach ma znaczenie.
a) Ile jest sposobów na umieszczenie książek na półkach?
b)Ile jest sposobów, jeśli półki nie mogą być puste?

Rozwiązanie wygląda następująco:

ad.a)
\(\displaystyle{ \[\frac{(n+k-1)!}{(k-1)!}\]}\)

ad.b
\(\displaystyle{ \binom{n}{k} k!\[\frac{(n-1)!}{(k-1)!}\]}\)

Czy jest ono poprawne? Wydaje mi się, że ono nie uwzględnia różnej kolejności książek na półkach.

[arek1357]

W pierwszym

\(\displaystyle{ \sum_{x_{1}+...+x_{k}=n}^{} {n \choose x_{1},x_{2},...,x_{k}} x_{1}! \cdot ... \cdot x_{k}!=n! \cdot {n+k-1 \choose n}}\)

W drugim analogicznie:

\(\displaystyle{ \sum_{x_{1}+...+x_{k}=n ,x_{i} \ge 1}^{} {n \choose x_{1},x_{2},...,x_{k} } x_{1}! \cdot ... \cdot x_{k}!=n! \cdot {n-1 \choose k-1}}\)

poprawa wiadomości.

[tomwanderer]

a)
niech \(\displaystyle{ \cdot}\) oznacza książkę, a \(\displaystyle{ \setminus}\) oznacza półkę. Stosujemy konwencję, że zapis np. \(\displaystyle{ \setminus \cdot \cdot \setminus \setminus \cdot}\) oznacza, że na pierwszej półce są 2 książki, na drugiej ani jednej, na trzeciej jest jedna.
Najpierw wybieramy sekwencję złożoną ze znaków \(\displaystyle{ \cdot}\) oraz \(\displaystyle{ \setminus}\), przy czym musi się ona zaczynać od \(\displaystyle{ \setminus}\). Sprowadza się to do określenia \(\displaystyle{ k-1}\) miejsc dla symboli \(\displaystyle{ \setminus}\) wśród \(\displaystyle{ n+k-1}\) wszystkich miejsc. Możemy to zrobić na \(\displaystyle{ {n+k-1 \choose k-1}}\) sposobów. Podany wzór otrzymamy po uwzględnieniu, że kolejność książek ma znaczenie.

b)
Najpierw na każdą półkę położymy książkę. Wybieramy więc \(\displaystyle{ k}\) książek na \(\displaystyle{ {n \choose k}}\) sposobów. Domnażamy przez \(\displaystyle{ k!}\), aby uwzględnić kolejność. Pozostaje nam \(\displaystyle{ n-k}\) książek do rozstawienia na \(\displaystyle{ k}\) półkach. Postępując jak w a), tym razem mamy \(\displaystyle{ (n-k)+k-1=n-1}\) miejsc, na których mamy ustawić tym razem \(\displaystyle{ k-1}\) par symboli \(\displaystyle{ \setminus \cdot}\) (bo na każdej półce już jest książka). Po domnożeniu przez \(\displaystyle{ (n-k)!}\) (uwzględniamy kolejność książek, które pozostały), otrzymujemy żądany wzór.

[arek1357]

co do a).Ten wzór już się sypie przy np: 2 półkach i 3 książkach.

1,2,3
\ - tu już masz 6 możliwości


\
1,2,3 - tu też 6 możliwości

teraz na górnej jest dwie książki a na dolnej jedna jest już też sześć możliwości + na odwrót kolejne sześć masz już 24 możliwości a teraz z twego wzoru:

\(\displaystyle{ {2+3-1 \choose 2-1}=4}\)

lipa...

Nie uwzględniasz, że półki i książki są rozróżnialne więc każde ułożenie jest inne

Jest tu złożenie kombinacji z powtórzeniem wraz z permutacjami na półkach...
w moim wzorze jest to założenie wzięte pod uwagę!

w b). pewnie też nie będzie lepiej.

[kerajs]

a):    

Niech na półce/półkach stoi już p-1 książek. Liczba miejsc na dowolnej półce (półce x) jaką ma do wyboru nowa książka (p-eta) jest zawsze większa o 1 od liczby książek (i_x) które na niej stoją (jest to także prawdą dla pustej półki oferującej 0+1 miejsc). Czyli p-ta książka ma do wyboru:
\(\displaystyle{ (i_1+1)+(i_2+1)+....(i_k+1)=i_1+i_2+...+i_k+k \cdot 1=p-1+k=p+k-1}\)
Pierwsza książka ma \(\displaystyle{ 1+k-1=k}\) możliwych miejsc do wybrania.
Druga książka ma \(\displaystyle{ 2+k-1=k+1}\) możliwych miejsc do wybrania.
...
P-eta książka ma \(\displaystyle{ p+k-1}\) możliwych miejsc do wybrania.
...
N-ta książka ma \(\displaystyle{ n+k-1}\) możliwych miejsc do wybrania.
Ilość możliwych ustawień:
\(\displaystyle{ (k) \cdot (k+1) \cdot ... \cdot (p+k-1) \cdot ... \cdot (n+k-1)= \frac{1 \cdot ... \cdot (k-1) \cdot \left[ k(k+1) \cdot ... \cdot (p+k-1) \cdot ... \cdot (n+k-1)\right] }{1 \cdot ... \cdot (k-1)}=\\= \frac{(n+k-1)!}{(k-1)!}}\)

b):    

Wybieram k książek i ustawiam na k półkach. Robię to na \(\displaystyle{ {n \choose k}k!}\) sposobów.
Dalej postępuję jak w a)
k+1 książka ma \(\displaystyle{ k+1+k-1=2k}\) możliwych miejsc do wybrania.
k+2 książka ma \(\displaystyle{ k+2+k-1=2k+1}\) możliwych miejsc do wybrania.
...
N-ta książka ma \(\displaystyle{ n+k-1}\) możliwych miejsc do wybrania.
Ilość możliwych ustawień:
\(\displaystyle{ {n \choose k}k! \cdot (2k) \cdot (2k+1) \cdot ... \cdot (n+k-1)= {n \choose k}k! \cdot \frac{(n+k-1)!}{(2k-1)!}}\)

[tomwanderer]

arek1357, podstawiłeś pod zły wzór. Moje wzory są dokładnie takie, jak w pierwszym poście. Ja napisałem do nich uzasadnienie.

[arek1357]

Gdzie jest źle w moim wzorze?


dla n=3, k=2 wychodzi 24 tyle ile ma być u ciebie nie, wzór kerajsa jest też ok , wychodzi to samo

U mnie jest prosto łączę kombinacje z permutacjami i wszystko trybi

[tomwanderer]

Chodzi mi o to, że tutaj, chcąc liczyć z mojego wzoru, użyłeś złego wzoru:

\(\displaystyle{ {2+3-1 \choose 2-1}=4}\)

Bo ja napisałem:

Możemy to zrobić na \(\displaystyle{ {n+k-1 \choose k-1}}\) sposobów. Podany wzór otrzymamy po uwzględnieniu, że kolejność książek ma znaczenie.

Pisząc "podany" mam na myśli ten z pierwszego posta. "Po uwzględnieniu, że kolejność książek ma znaczenie", czyli po przemnożeniu przez \(\displaystyle{ n!}\).