Podzbiory koszerne
- mol_ksiazkowy
- Użytkownik
- Posty: 11409
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3155 razy
- Pomógł: 748 razy
Podzbiory koszerne
Udowodnić, że ilość podzbiorów \(\displaystyle{ \{ 1,..., n \}}\) takich, że średnia i mediana ich wszystkich elementów są równe jest nieparzysta.
- arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Podzbiory koszerne
Takie zbiory, których średnia arytmetyczna i mediana są równe nazywamy symetrycznymi.
Czyli będą to podzbiory typu:
\(\displaystyle{ \left\{ 1,2,3\right\}}\) w każdym
\(\displaystyle{ \left\{ 1,2,5,6\right\}}\) w np. \(\displaystyle{ 6}\)
Każde dwu i jednoelementowe są symetryczne czyli koszerne, itd...
niech.:\(\displaystyle{ a(n)}\) - oznacza ilość podzbiorów zbiorów koszernych w zbiorze \(\displaystyle{ n}\)- elementowym
zauważmy, że:
\(\displaystyle{ a(n+1)=a(n)+b(n+1)+1}\)
Ja teraz podzieliłem zbiór n+1 elementowy na zbiór n elementowy i jedno elementowy:
\(\displaystyle{ \left\{ 1,...,n,n+1\right\}=\left\{ 1,...,n\right\} \cup \left\{ n+1\right\}}\)
\(\displaystyle{ a(n)}\) - oznacza ile jest zbiorów koszernych w pierwszym \(\displaystyle{ n}\) elementowym zbiorze
\(\displaystyle{ a(n+1)}\) - oznacza ile jest zbiorów koszernych w \(\displaystyle{ \left\{ 1,...,n,n+1\right\}}\) zbiorze.
Natomiast :
\(\displaystyle{ ,b(n+1)}\) - oznacza , ile jest zbiorów koszernych, których ostatni element to:\(\displaystyle{ n+1}\)
Zauważmy, że:
\(\displaystyle{ b(n+1)=b(n)+ \sum_{k=2}^{n+1}b(1,k,n+1)}\)
Teraz należy się wytłumaczenie:
Będę troszkę nieścisły, i \(\displaystyle{ b(n)}\) może oznaczać wszystkie zbiory koszerne, zaczynające się
jedynką i kończące \(\displaystyle{ n}\), lub zaczynające się dwójką i i kończące :\(\displaystyle{ n+1}\) co na jedno wyjdzie.(oczywiście chodzi o ich ilość)
natomiast co znaczy:
\(\displaystyle{ b(1,k,n+1)}\), otóż jest to ilość zbiorów koszernych o pierwszym elemencie w jedynce,
ostatnim w.: \(\displaystyle{ n+1}\) zawierających dokładnie\(\displaystyle{ k}\) elemenów.
Jak widać rekurencja się zgadza...
Łatwo jest obliczyć precyzyjnie.:\(\displaystyle{ b(1,k,n+1)}\)
otóż:
\(\displaystyle{ b(1,k,n+1)= { \frac{n-2}{2} \choose \left[ \frac{k-2}{2} \right] }}\) , dla \(\displaystyle{ n+1}\) - nieparzystych.
\(\displaystyle{ b(1,k,n+1)= { \frac{n-1}{2} \choose \frac{k-2}{2} }}\) , dla \(\displaystyle{ n+1}\) - parzystych
i\(\displaystyle{ k}\)- parzystych.
\(\displaystyle{ b(1,k,n+1)= 0}\) , dla \(\displaystyle{ n+1}\) - parzystych i\(\displaystyle{ k}\)- nieparzystych.
Uprośćmy to, najpierw dla nieparzystych.: \(\displaystyle{ (n+1)}\)
\(\displaystyle{ R= \frac{n-2}{2}}\)
I wtedy:
\(\displaystyle{ \sum_{k=2}^{n+1}b(1,k,n+1)= \sum_{k=2}^{R} {R \choose k}=2^R}\)
teraz weźmy dla parzystych.: \(\displaystyle{ n+1}\)
\(\displaystyle{ r= \frac{n-1}{2}}\)
I wtedy biorąc pod uwagę powyższe rozumowania:
\(\displaystyle{ \sum_{k=2}^{n+1}b(1,k,n+1)= {r \choose 0}+ {r \choose 2}+...}\) ta suma też zawsze jest parzysta, na dole same parzyste...
Więc reasumując zapiszmy zgodnie z tym co wymyśliłem indukcyjnie:
Z:
\(\displaystyle{ a(n)=a(n-1)+b(n)+1}\)
T:
\(\displaystyle{ a(n+1)=a(n)+b(n+1)+1}\)
Dw:
\(\displaystyle{ b(n+1)=b(n)+ \sum_{k=2}^{n+1}b(1,k,n+1)}\)
lub:
(*) \(\displaystyle{ a(n+1)=a(n)+b(n)+ \sum_{k=2}^{n+1}b(1,k,n+1)+1}\)
Dla:\(\displaystyle{ n=1,2,3...}\) - łatwo sprawdzić, że:
\(\displaystyle{ a(1), a(2), a(3),...}\) - są nieparzyste, jak również nieparzyste są:\(\displaystyle{ b(1),b(2), b(3)}\)
czyli z założenia indukcyjnego w wyrażeniu (*) , nieparzyste są:
\(\displaystyle{ a(n), b(n), 1}\)
natomiast parzysta jest:
\(\displaystyle{ \sum_{k=2}^{n+1}b(1,k,n+1)}\)
co wykazaliśmy wyżej, zatem całe \(\displaystyle{ a(n+1)}\) jest nieparzyste
cnd...
A przy okazji wyprowadziłem wzór na ilość zbiorów koszernych=symetrycznych...
Czyli będą to podzbiory typu:
\(\displaystyle{ \left\{ 1,2,3\right\}}\) w każdym
\(\displaystyle{ \left\{ 1,2,5,6\right\}}\) w np. \(\displaystyle{ 6}\)
Każde dwu i jednoelementowe są symetryczne czyli koszerne, itd...
niech.:\(\displaystyle{ a(n)}\) - oznacza ilość podzbiorów zbiorów koszernych w zbiorze \(\displaystyle{ n}\)- elementowym
zauważmy, że:
\(\displaystyle{ a(n+1)=a(n)+b(n+1)+1}\)
Ja teraz podzieliłem zbiór n+1 elementowy na zbiór n elementowy i jedno elementowy:
\(\displaystyle{ \left\{ 1,...,n,n+1\right\}=\left\{ 1,...,n\right\} \cup \left\{ n+1\right\}}\)
\(\displaystyle{ a(n)}\) - oznacza ile jest zbiorów koszernych w pierwszym \(\displaystyle{ n}\) elementowym zbiorze
\(\displaystyle{ a(n+1)}\) - oznacza ile jest zbiorów koszernych w \(\displaystyle{ \left\{ 1,...,n,n+1\right\}}\) zbiorze.
Natomiast :
\(\displaystyle{ ,b(n+1)}\) - oznacza , ile jest zbiorów koszernych, których ostatni element to:\(\displaystyle{ n+1}\)
Zauważmy, że:
\(\displaystyle{ b(n+1)=b(n)+ \sum_{k=2}^{n+1}b(1,k,n+1)}\)
Teraz należy się wytłumaczenie:
Będę troszkę nieścisły, i \(\displaystyle{ b(n)}\) może oznaczać wszystkie zbiory koszerne, zaczynające się
jedynką i kończące \(\displaystyle{ n}\), lub zaczynające się dwójką i i kończące :\(\displaystyle{ n+1}\) co na jedno wyjdzie.(oczywiście chodzi o ich ilość)
natomiast co znaczy:
\(\displaystyle{ b(1,k,n+1)}\), otóż jest to ilość zbiorów koszernych o pierwszym elemencie w jedynce,
ostatnim w.: \(\displaystyle{ n+1}\) zawierających dokładnie\(\displaystyle{ k}\) elemenów.
Jak widać rekurencja się zgadza...
Łatwo jest obliczyć precyzyjnie.:\(\displaystyle{ b(1,k,n+1)}\)
otóż:
\(\displaystyle{ b(1,k,n+1)= { \frac{n-2}{2} \choose \left[ \frac{k-2}{2} \right] }}\) , dla \(\displaystyle{ n+1}\) - nieparzystych.
\(\displaystyle{ b(1,k,n+1)= { \frac{n-1}{2} \choose \frac{k-2}{2} }}\) , dla \(\displaystyle{ n+1}\) - parzystych
i\(\displaystyle{ k}\)- parzystych.
\(\displaystyle{ b(1,k,n+1)= 0}\) , dla \(\displaystyle{ n+1}\) - parzystych i\(\displaystyle{ k}\)- nieparzystych.
Uprośćmy to, najpierw dla nieparzystych.: \(\displaystyle{ (n+1)}\)
\(\displaystyle{ R= \frac{n-2}{2}}\)
I wtedy:
\(\displaystyle{ \sum_{k=2}^{n+1}b(1,k,n+1)= \sum_{k=2}^{R} {R \choose k}=2^R}\)
teraz weźmy dla parzystych.: \(\displaystyle{ n+1}\)
\(\displaystyle{ r= \frac{n-1}{2}}\)
I wtedy biorąc pod uwagę powyższe rozumowania:
\(\displaystyle{ \sum_{k=2}^{n+1}b(1,k,n+1)= {r \choose 0}+ {r \choose 2}+...}\) ta suma też zawsze jest parzysta, na dole same parzyste...
Więc reasumując zapiszmy zgodnie z tym co wymyśliłem indukcyjnie:
Z:
\(\displaystyle{ a(n)=a(n-1)+b(n)+1}\)
T:
\(\displaystyle{ a(n+1)=a(n)+b(n+1)+1}\)
Dw:
\(\displaystyle{ b(n+1)=b(n)+ \sum_{k=2}^{n+1}b(1,k,n+1)}\)
lub:
(*) \(\displaystyle{ a(n+1)=a(n)+b(n)+ \sum_{k=2}^{n+1}b(1,k,n+1)+1}\)
Dla:\(\displaystyle{ n=1,2,3...}\) - łatwo sprawdzić, że:
\(\displaystyle{ a(1), a(2), a(3),...}\) - są nieparzyste, jak również nieparzyste są:\(\displaystyle{ b(1),b(2), b(3)}\)
czyli z założenia indukcyjnego w wyrażeniu (*) , nieparzyste są:
\(\displaystyle{ a(n), b(n), 1}\)
natomiast parzysta jest:
\(\displaystyle{ \sum_{k=2}^{n+1}b(1,k,n+1)}\)
co wykazaliśmy wyżej, zatem całe \(\displaystyle{ a(n+1)}\) jest nieparzyste
cnd...
A przy okazji wyprowadziłem wzór na ilość zbiorów koszernych=symetrycznych...
-
- Użytkownik
- Posty: 826
- Rejestracja: 8 wrz 2013, o 11:31
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Pomógł: 187 razy
Re: Podzbiory koszerne
Niech \(\displaystyle{ X}\) będzie rodziną wszystkich zbiorów koszernych.
Ja bym rozważył funkcję \(\displaystyle{ f\colon X \to X}\) daną wzorem \(\displaystyle{ f\left( A\right) =\left\{ n-a \colon a \in A\right\}}\) i policzył ile ona ma punktów stałych.
Ja bym rozważył funkcję \(\displaystyle{ f\colon X \to X}\) daną wzorem \(\displaystyle{ f\left( A\right) =\left\{ n-a \colon a \in A\right\}}\) i policzył ile ona ma punktów stałych.
-
- Użytkownik
- Posty: 826
- Rejestracja: 8 wrz 2013, o 11:31
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Pomógł: 187 razy
Re: Podzbiory koszerne
\(\displaystyle{ f}\) jest automorfizmem rzędu 2. Liczba jego punktów stałych ma więc taką samą parzystość jak \(\displaystyle{ \left| X\right|}\).
Mała poprawka: powinno być \(\displaystyle{ f\left( A\right) =\left\{ n+1-a \colon a \in A\right\}}\) (z oczywistych względów).
Mała poprawka: powinno być \(\displaystyle{ f\left( A\right) =\left\{ n+1-a \colon a \in A\right\}}\) (z oczywistych względów).
- arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Podzbiory koszerne
Generalnie to\(\displaystyle{ f}\) według mnie jest pewną permutacją zbiorów koszernych na na siebie.
No więc jakie to zbiory będą stanowiły elementy stałe tego przekształcenia.Bo coś dalej tego nie widzę...
Sprawdzałem pobieżnie i \(\displaystyle{ f}\) przekształca zbiór koszerny w zbiór koszerny...
Bo to wymaga małego uzasadnienia...
No więc jakie to zbiory będą stanowiły elementy stałe tego przekształcenia.Bo coś dalej tego nie widzę...
Sprawdzałem pobieżnie i \(\displaystyle{ f}\) przekształca zbiór koszerny w zbiór koszerny...
Bo to wymaga małego uzasadnienia...
-
- Użytkownik
- Posty: 826
- Rejestracja: 8 wrz 2013, o 11:31
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Pomógł: 187 razy
Re: Podzbiory koszerne
Tak, \(\displaystyle{ f}\) jest permutacją \(\displaystyle{ X}\) na siebie i \(\displaystyle{ f \circ f= \mbox{id}}\). Jest to nic innego niż symetria względem punktu \(\displaystyle{ \frac{n+1}{2}}\) na prostej rzeczywistej (tylko że przekształcamy całe zbiory a nie punkty). Przy takiej interpretacji łatwo zliczyć punkty stałe.
- arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Podzbiory koszerne
Czyli zbiór tych wszystkich permutacji będzie typu:
\(\displaystyle{ (x)...(xy).....}\) , na zbiorze, którego elementy są zbiorami koszernymi, jest ich \(\displaystyle{ a(n)}\)
jak wyliczyłem.
Teraz ile jest w tym cykli jednoelementowych czyli stałych...
\(\displaystyle{ (x)...(xy).....}\) , na zbiorze, którego elementy są zbiorami koszernymi, jest ich \(\displaystyle{ a(n)}\)
jak wyliczyłem.
Teraz ile jest w tym cykli jednoelementowych czyli stałych...
-
- Użytkownik
- Posty: 826
- Rejestracja: 8 wrz 2013, o 11:31
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Pomógł: 187 razy
Re: Podzbiory koszerne
Nie całkiem rozumiem o co Ci chodzi Arku.
Moja idea jest taka: definiujemy \(\displaystyle{ f}\) jak wyżej, pokazujemy że \(\displaystyle{ f}\) jest permutacją \(\displaystyle{ X}\) na siebie i \(\displaystyle{ f \circ f= \mbox{id}}\). Zliczamy punkty stałe funkcji \(\displaystyle{ f}\) (skoro \(\displaystyle{ f}\) jest w pewnym sensie symetrią środkową, to takie punkty idzie prosto zliczyć - punkty stały są postaci \(\displaystyle{ A \cup f\left( A\right)}\), gdzie \(\displaystyle{ A \subset \{ 1,..., n \} \cap \left[ 1, \frac{n+1}{2}\right]}\)) i korzystamy z faktu, że \(\displaystyle{ f}\) jest inwolucją, więc liczba jej punktów stałych ma więc taką samą parzystość jak \(\displaystyle{ \left| X\right|}\) (a o parzystości tej ostatniej liczby chcemy rozstrzygać).
Moja idea jest taka: definiujemy \(\displaystyle{ f}\) jak wyżej, pokazujemy że \(\displaystyle{ f}\) jest permutacją \(\displaystyle{ X}\) na siebie i \(\displaystyle{ f \circ f= \mbox{id}}\). Zliczamy punkty stałe funkcji \(\displaystyle{ f}\) (skoro \(\displaystyle{ f}\) jest w pewnym sensie symetrią środkową, to takie punkty idzie prosto zliczyć - punkty stały są postaci \(\displaystyle{ A \cup f\left( A\right)}\), gdzie \(\displaystyle{ A \subset \{ 1,..., n \} \cap \left[ 1, \frac{n+1}{2}\right]}\)) i korzystamy z faktu, że \(\displaystyle{ f}\) jest inwolucją, więc liczba jej punktów stałych ma więc taką samą parzystość jak \(\displaystyle{ \left| X\right|}\) (a o parzystości tej ostatniej liczby chcemy rozstrzygać).
- arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Podzbiory koszerne
No tak teraz już to wszystko widzę dokładnie, punkty stałe to takie, które są środkowosymetryczne,
a obrazem\(\displaystyle{ A}\) jest\(\displaystyle{ f(A)}\),(i też są środkowosymetryczne) (a Ty napisałeś wogóle o tym co wszystko jest stałe, nawet za dużo, ale ok...) .Teraz już bez liczenia wszystko zobaczyłem, pomysł fajny podoba mi się, lecz ja podchodząc do tego zadania, miałem za cel znaleźć wzór na ilość tych zbiorów koszernych, a dowód o ich nieparzystości był dla mnie uboczną i w sumie mało ważną rzeczą.
Bo reasumując zbiory są fajne, funkcję też znalazłeś fajną, fajny jest wzór na ich ilość , i naprawdę wszystko jest fajne, najmniej fajny jest tylko ten niby cel z tego zadania o udowodnieniu nieparzystości,
bo tak naprawdę najmniej mnie obchodziło czy one będą parzyste czy nieparzyste czy mieszane...
a obrazem\(\displaystyle{ A}\) jest\(\displaystyle{ f(A)}\),(i też są środkowosymetryczne) (a Ty napisałeś wogóle o tym co wszystko jest stałe, nawet za dużo, ale ok...) .Teraz już bez liczenia wszystko zobaczyłem, pomysł fajny podoba mi się, lecz ja podchodząc do tego zadania, miałem za cel znaleźć wzór na ilość tych zbiorów koszernych, a dowód o ich nieparzystości był dla mnie uboczną i w sumie mało ważną rzeczą.
Bo reasumując zbiory są fajne, funkcję też znalazłeś fajną, fajny jest wzór na ich ilość , i naprawdę wszystko jest fajne, najmniej fajny jest tylko ten niby cel z tego zadania o udowodnieniu nieparzystości,
bo tak naprawdę najmniej mnie obchodziło czy one będą parzyste czy nieparzyste czy mieszane...