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
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗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
Stránky: 1
Dobry den,
pri zistovani poctu monotonnych abelovskych monoidov na istych typoch zvazov som sa dostal k nasledujucemu problemu: Nech je obdlznikova matica. Kolkymi sposobmi je mozne vybrat podmnozinu jej prvkov , pe ktoru plati: ak , tak NIE JE a sucasne . Inymi slovami - ak je nejaky prvok v mnozine , nesmie v byt uz prvok od neho "vlavo hore" ani "vpravo dolu". Vec je jasna pri pocte prvkov mnoziny 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
↑ 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...
Offline
↑ check_drummer: Mate pravdu - tak, ako som to napisal, by to bolo maximum. Spravna podmienka znie:
ak su navzajom rozne prvky , tak NIE JE a sucasne .
Offline
↑ 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.
Offline
↑ check_drummer: Ak by sa podarilo najst rekurentny vztah, nic viac nemozem chciet :) Poslal som vam aj privatnu spravu.
Offline
↑ 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 .
Edit: Opravil jsem předchozí chybu a začal uvažovat prázdnou množinu.
Offline
Ahoj, nejsem si jist, zda je správné toto:
jarrro napsal(a):
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ě a , 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:
Totiž výrok, který máš negovat, není jen , ale je to . 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.
Offline
↑ 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).
Offline
↑ check_drummer: Mili priatelia, dakujem este raz za spolupracu, uloha je s vasou pomocou vyriesena.
Offline
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 dělí f(m,n).
Offline
Stránky: 1