W klasie jest n uczniów

[max123321]

W klasie jest \(\displaystyle{ n}\) uczniów. Stoją oni w jednym szeregu przed wychowawcą, który ma ich podzielić na dowolną liczbę niepustych zespołów (w szczególności zespołów może być \(\displaystyle{ 1}\) lub \(\displaystyle{ n}\)) i w każdym z zespołów wyznaczyć szefa. Zespół może składać się wyłącznie z uczniów stojących kolejno w szeregu. Na ile różnych sposobów wychowawca może tego dokonać? Ułóż odpowiednie równanie lub układ równań rekurencyjnych i wyznacz wzór ogólny.

Jak to zrobić?

[Premislav]

Oznaczmy \(\displaystyle{ a_{n,k}}\) – liczba sposobów wyróżnienia zgodnie z opisaną procedurą \(\displaystyle{ k}\) grup z szeregu \(\displaystyle{ n\ge k}\) uczniów. Mamy
\(\displaystyle{ a_{n, k+1}= \sum_{j=k}^{n-1}a_{j,k}(n-j)}\)
oraz oczywiście \(\displaystyle{ a_{n,1}=n}\) (mamy jedną grupę i na \(\displaystyle{ n}\) sposobów dobieramy szefa).
Wyliczamy, że o ile \(\displaystyle{ n\ge2}\), to
\(\displaystyle{ a_{n,2}= \sum_{j=1}^{n-1} a_{j, 1}(n-j)= \sum_{j=1}^{n-1}j(n-j)= \frac{n^2(n-1)}{2} - \frac{(n-1)n(2n-1)}{6}= \frac{(n+1)n(n-1)}{6}={n+1\choose 3}}\)
Podobnież
\(\displaystyle{ a_{n,3}= \sum_{j=2}^{n-1}a_{j,2}(n-j}= \sum_{j=2}^{n-1} {j+1\choose 3}(n-j)=\ldots={n+2\choose 5}}\)
Patrzymy tak na te wartości… a może jest \(\displaystyle{ a_{n,k}={n+k-1\choose 2k-1}}\)

Dowód jest indukcyjny (po \(\displaystyle{ k\le n}\), przy ustalonym \(\displaystyle{ n}\)). Choć nie wykluczam, że da się ułożyć ładniejszą zależność rekurencyjną niż ta, którą zaproponowałem i może wtedy da się bez indukcji.-- 5 sie 2019, o 00:32 --Właściwie to nie do końca przy ustalonym, bo potrzebna nam jest indukcja zupełna. W kroku indukcyjnym założenie jest takie: dla dowolnego \(\displaystyle{ k\le j<n}\) jest
\(\displaystyle{ a_{j,k}={j+k-1\choose 2k-1}}\). A teza: dla dowolnego \(\displaystyle{ k+1\le j\le n}\) jest
\(\displaystyle{ a_{j,k+1}={j+k\choose 2k+1}}\), czy coś w ten deseń. Sprawę załatwia to, że
\(\displaystyle{ \sum_{j=k}^{n-1}{j+k-1\choose 2k-1}(n-j)={n+k\choose 2k+1}}\).

A to też idzie indukcją, tym razem po \(\displaystyle{ n\ge k+1}\) przy ustalonym \(\displaystyle{ k}\). Choć można sprytniej.

[max123321]

Czekaj, bo za bardzo nie rozumiem tego wzoru:
\(\displaystyle{ a_{n, k+1}= \sum_{j=k}^{n-1}a_{j,k}(n-j)}\)
Z czego to wynika?

[Premislav]

Ustawiliśmy w szeregu \(\displaystyle{ n}\) uczniów i wyróżniliśmy \(\displaystyle{ k+1}\) grup zgodnie z opisaną regułą, po czym w każdej wybraliśmy szefa. Popatrzmy na ostatniego spośród szefów grup w tym szeregu (czyli gościa, który został szefem grupy nr \(\displaystyle{ k+1}\)). Będzie miał on jeden spośród numerów \(\displaystyle{ k+1, \ldots n}\) (skoro jest w szeregu przed nim co najmniej \(\displaystyle{ k}\) szefów, to w szczególności co najmniej \(\displaystyle{ k}\) osób). „Przed nim" uformowano \(\displaystyle{ k}\) grup, każdej wyznaczając szefa, to znaczy dla pewnego \(\displaystyle{ j\in \left\{ k, k+1, \ldots n-1\right\}}\) powstało \(\displaystyle{ k}\) grup z wyróżnionym członkiem (czyli szefem) na
\(\displaystyle{ a_{j, k}}\) sposobów. Grupa tego ostatniego szefa ma wtedy liczebność \(\displaystyle{ n-j}\) (bo będą do niej należały osoby o numerach \(\displaystyle{ j+1,j+2 \ldots n}\) w szeregu), czyli tego szefa ostatniej grupy możemy wybrać na \(\displaystyle{ n-j}\) sposobów.

Stąd ten wzorek
\(\displaystyle{ a_{n, k+1}= \sum_{j=k}^{n-1}a_{j,k}(n-j)}\)
Może się da ułożyć ładniejszą rekurencję, ale ja nie umiem.

[max123321]

Ok, dzięki wielkie. To już chyba rozumiem, ale teraz nie wiem skąd jest ta równość:
\(\displaystyle{ \sum_{j=1}^{n-1}j(n-j)= \frac{n^2(n-1)}{2} - \frac{(n-1)n(2n-1)}{6}}\)
Z czego to wynika?

[Premislav]

Rozbiłem to na dwie sumy:
\(\displaystyle{ \sum_{j=1}^{n-1}j(n-j)= \sum_{j=1}^{n-1}jn- \sum_{j=1}^{n-1}j^2\\= n\sum_{j=1}^{n-1}j- \sum_{j=1}^{n-1}j^2}\)
i zastosowałem znane wzory:
\(\displaystyle{ \sum_{j=1}^{k}j=\frac{k(k+1)}{2}\\ \sum_{j=1}^{k}j^2=\frac{k(k+1)(2k+1)}{6}}\)
dla \(\displaystyle{ k:=n-1}\).