Jeśli ktoś miał by chwile to bardzo bym prosił o wyjaśnienie kilku zagadnień których rozwiązania nigdzie nie moge znaleźć z konfiguracji kombinatorycznych a mianowicie:
1) jakie są warunki na istnienie t-konfiguracji kombinatorycznej. (np jak obliczyć: "oblicz konfiguracje lub uzasadnij że nie istnieje: (n,k,r) = (6,3,1) i (n,k,r) = (7,3,3) "
2) jeśli mam zbiór X , #X = n, to jak obrazowo można zrozumieć że rodzina k-podzbiorów X jest t-kombinatoryczna.
z góry thx za odp.
t-konfiguracja kombinatoryczna
t-konfiguracja kombinatoryczna
Definicja
Niech X zbior, oraz \(\displaystyle{ \left | X \right |=v}\).
Zbior B zlozony z k-elementowych podzbiorow zbioru X nazywamy t-konfiguracja z parametrami \(\displaystyle{ (v,k,r_{t})}\)
jesli dla kazdego t-podzbioru T zbioru X (t-podzbior oznacza podzbior o licznosci t) liczba podzbiorow zbioru B zawierajacych T jest rowna \(\displaystyle{ r_{t}}\).
Definicja troche zawila, wiec moze dwa przyklady:
Przyklad 1
1-konfiguracja z parametrami: v=8, k=4, \(\displaystyle{ r_{1}=3}\) wyglada nastepujaca:
1234, 5678, 1357, 2468, 1247, 3568
W tym przykladzie mamy zbior \(\displaystyle{ X=\left \{ 1,2,3,4,5,6,7,8 \right \}}\)
Chcemy wybrac takie 4-elementowe podzbiory (k=4), by kazdy podzbior jedno elementowy z X
(t=1) wystapil dokladnie w trzech (wybranych 4-elementowych) podzbiorach.
1 znajduje sie w podzbiorach 1234, 1357, oraz 1247
2 znajduje sie w podzbiorach 1234, 2468, oraz 1247
3 znajduje sie w podzbiorach 1234, 1357, oraz 3568
itd...
Czy jest to 2-konfiguracja (kazdy podzbior dwu elementowy z X wystepuje dokladnie w \(\displaystyle{ r_{2}}\) wybranych podzbiorach)?
Oczywiscie nie jest to 2-konfiguracja. Przykladowo \(\displaystyle{ \left \{ 1,2 \right \}}\) wystepuje 2 razy: 1234 i 1247 podczas gdy \(\displaystyle{ \left \{ 1,5 \right \}}\) wystepuje tylko raz: 1357, a podzbior \(\displaystyle{ \left \{ 1,6 \right \}}\) wogole nie wystepuje.
Przyklad 2
3-konfiguracja z parametrami: v=8, k=4, \(\displaystyle{ r_{3}=1}\) wyglada nastepujaca:
1235, 1346, 1457, 1568, 1267, 1378, 1248, 4678, 2578, 2368, 2347, 3458, 2456, 3567
Mozna sprawdzic ze kazdy 3 elementowy podzbior zbioru \(\displaystyle{ X=\left \{ 1,2,...,8 \right \}}\) zawiera sie dokladnie w jednej z wypisanych wyzej czworek.
Na koniec jeszcze dwa przydatne twierdzenia (bez dowodow):
Twierdzenie
Jesli B jest t-konfiguracja to dla s=1,2,...,t-1 istnieja s-konfiguracje.
Z powyzszego twierdzenia (wlasciwie z jego dowodu, ktorego nie przytaczam) wynika nastepujaca rownosc:
\(\displaystyle{ r_{t-1}=r_{t}*\frac{v-t+1}{k-t+1}}\)
Twierdzenie
(i) Jesli B jest t-konfiguracja z parametrami \(\displaystyle{ (v,k,r_{t})}\) wowczas, rozwazajac B jako s-konfiguracje, dla \(\displaystyle{ 0\leq s\leq t-1}\), parametr \(\displaystyle{ r_{s}}\) wynosi
\(\displaystyle{ r_{s}=r_{t}*\frac{(v-s)(v-s-1)...(v-t+1)}{(k-s)(k-s-1)...(k-t+1)}}\)
(ii) Jesli istnieje t-konfiguracja z parametrami \(\displaystyle{ (v,k,r_{t})}\), wowczas dla kazdego s, \(\displaystyle{ 0\leq s\leq t-1}\), musi zachodzic podzielnosc:
\(\displaystyle{ (k-s)(k-s-1)...(k-t+1)|r_{t}(v-s)(v-s-1)...(v-t+1)}\)
Niech X zbior, oraz \(\displaystyle{ \left | X \right |=v}\).
Zbior B zlozony z k-elementowych podzbiorow zbioru X nazywamy t-konfiguracja z parametrami \(\displaystyle{ (v,k,r_{t})}\)
jesli dla kazdego t-podzbioru T zbioru X (t-podzbior oznacza podzbior o licznosci t) liczba podzbiorow zbioru B zawierajacych T jest rowna \(\displaystyle{ r_{t}}\).
Definicja troche zawila, wiec moze dwa przyklady:
Przyklad 1
1-konfiguracja z parametrami: v=8, k=4, \(\displaystyle{ r_{1}=3}\) wyglada nastepujaca:
1234, 5678, 1357, 2468, 1247, 3568
W tym przykladzie mamy zbior \(\displaystyle{ X=\left \{ 1,2,3,4,5,6,7,8 \right \}}\)
Chcemy wybrac takie 4-elementowe podzbiory (k=4), by kazdy podzbior jedno elementowy z X
(t=1) wystapil dokladnie w trzech (wybranych 4-elementowych) podzbiorach.
1 znajduje sie w podzbiorach 1234, 1357, oraz 1247
2 znajduje sie w podzbiorach 1234, 2468, oraz 1247
3 znajduje sie w podzbiorach 1234, 1357, oraz 3568
itd...
Czy jest to 2-konfiguracja (kazdy podzbior dwu elementowy z X wystepuje dokladnie w \(\displaystyle{ r_{2}}\) wybranych podzbiorach)?
Oczywiscie nie jest to 2-konfiguracja. Przykladowo \(\displaystyle{ \left \{ 1,2 \right \}}\) wystepuje 2 razy: 1234 i 1247 podczas gdy \(\displaystyle{ \left \{ 1,5 \right \}}\) wystepuje tylko raz: 1357, a podzbior \(\displaystyle{ \left \{ 1,6 \right \}}\) wogole nie wystepuje.
Przyklad 2
3-konfiguracja z parametrami: v=8, k=4, \(\displaystyle{ r_{3}=1}\) wyglada nastepujaca:
1235, 1346, 1457, 1568, 1267, 1378, 1248, 4678, 2578, 2368, 2347, 3458, 2456, 3567
Mozna sprawdzic ze kazdy 3 elementowy podzbior zbioru \(\displaystyle{ X=\left \{ 1,2,...,8 \right \}}\) zawiera sie dokladnie w jednej z wypisanych wyzej czworek.
Na koniec jeszcze dwa przydatne twierdzenia (bez dowodow):
Twierdzenie
Jesli B jest t-konfiguracja to dla s=1,2,...,t-1 istnieja s-konfiguracje.
Z powyzszego twierdzenia (wlasciwie z jego dowodu, ktorego nie przytaczam) wynika nastepujaca rownosc:
\(\displaystyle{ r_{t-1}=r_{t}*\frac{v-t+1}{k-t+1}}\)
Twierdzenie
(i) Jesli B jest t-konfiguracja z parametrami \(\displaystyle{ (v,k,r_{t})}\) wowczas, rozwazajac B jako s-konfiguracje, dla \(\displaystyle{ 0\leq s\leq t-1}\), parametr \(\displaystyle{ r_{s}}\) wynosi
\(\displaystyle{ r_{s}=r_{t}*\frac{(v-s)(v-s-1)...(v-t+1)}{(k-s)(k-s-1)...(k-t+1)}}\)
(ii) Jesli istnieje t-konfiguracja z parametrami \(\displaystyle{ (v,k,r_{t})}\), wowczas dla kazdego s, \(\displaystyle{ 0\leq s\leq t-1}\), musi zachodzic podzielnosc:
\(\displaystyle{ (k-s)(k-s-1)...(k-t+1)|r_{t}(v-s)(v-s-1)...(v-t+1)}\)