Znajdź wzór (wyrażony sumą otrzymaną z zasady włączeń i wyłączeń) na liczbę wszystkich ciągów \(\displaystyle{ (Z_1,Z_2,...,Z_n),n>0}\), spełniających warunek \(\displaystyle{ Z_1 \cup Z_2 \cup ... \cup Z_n=\left[k \right]}\), których wyrazami są trzyelementowe podzbiory zbioru \(\displaystyle{ \left[ k\right] (k \ge 3)}\). Zbiór \(\displaystyle{ \left[ k\right]=\left\{ 1,2,3,...,k\right\}}\).
Jak to zrobić? Jakaś wskazówka?
Zasada włączeń i wyłączeń
-
arek1357
- Użytkownik
- Posty: 5747
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 526 razy
Re: Zasada włączeń i wyłączeń
No tak sprawa nie jest zbyt jasna, choćby z tego względu, że piszesz:
wszystkich ciągów:
\(\displaystyle{ (Z_{1},Z_{2},...,Z_{n})}\)
Ale każda permutacja każdego takiego ciągu w zasadzie ma dostarczyć całe.: \(\displaystyle{ [k]}\)
Więc nie powinno się pisać ciągów tylko układów raczej...
Po drugie znam taki wzorek na liczbę.: \(\displaystyle{ k_{ \ge r}}\)(czyli wszystkich elementów) znajdujących się w\(\displaystyle{ r}\) spośród:
\(\displaystyle{ Z_{1},Z_{2},...,Z_{n}}\) zbiorów trójelementowych...
Ten wzór to:
\(\displaystyle{ \sum_{i=r}^{n}(-1)^{i-r} {i-1 \choose r-1}S_{i}^{(n)}}\)
Gdzie:
\(\displaystyle{ S_{i}^{(n)}= \sum_{I \in [n]^i}^{}\left| \bigcap_{j \in I}^{}Z_{j} \right|}\)
Pamiętając, że chodzi o kombinacje wszystkich przecięć...tych zbiorów trójelementowych...
oczywiście z tego względu, że zbiory są trójelementowe powinno być:
\(\displaystyle{ r = \left \lceil \frac{k}{3} \right \rceil}\)
wszystkich ciągów:
\(\displaystyle{ (Z_{1},Z_{2},...,Z_{n})}\)
Ale każda permutacja każdego takiego ciągu w zasadzie ma dostarczyć całe.: \(\displaystyle{ [k]}\)
Więc nie powinno się pisać ciągów tylko układów raczej...
Po drugie znam taki wzorek na liczbę.: \(\displaystyle{ k_{ \ge r}}\)(czyli wszystkich elementów) znajdujących się w\(\displaystyle{ r}\) spośród:
\(\displaystyle{ Z_{1},Z_{2},...,Z_{n}}\) zbiorów trójelementowych...
Ten wzór to:
\(\displaystyle{ \sum_{i=r}^{n}(-1)^{i-r} {i-1 \choose r-1}S_{i}^{(n)}}\)
Gdzie:
\(\displaystyle{ S_{i}^{(n)}= \sum_{I \in [n]^i}^{}\left| \bigcap_{j \in I}^{}Z_{j} \right|}\)
Pamiętając, że chodzi o kombinacje wszystkich przecięć...tych zbiorów trójelementowych...
oczywiście z tego względu, że zbiory są trójelementowe powinno być:
\(\displaystyle{ r = \left \lceil \frac{k}{3} \right \rceil}\)