[755] marcius8 | 2014-01-07 10:14:14 |
![](https://www.komal.hu/forum/kep/fenykep/6899/0_ZP0g.jpg) Köszönöm a hozzászólást. Igazából csak addig jutottam én is, hogy hogyan nézhet ki egy ilyen gráf, és arra jutottam, hogy egy ilyen gráf diszjunkt körökből áll. Tisztelettel: Bertalan Zoltán.
|
Előzmény: [753] aaaa, 2013-12-23 01:12:02 |
|
[754] aaaa | 2013-12-23 02:19:16 |
![](https://www.komal.hu/forum/kep/fenykep/default.jpg) Némi elírás, a megadott képlet minden gráfra számol, és l-et 3-től kell indítani.
Javítás páros gráfra
Párosra csak a páros tagokat kell összegezni, ezeket is csak 2-től kezdve, így a következőképpen módosulnak a dolgaink:
![T(l)=1+\frac{x^{l}}{2l}e^{x^{l}(2l)^{-1}}](keplet.cgi?k=A265470D36F1B5DB)
![G(x)=\prod_{i=2}^\infty \left(1+\frac{x^{2i}}{4i}e^{x^{2i}(4i)^{-1}}\right)](keplet.cgi?k=F0DD077AF1AB027C)
És G(x)-ben xn együtthatója adja meg a sorrendek számát n!-al osztva.
|
Előzmény: [753] aaaa, 2013-12-23 01:12:02 |
|
[753] aaaa | 2013-12-23 01:12:02 |
![](https://www.komal.hu/forum/kep/fenykep/default.jpg) Egy előzőhöz hasonló gondolatmenettel valahogy így kellene:
Most irányított gráfra csináljuk: Ha meg meg vannak különböztetve a csúcsok, akkor ugye ezeknek n! sorrendje van. Ezt ugye daraboljuk egy partíció szerint. Mit számolunk többször? Hát, ha ugyanazok a csúcsok más sorrendben, de ugyanabban a ciklikus permutációnak megfelelő sorrendben vannak, illetve ha ugynakkora méretű halmazaink vannak, csak más sorrendben. Most generátorfüggvényt csinálunk, -ra:
Először csak azt vesszük bele a játékba, hogy k darab ugyanakkora halmazt (k-1)! alkalommal számoltunk, vagyis a hatványsora valahogy így nézzen ki egy tényező:
![U(l)=1+\sum_{k=1}^\infty \frac{x^{lk}}{(k-1)!}](keplet.cgi?k=6D69F58BE02B942C)
Viszont ezeknek lk darab egymástól független, ugyanolyan gráfot eredményező sorrendje van, tehát:
![T(l)=1+\sum_{k=1}^\infty \frac{x^{lk}}{(k-1)!l^k}=1+\frac{x^l}{l}e^{x^{l}l^{-1}}](keplet.cgi?k=A1E5A637568CF592)
A keresett generátorfüggvény tehát úgy áll elő, hogy a
![g(l)=\prod_{l=2}^{\infty}1+\frac{x^l}{l}e^{x^{l}l^{-1}}](keplet.cgi?k=7BBB8AFBE976BA66)
Szorzat xn-hez tartozó együtthatóját szorozzuk n!-al, és elvileg készen kellene lennünk. Ha meg irányításfüggetlen, akkor ennek pontosan a fele jó sorrend, ekkor
![G(l)=\prod_{l=2}^{\infty}\left(1+\frac{x^l}{2l}e^{x^{l}(2l)^{-1}}\right)](keplet.cgi?k=2B54D10DBC3C97D7)
|
Előzmény: [752] aaaa, 2013-12-23 00:24:11 |
|
[752] aaaa | 2013-12-23 00:24:11 |
![](https://www.komal.hu/forum/kep/fenykep/default.jpg) Kb. 2 percet gondolkozva rajta a következőre jutottam: Mivel a gráf páros, minden kör 2k hosszú, ahol k 2, és ez elég is a párossághoz. Címkézetlen csúcsokon vagyunk, így lényegében n pont partíciónak a száma a kérdés, ahol minden egyes részhalmaz legalább 2 elemet tartalmaz. Ennek a generátorfüggvénye meg:
![g(x)=\prod_{i=2}^\infty\frac{1}{1-x^i}](keplet.cgi?k=168DB1948A56285B)
Aminek a hatványsorának xi-hez tartozó együtthatója épp a 2i-re a nem izomorf fák számát. Ennek első néhány tagja:
g(x) 1+x2+x3+2x4+2x5+4x6+4x7+7x8+8x9+12x10+14x11+21x12+24x13+34x14+41x15+55x16+66x17+88x18+105x19+137x20+O[x]21
Itt megtalálod a sorozat néhány következő tagját. Szerintem ez megadja az izomorfia erejéig a jó gráfok számát, csak ki kell fejteni. Azt nem hinném, hogy ennél sokkal explicitebb képlet létezik, mivel azt írja, hogy P(n+1)-P(n) sorozat ez lesz, ahol P(n) a partíciók száma. Kicsit fáradt vagyok már, szóval lehet, hogy valamit elnéztem.
|
Előzmény: [750] marcius8, 2013-12-20 10:04:05 |
|
[751] csábos | 2013-12-22 23:35:36 |
![](https://www.komal.hu/forum/kep/fenykep/default.jpg) Nem értem a kérdést. Adott a páros gráf? Akkor mik az élei? Ha nem adott, akkor adott két db n-elemű halmaz, és ezen hány olyan páros gráf van, amely diszjunkt körök uniója? Ha a gráf adott, meg kell-e őrizni a paritását?
|
Előzmény: [750] marcius8, 2013-12-20 10:04:05 |
|
[750] marcius8 | 2013-12-20 10:04:05 |
![](https://www.komal.hu/forum/kep/fenykep/6899/0_ZP0g.jpg) Tekintsünk egy páros gráfot, melynek "2n" csúcsa van. Hányféleképpen lehet ebbe a páros gráfba berajzolni az éleket, úgy hogy minden csúcs foka 2 legyen? Kicsit nehezebb kérdés: ezen lehetőségek között mennyi egymással nem izomorf gráf van? Ha valakinek van ötlete ezzel kapcsolatban, kérem írja le. Előre is köszönettel: Bertalan Zoltán.
|
|
[749] marcius8 | 2013-12-20 10:00:36 |
![](https://www.komal.hu/forum/kep/fenykep/6899/0_ZP0g.jpg) Tudjuk, hogy ha egy tórusz középkörének sugara "R", meridiánkörének sugara "r", ahol "r" kisebb "R" egyenlőtlenség teljesül (klasszikus úszógumi), akkor a tórusz felszíne 4*pi*pi*R*r és a tórusz térfogata 2*pi*pi*R*r*r. Azt is tudjuk, hogy a pozitív egész számok négyzetének reciprokösszege pi*pi/6. Vajon ez utóbbi állítást nem lehetséges bebizonyítani a tórusz felszínképletének vagy térfogatképletének felhasználásával, tekintettel arra, hogy a "pi*pi" mennyiség itt is és ott is megjelenik? Ha valakinek van ötlete, és megírja, nagyon megköszönöm. Tisztelettel: Bertalan Zoltán.
|
|
|
|
|
[745] Cogito | 2013-12-09 00:40:38 |
![](https://www.komal.hu/forum/kep/fenykep/default.jpg) Egyetértek, a "2. megoldásbeli" azonosság önmagában tényleg bosszantóan kevés.
Az interneten itt olvashatjuk a The Interesting Around Technical Analysis Three Variable Inequalities - Nguyen Duy Tung, Zhou Yuan Zhe.pdf-et, melynek 10-11. oldalán közlik a feladat egy - még mindig nem teljes és sajnos (sajtó)hibás - megoldását. E hibás helyeket negatívba fordítottam. Ide írom a javításukat:
A fekete hátterű részeknél: az egyenlőtlenség helyesen a b c, a 2-esek helyére pedig 1-esek írandók.
Kiegészítésül egy azonosság, amit itt érdemes ismerni: a3b + b3c + c3a - (ab3 + bc3 + ca3) = (a + b + c)(a - c)(c - b)(b - a).
|
![](https://www.komal.hu/forum/kep/abra/93/5f/cd/57b177d2f9c6cb03a8a5ae462a-2423.gif) |
Előzmény: [741] w, 2013-12-02 20:58:17 |
|
|
|
|
[741] w | 2013-12-02 20:58:17 |
![](https://www.komal.hu/forum/kep/fenykep/6841/2_RZgu.jpg) Igen, ez így van, de azzal egyetérthetsz, hogy a "2. megoldásbeli" azonosságot egymagában kicsit szemetebb dolog odavágni. :-) A két megoldás azonban olyan szempontból különbözik egymástól, hogy teljesen eltérő módon lehet rájönni - az 1. megoldás kitalálhatóbb, ha az említett egyenlőtlenségből indulunk ki, a második pedig az egyenlőség-esetből vezeti le a kívánt állítást (ami egyébként önmagában nehéz feladat). A megoldás kialakulásáról ebben a beszélgetésben olvashatunk.
|
Előzmény: [740] Cogito, 2013-12-02 20:10:08 |
|
[740] Cogito | 2013-12-02 20:10:08 |
![](https://www.komal.hu/forum/kep/fenykep/default.jpg) Nézzük, hogyan jutunk 1-ről a 2-re:
Az "1. megoldás"-ban szereplő triviális egyenlőtlenséggel ekvivalens:
ahová x, y, z értékeit behelyettesítve:
adódik, ahol a bal oldalon álló kifejezés éppen A. Az első "megoldás" tehát ekvivalens a másodikkal! Ezért - valójában - egyetlen "megoldást" mutattál be. Azért használom az idézőjeleket, mert hiányérzetem van. Nem mutattad meg, hogy milyen út, milyen meggondolások vezettek az x-re, y-ra és z-re adott helyettesítésekhez.
|
Előzmény: [739] w, 2013-11-29 22:31:58 |
|
[739] w | 2013-11-29 22:31:58 |
![](https://www.komal.hu/forum/kep/fenykep/6841/2_RZgu.jpg) Állítás: .
1. megoldás. Hasonlítsuk össze egy triviális egyenlőtlenséggel, azaz hogy (x+y+z)2 3(xy+yz+zx) tetszőleges valós x,y,z-re. Ebbe x=a2+bc-ab, y=b2+ca-bc, z=c2+ab-ca értékeket helyettesítve pedig éppen a bizonyítandó adódik!
2. megoldás. Vegyük észre, hogy
![A=\left(a^2+b^2+c^2\right)^2-3\left(a^3b+b^3c+c^3a\right)=](keplet.cgi?k=C4BEFAE239F24466)
![=\frac{1}{2}\left(\left( a^{2}-2ab+bc-c^{2}+ca\right)^2+\left(b^{2}-2bc+ca-a^{2}+ab\right)^2+\left( c^{2}-2ca+ab-b^{2}+bc\right)^2\right)\ge0.](keplet.cgi?k=B45F790A2265982D)
Mit szóltok?
|
Előzmény: [733] w, 2013-10-25 23:07:23 |
|
|
[737] HoA | 2013-11-18 15:26:19 |
![](https://www.komal.hu/forum/kep/fenykep/1191/2_VfJj.jpg) A követelmény úgy is megfogalmazható, hogy minden kiválasztott négyzetnek páros, minden nem kiválasztott négyzetnek páratlan számú kiválasztott szomszédja legyen.
|
Előzmény: [734] kurthyg, 2013-11-17 00:44:52 |
|
[736] kurthyg | 2013-11-17 11:04:40 |
![](https://www.komal.hu/forum/kep/fenykep/default.jpg) A kiválasztandó négyzetek sorozata. Számozzuk be a négyzeteket: a bal fölső sarok az 1-es a jobb alsó nxn: tehát balról jobbra és föntről lefelé növekszenek a számok.
Ekkor az út (ha eredetileg minden négyzet fehér volt): 1 3 5 7 9
Ezeket sorban kiválasztva minden négyzet fekete lesz.
|
Előzmény: [735] Sinobi, 2013-11-17 10:48:31 |
|
|
[734] kurthyg | 2013-11-17 00:44:52 |
![](https://www.komal.hu/forum/kep/fenykep/default.jpg) A következő feladatot szeretném megosztani (persze, lehet, hogy már volt, kb 15 éve olvastam KöMaL-t utoljára, még gimnáziumban).
Adott egy nxn-es négyzetrács csupa fehér négyzettel. Válasszuk ki valamelyik négyzetet, ekkor a kiválasztott négyzet, a tőle jobbra és balra, alatta és fölötte lévők feketévé változnak. És minden egyes későbbi kiválasztás ellentétes színűre változtatja a kiválasztott négyzetet és a szomszédait.
Feladat olyan utat találni, amelynek végén az összes négyzet fekete lesz. Hogyan adható meg általános megoldás?
(Pl.: 1x1-es nél triviális. 2x2-esnél minden négyzetet ki kell választani. 3x3-asnál a sarkokat és a középső négyzetet.)
A probléma általánosítása: az nxn-es négyzetrács néhány négyzete fehér, néhány négyzete fekete. Milyen út vezet csupa fekete négyzethez? Hogyan kereshető meg a megoldás? Van-e mindig megoldás?
|
|
[733] w | 2013-10-25 23:07:23 |
![](https://www.komal.hu/forum/kep/fenykep/6841/2_RZgu.jpg) A következő egy rendkívül érdekes, a pozitív valós számokra bizonyítandó egyenlőtlenség (négyzetreemelve a valósokra is érvényes marad!). Annál inkább érdekes, hogy milyen egyszerű alakú, negyedfokú egyenlőtlenség.
![a^2+b^2+c^2\ge\sqrt{3(a^3b+b^3c+c^3a)}](keplet.cgi?k=6479F8136E04B158)
Különösen szokatlan az egyenlőség-esete, amit mindenképpen érdemes előre megfigyelni.
(A feladat egyébként valamennyire ismert, egy idő múlva majd elárulom, hol találtam.)
|
|
|
[731] Sinobi | 2013-10-20 01:36:18 |
![](https://www.komal.hu/forum/kep/fenykep/6798/4_NxWzmhKo.jpg) Bocsánat, nem ilyen alakra kell a végén hozni. Ezt még tovább kell alakítanod, hogy l:=-14/9*m, s akkor azt kapod, hogy:
![\lim_{l\to\infty} \bigg( 1 + \frac{1}{l} \bigg) ^{-14/9*l}= \bigg( \lim_{l\to\infty} \bigg( 1 + \frac{1}{l} \bigg) ^{l} \bigg) ^{-14/9}](keplet.cgi?k=A3876B281283305A)
Amiben még mindig ott van n a kitevőben. De azzal nem tudsz semmit se kezdeni. Igazából már Euler se tudott vele semmit kezdeni, csak feltűnt neki, hogy az olyan kifejezéseknek, melyekben n a kitevőben van, a limesze gyakran -lel és algebrai műveletekkel megadható, ezért a -et elnevezte magáról e-nek. Azóta általában az a feladat, hogy a kapott sorozatokat valahogy leredukáljuk erre a kifejezésre.
|
Előzmény: [730] Sinobi, 2013-10-20 01:12:11 |
|