Matematyka.pl

Ile jest ciągów \(\displaystyle{ k}\) wyrazowych \(\displaystyle{ (A_1,...,A_k) }\) podzbiorów zbioru \(\displaystyle{ n}\) elementowego \(\displaystyle{ X}\) takich, że \(\displaystyle{ A_1 \subset ... \subset A_k}\) ?

Ponieważ część autorów używa relacji \(\displaystyle{ \subset}\) i \(\displaystyle{ \subseteq}\) wymiennie, a część nie, to czy w tym zadaniu \(\displaystyle{ A_1 \subset A_2}\) oznacza:
1) że zbiór \(\displaystyle{ A_1}\) jest mniej liczny niż zbiór \(\displaystyle{ A_2}\)
2) że zbiór \(\displaystyle{ A_1}\) może być równoliczny jak zbiór \(\displaystyle{ A_2 }\)?

Jeśli dopuszczamy równości kolejnych zbiorów, to wynikiem jest \((k+1)^n\). Jeśli każdy kolejny ma być nadzbiorem właściwym poprzedniego, to \(\displaystyle{ (k+1)^n-(k-1)\cdot k^n+\binom{k-1}{2}\cdot(k-1)^n-\ldots+(-1)^{k-1}\binom{k-1}{k-1}\cdot1^n}\)

Coś w tym wzorze jest nie tak choćby to, że na końcu nie może być \(\displaystyle{ 1^n}\) prędzej \(\displaystyle{ 2^n}\)

Ale wiele to i tak nie da, najprędzej początek powinien zaczynać się od \(\displaystyle{ k^n}\)

Ale też chyba nie do końca...

arek1357 pisze: ↑28 sty 2023, o 11:48 Coś w tym wzorze jest nie tak choćby to, że na końcu nie może być \(\displaystyle{ 1^n}\) prędzej \(\displaystyle{ 2^n}\)

Racja, w ostatnim wyrazie powinno być \(2^n\), bo zliczamy tam przypadki, gdy wszystkie podzbiory są równe: \(A_1=A_2=\ldots=A_k\), czyli mamy po prostu wybrać dowolny jeden podzbiór zbioru \(X\).

arek1357 pisze: ↑28 sty 2023, o 11:48 Ale wiele to i tak nie da, najprędzej początek powinien zaczynać się od \(\displaystyle{ k^n}\)

A tu opowiadasz bajki. Zaczyna się od wyboru dowolnych podzbiorów \(A_1\subseteq A_2\subseteq\ldots\subseteq A_k\), czyli dla każdego z \(n\) elementów zbioru \(X\) mamy \(k+1\) możliwości. Będzie należał do \(A_1\) albo do \(A_2\setminus A_1\) albo do \(A_3\setminus A_2\) albo ... albo do \(X\setminus A_k\).

To w takim razie napisz ten wzór tak jak ma wyglądać...

Jeśli dopuszczamy równości kolejnych zbiorów, to \(\displaystyle{ (k+1)^n}\). Jeśli nie, to musimy odrzucić przypadki, gdy w którymś miejscu wystąpi równość. Jest \(k-1\) miejsc w ciągu, w których mogła zajść równość pomiędzy kolejnymi zbiorami. Odrzucamy te przypadki zgodnie ze wzorem włączeń i wyłączeń:

\(\displaystyle{ (k+1)^n-(k-1)\cdot k^n+\binom{k-1}{2}\cdot(k-1)^n-\ldots+(-1)^{k-1}\binom{k-1}{k-1}\cdot2^n = \sum_{l=0}^{k-1}(-1)^l \binom{k-1}{l}\cdot(k+1-l)^n }\)

arek1357 pisze: ↑24 sty 2023, o 10:39 I po co dawać rybę ja dałem wędkę...

Przepraszam za podanie ryby, ale tym razem inaczej się nie dało.

Jeszcze jedno pytanie czy wliczasz w to zbiór pusty?

Myślę że to pytanie dasz radę sam rozstrzygnąć. Podpowiem Ci, że dla \(k=1\) wynikiem jest \(2^n\), czyli liczba wszystkich podzbiorów zbioru \(n\)-elementowego.