Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
!! 17.06.2018 (Jel.) Khanova škola zve nadšence ke spolupráci na překladech návodů pro učitele a rodiče.
! 04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17.01.2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17.01.2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 12. 02. 2018 05:43

vlado_bb
Moderátor
Příspěvky: 3484
Škola:
Reputace:   96 
 

Vyber prvkov v matici

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.

Offline

  • (téma jako vyřešené označil(a) vlado_bb)

#2 12. 02. 2018 07:17

jarrro
Příspěvky: 4878
Škola: UMB BB Matematická analýza
Reputace:   276 
Web
 

Re: Vyber prvkov v matici

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


MATH IS THE BEST!!!

Offline

 

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

vlado_bb
Moderátor
Příspěvky: 3484
Škola:
Reputace:   96 
 

Re: Vyber prvkov v matici

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

Od zvazu zavisi iba pocet riadkov a stlpcov.

Offline

 

#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

jarrro
Příspěvky: 4878
Škola: UMB BB Matematická analýza
Reputace:   276 
Web
 

Re: Vyber prvkov v matici

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?


MATH IS THE BEST!!!

Offline

 

#6 12. 02. 2018 12:17

vlado_bb
Moderátor
Příspěvky: 3484
Škola:
Reputace:   96 
 

Re: Vyber prvkov v matici

↑ jarrro: Ano, tak.

Offline

 

#7 14. 02. 2018 22:06

check_drummer
Příspěvky: 2554
Reputace:   66 
 

Re: Vyber prvkov v matici

↑ 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...


Nikdy nechibuji.

Offline

 

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

vlado_bb
Moderátor
Příspěvky: 3484
Škola:
Reputace:   96 
 

Re: Vyber prvkov v matici

↑ 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$.

Offline

 

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

check_drummer
Příspěvky: 2554
Reputace:   66 
 

Re: Vyber prvkov v matici

↑ 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.


Nikdy nechibuji.

Offline

 

#10 15. 02. 2018 20:47

vlado_bb
Moderátor
Příspěvky: 3484
Škola:
Reputace:   96 
 

Re: Vyber prvkov v matici

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

Offline

 

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

check_drummer
Příspěvky: 2554
Reputace:   66 
 

Re: Vyber prvkov v matici

↑ 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.


Nikdy nechibuji.

Offline

 

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

check_drummer
Příspěvky: 2554
Reputace:   66 
 

Re: Vyber prvkov v matici

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.


Nikdy nechibuji.

Offline

 

#13 16. 02. 2018 10:58

jarrro
Příspěvky: 4878
Škola: UMB BB Matematická analýza
Reputace:   276 
Web
 

Re: Vyber prvkov v matici

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?


MATH IS THE BEST!!!

Offline

 

#14 19. 02. 2018 21:58

check_drummer
Příspěvky: 2554
Reputace:   66 
 

Re: Vyber prvkov v matici

↑ 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).


Nikdy nechibuji.

Offline

 

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

vlado_bb
Moderátor
Příspěvky: 3484
Škola:
Reputace:   96 
 

Re: Vyber prvkov v matici

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

Offline

 

#16 20. 02. 2018 20:11

check_drummer
Příspěvky: 2554
Reputace:   66 
 

Re: Vyber prvkov v matici

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).


Nikdy nechibuji.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson