Matematické Fórum

vlado_bb · 12. 02. 2018 05:43

Dobry den,

pri zistovani poctu monotonnych abelovskych monoidov na istych typoch zvazov som sa dostal k nasledujucemu problemu: Nech $A=(a_{ij})$ je obdlznikova matica. Kolkymi sposobmi je mozne vybrat podmnozinu jej prvkov $B$ , pe ktoru plati: ak $a_{kl}, a_{mn} \in B$ , tak NIE JE $k < m$ a sucasne $l<n$ . Inymi slovami - ak je nejaky prvok v mnozine $B$ , nesmie v $B$ byt uz prvok od neho "vlavo hore" ani "vpravo dolu". Vec je jasna pri pocte prvkov mnoziny $B$ rovnom jednej a takisto pri najvacsom moznom, co je minimum z poctu riadkov a stlpcov, ale pri inych mohutnostiach to vidim na pomerne netrivialny kombinatoricky problem. Nevie o tom niekto nieco viac?

Dakujem.

jarrro · 12. 02. 2018 07:17

Nezáleží aj na konkrétnom zväze?
Btw je to $k\not{\!\!<}m\ \&\ l< n$ ?
Alebo $\neg{$k< m\ \&\ l< n$}$

vlado_bb

↑ jarrro: $\neg{$k< m\ \&\ l< n$}$ .

Od zvazu zavisi iba pocet riadkov a stlpcov.

jarrro · 12. 02. 2018 11:48

Aha indexy sú prirodzené ja som somár
Vlastne sa to dá preformulovať na
Nech $m,n\in\mathbb{N}\nl M=\{k;k\in\mathbb{N}\ \&\ k\leq m\}\nl N=\{k;k\in\mathbb{N}\ \&\ k\leq n\}$
Nech $\mathcal{C}=\{C;C\subset M\times N:$\forall i,j,k,l$$\(i,j$,$k,l$\in C\Rightarrow i\geq k \| j\geq l\)\}$
Určte $\left|\mathcal{C}\right|$
Je to tak?

vlado_bb · 12. 02. 2018 12:17

↑ jarrro: Ano, tak.

check_drummer · 14. 02. 2018 22:06

↑ vlado_bb:
Ahoj, není maximální možnou mohutností B spíše maximum (a nikoli minimum) z počtu řádků a sloupců? Pokud totiž vezmu všechny prvky libovolného pevného řádku a nebo sloupce, tak ty mohou tvořit množinu B...

vlado_bb

↑ check_drummer: Mate pravdu - tak, ako som to napisal, by to bolo maximum. Spravna podmienka znie:

ak $a_{kl}, a_{mn}$ su navzajom rozne prvky $B$ , tak NIE JE $k \le m$ a sucasne $l \le n$ .

check_drummer

↑ vlado_bb:
Škoda, už jsem sestrojil rekurentní vztah pro ten předchozí případ. :-) Tak se zamyslím nad tímto.
Jinak dokonce by v tom předchozím případě mohla mít B až "počet řádků"+"počet sloupců"-1 prvků, protože by vyhovělo vzít dohromady dolní řádek a pravý sloupec.

vlado_bb · 15. 02. 2018 20:47

↑ check_drummer: Ak by sa podarilo najst rekurentny vztah, nic viac nemozem chciet :) Poslal som vam aj privatnu spravu.

check_drummer

↑ vlado_bb:
Je-li matice A typu mxn a označím-li počet těch podmnožin B jako f(m,n), tak mi vychází rekurentní vztah:

(Edit: Neuvažoval jsem prázdnou množinu - a s ní se rekurentní vzorec pro f zjednoduší) na: f(m+1.n+1)=f(m+1,n)+f(m,n+1), kde f(1,1)=2 a položíme f(0,n)=f(m,0)=0 - a na základě toho lze pro funkci f odvodit jednoduchý explicitní vzorec, a sice $f(m,n)={m+n \choose n}$ .

Edit: Opravil jsem předchozí chybu a začal uvažovat prázdnou množinu.

check_drummer

Ahoj, nejsem si jist, zda je správné toto:

jarrro napsal(a):
$$\forall i,j,k,l$$\(i,j$,$k,l$\in C\Rightarrow i\geq k \| j\geq l\)$

