Pierwszy post na forum a więc witam wszystkich matematyków serdecznie!
Już jakiś czas próbuję bezskutecznie rozwiązać zadanie o takiej treści:
Podaj jawną postać \(\displaystyle{ n}\)-tego wyrazu ciągu \(\displaystyle{ a_{n} =\left\{ \begin{matrix} n\\ n-1\\ \end{matrix} \right\}}\) jako funkcji zmiennej \(\displaystyle{ n}\) i ją uzasadnić.
Znam zależność \(\displaystyle{ S(n,k) = S(n-1,k-1) + k \cdot S(n-1,k), S(0,0) = 1}\). Domyślam się, że trzeba skorzystać z funkcji tworzącej niestety nie wiem jak zacząć. Będę wdzięczny za każdą wskazówkę, pozdrawiam
Podstać jawna ciągu Stirlinga
-
Dyskretnie123
- Użytkownik
- Posty: 4
- Rejestracja: 25 sie 2018, o 16:03
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 3 razy
Podstać jawna ciągu Stirlinga
Ostatnio zmieniony 26 sie 2018, o 00:34 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Nieczytelny zapis - brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm .
Powód: Nieczytelny zapis - brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm .
-
Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Podstać jawna ciągu Stirlinga
Mamy po prostu \(\displaystyle{ \left\{ \begin{matrix} n\\ n-1\\ \end{matrix} \right\}=\frac{n(n-1)}{2}}\)
Uzasadnienie analityczne:
kładąc w podanym przez Ciebie wzorze rekurencyjnym \(\displaystyle{ k:=n-1}\) mamy
\(\displaystyle{ \left\{ n \atop n-1\right\}=\left\{n-1 \atop n-2\right\}+(n-1)\left\{n-1 \atop n-1\right\}}\)
Oczywiście \(\displaystyle{ \left\{n-1 \atop n-1\right\}=1}\) (na jeden tylko sposób możemy podzielić zbiór o \(\displaystyle{ n-1}\) elementach na \(\displaystyle{ n-1}\) niepustych podzbiorów – singletony), więc oznaczając
\(\displaystyle{ a_n=\left\{ n \atop n-1\right\}}\) otrzymujesz
\(\displaystyle{ a_n=a_{n-1}+n-1, \ n=1,2,\ldots}\)
Ponadto oczywiście \(\displaystyle{ a_1=0}\). Stąd dla \(\displaystyle{ n>1}\):
\(\displaystyle{ a_n=a_1+ \sum_{k=2}^{n}(a_k-a_{k-1})=\\=a_1+ \sum_{k=2}^{n}(k-1)=\\=\sum_{k=2}^{n}(k-1)=\frac{n(n-1)}{2}}\)
Uzasadnienie kombinatoryczne:
rozbijamy zbiór \(\displaystyle{ n}\)-elementowy na \(\displaystyle{ n-1}\) niepustych podzbiorów (parami rozłącznych oczywiście). Zatem będzie jeden podzbiór dwuelementowy i \(\displaystyle{ n-2}\) singletonów.
Na \(\displaystyle{ {n \choose 2}=\frac{n(n-1)}{2}}\) sposobów wybieramy spośród tych \(\displaystyle{ n}\) elementów elementy podzbioru dwuelementowego. Co do pozostałych elementów, wyboru już nie mamy, rozbijamy na singletony.
Uwaga na \(\displaystyle{ n=1}\), ale tak się składa, że wtedy też wzór działa.
Uzasadnienie analityczne:
kładąc w podanym przez Ciebie wzorze rekurencyjnym \(\displaystyle{ k:=n-1}\) mamy
\(\displaystyle{ \left\{ n \atop n-1\right\}=\left\{n-1 \atop n-2\right\}+(n-1)\left\{n-1 \atop n-1\right\}}\)
Oczywiście \(\displaystyle{ \left\{n-1 \atop n-1\right\}=1}\) (na jeden tylko sposób możemy podzielić zbiór o \(\displaystyle{ n-1}\) elementach na \(\displaystyle{ n-1}\) niepustych podzbiorów – singletony), więc oznaczając
\(\displaystyle{ a_n=\left\{ n \atop n-1\right\}}\) otrzymujesz
\(\displaystyle{ a_n=a_{n-1}+n-1, \ n=1,2,\ldots}\)
Ponadto oczywiście \(\displaystyle{ a_1=0}\). Stąd dla \(\displaystyle{ n>1}\):
\(\displaystyle{ a_n=a_1+ \sum_{k=2}^{n}(a_k-a_{k-1})=\\=a_1+ \sum_{k=2}^{n}(k-1)=\\=\sum_{k=2}^{n}(k-1)=\frac{n(n-1)}{2}}\)
Uzasadnienie kombinatoryczne:
rozbijamy zbiór \(\displaystyle{ n}\)-elementowy na \(\displaystyle{ n-1}\) niepustych podzbiorów (parami rozłącznych oczywiście). Zatem będzie jeden podzbiór dwuelementowy i \(\displaystyle{ n-2}\) singletonów.
Na \(\displaystyle{ {n \choose 2}=\frac{n(n-1)}{2}}\) sposobów wybieramy spośród tych \(\displaystyle{ n}\) elementów elementy podzbioru dwuelementowego. Co do pozostałych elementów, wyboru już nie mamy, rozbijamy na singletony.
Uwaga na \(\displaystyle{ n=1}\), ale tak się składa, że wtedy też wzór działa.