Kromě toho, že bylo výše upřesněno, že nerovnosti v zadání mají být neostré, tak si myslím, že podmínka výše, pokud zaměníme (i,j) a (k,l) a pokud platí současně $k \leq i$ a $l\leq j$ , tak je to přesně totéž, čemu se chceme podle zadání vyhnout. Ale nejspíš jsi výrok formálně negoval, tak někde bude nějaká logická chyba, možná v mé úvaze, to také nevylučuji.
Já bych to formuloval spíš takto:
$$\forall i,j,k,l$$\(i,j$,$k,l$\in C\Rightarrow ((i < k \& j > l) \| (i > k \& j < l))\)$

Totiž výrok, který máš negovat, není jen $i \leq k \& j \leq l$ , ale je to $(i \leq k \& j \leq l) \| (k \leq i \& l \leq j)$ . A jeho negací a "roznásobením" vzniklého logického výrazu na základě toho, že spojka $\&$ je distributivní vzhledem k $\|$ získáme můj tvar výše.

jarrro · 16. 02. 2018 10:58

Myslím, že to je jedno, lebo ak $$\exists i,j,k,l$$\(i,j$,$k,l$\in C\& (i \leq k\& j \leq l)\)$ tak aj
$$\exists i,j,k,l$$\(i,j$,$k,l$\in C\& ((i \geq k \| j \leq l) \& (i \leq k \| j \geq l))\)$ (stačí vziať tú istú štvoricu)
podobne ak $$\exists i,j,k,l$$\(i,j$,$k,l$\in C\& ((i \geq k \| j \leq l) \& (i \leq k \| j \geq l))\)$ tak $$\exists i,j,k,l$$\(i,j$,$k,l$\in C\& (i \leq k\& j \leq l)\)$ (buď pôvodná vyhovuje alebo (k,l,i,j) vyhovuje či mi niečo ušlo?

check_drummer · 19. 02. 2018 21:58

↑ jarrro:
Pardon, neuvědomil jsem si, že používáš implikaci a nikoli ekvivalenci (což je běžnější, definuje-li se nový pojem - zde množina C).

vlado_bb

↑ check_drummer: Mili priatelia, dakujem este raz za spolupracu, uloha je s vasou pomocou vyriesena.

check_drummer · 20. 02. 2018 20:11

Ještě přidám pro úplnost rekurentní vztah pro případ, že by v zadání platily neostré nerovnosti. Značení je podobné jako v příspěvku #11. Pak mi vychází f(m+1,n+1)=2.(f(m+1,n)+f(m,n+1)-f(m,n)), f(1,1)=2. Explicitní vzorec se mi nepodařilo nalézt, pravděpdoobně bude poměrně komplikovaný. Ale lze ukázat, že $2^{\max(m,n)}$ dělí f(m,n).

Matematické Fórum

#1 12. 02. 2018 05:43

Vyber prvkov v matici

#2 12. 02. 2018 07:17

Re: Vyber prvkov v matici

#3 12. 02. 2018 08:09 — Editoval vlado_bb (12. 02. 2018 08:10)

Re: Vyber prvkov v matici

#4 12. 02. 2018 10:23 — Editoval jarrro (12. 02. 2018 11:36) Příspěvek uživatele jarrro byl skryt uživatelem jarrro. Důvod: Somarina

#5 12. 02. 2018 11:48

Re: Vyber prvkov v matici

#6 12. 02. 2018 12:17

Re: Vyber prvkov v matici

#7 14. 02. 2018 22:06

Re: Vyber prvkov v matici

#8 14. 02. 2018 22:16 — Editoval vlado_bb (14. 02. 2018 22:16)

Re: Vyber prvkov v matici

#9 15. 02. 2018 20:36 — Editoval check_drummer (15. 02. 2018 20:38)

Re: Vyber prvkov v matici

#10 15. 02. 2018 20:47

Re: Vyber prvkov v matici

#11 15. 02. 2018 22:38 — Editoval check_drummer (19. 02. 2018 12:26)

Re: Vyber prvkov v matici

#12 16. 02. 2018 00:32 — Editoval check_drummer (16. 02. 2018 01:03)

Re: Vyber prvkov v matici

jarrro napsal(a):

#13 16. 02. 2018 10:58

Re: Vyber prvkov v matici

#14 19. 02. 2018 21:58

Re: Vyber prvkov v matici

#15 20. 02. 2018 09:42 — Editoval vlado_bb (20. 02. 2018 09:45)

Re: Vyber prvkov v matici

#16 20. 02. 2018 20:11

Re: Vyber prvkov v matici

Zápatí