|
|
|
|
|
|
|
[1521] Lóczi Lajos | 2006-11-19 17:44:40 |
Oldjuk meg a valós számok halmazán a
trigonometrikus egyenletet.
|
|
[1520] Cckek | 2006-11-18 11:59:12 |
Még valami. Az vajon eldönthető-e, hogy egy k inverzióval rendelkező n-edrendű permutáció hányféle képpen bontható fel transzpozíciók szorzatára? Én ezzel probálkoztam, persze nem jutottam sehova.:)
|
|
[1519] Cckek | 2006-11-18 11:51:16 |
Nagyon érdekes okfejtés. Az nyílvánvaló, már csak az inverziók számolási módszeréből is, hogy a t1+t2+...+tn-1=k összeg összes lehetséges képzésének a száma adja meg az n-edrendű k inverzióval rendelkező permutációk számát, hiszen ha a permutáció alsó sorában 1 előtt t1, 1-nél nagyobb, 2 előtt t2, 2-nél nagyobb,.. (n-1) előtt tn-1, (n-1)-nél nagyobb elem van akkor a permutáció inverzióinak a száma t1+t2+...+tn-1. Az is látható, hogy 0t1(n-1), 0t2(n-2),...,0tn-11 Tehát, a problémát, kitűnően letárgyáltátok, itt valóban nem beszélhetünk zárt alakról, annyit még hozzátennék, hogy amennyiben Skn-el jelöljük a k inverzióval rendelkező n-edrendű permutációk számát úgy fennáll :
Attila is említett egy rekurziót. Az hogy néz ki?
|
Előzmény: [1518] nadorp, 2006-11-18 10:22:10 |
|
[1518] nadorp | 2006-11-18 10:22:10 |
Megpróbálom vázolni a gondolatmenetemet. Jelölje az n-edrendű k inverziót tartalmazó permutációk számát I(n,k) és legyen p(n,k) egy ilyen permutáció. Ekkor ha az n+1 elemet a permutáció végére tesszük, akkor egy p(n+1,k) permutációt kapunk. Ha az n+1-et eggyel balra tolva a n-dik helyre tesszük, akkor egy p(n+1,k+1) permutációt kapunk stb. ha az n+1 az első helyen van, akkor egy p(n+1,k+n) permutációt kapunk. Foglaljuk be ezt az alábbi táblázatba, ahol a k-dik oszlopban a p(n,k)-ból kapható permutációk találhatóak.
Tekintsük még a következő hasonló táblázatot
Nyilvánvaló, hogy I(n+1,k) úgy kapható meg, hogy ahol az első táblázatban p(n+1,k) van, összeadjuk a második táblázatban az ezeken a helyeken szerplő I(n,...) értékeket.Tehát
I(n+1,0)=I(n,0)
I(n+1,1)=I(n,0)+I(n,1)
I(n+1,2)=I(n,0)+I(n,1)+I(n,2) stb..
Ezek az összegek éppen balról jobbra haladva a "balról jobbra fel átlókon" levő elemek összege. Ha most fn(x) az I(n,k) sorozat (n fix) generátor függvénye, azaz
, ahol ak=I(n,k), akkor
|
Előzmény: [1516] jenei.attila, 2006-11-16 15:44:31 |
|
[1517] jenei.attila | 2006-11-16 15:50:44 |
Egyébként (mint azóta utána néztem), D.E. Knuth: A számítógépes programozás művészete c. könyv harmadik kötete (Rendezések és keresések) is részletesen foglalkozik a problémával. Ott egy érdekes rekurziót is megad. A könyvet nagyon ajánlom mindenkinek.
|
Előzmény: [1516] jenei.attila, 2006-11-16 15:44:31 |
|
|
|
|
[1513] jenei.attila | 2006-11-15 19:27:32 |
A feladat megtalálható Lovász László Kombinatorikai problémák és feladatok c. könyvében. Itt a megoldást az ún. inverzió vektorok használatával adják meg. Egy n-ed rendű p permutáció inverzió vektora egy n elemű t vektor (tömb), amelynek j-edik eleme azt adja meg, hogy a permutációban hány előző elem kisebb, mint a j-edik elem: tj=|1<=i<j:p(i)>p(j)|, vagyis rögzített j mellet a kisebb indexekkel képezhető inverziók számát. Világos, hogy 0<=tj<=j-1, és a t elemeinek összege éppen a p inverzióinak számát adja. Fordítva is igaz: egy feltételeknek megfelelő t vektor egyértelműen meghatározza a p permutációt (ez is egy érdekes kis feladat). Ezért a k=t1,+t2+...+tn egyenlet feltételnek megfelelő (0<=tj<=j-1) megoldásait kell összeszámolni, vagyis k hányféleképpen írható fel ilyen módon n db. szám összegeként. Ennek az ún. partíciós problémának a megoldását adja a Nadorp által felírt polinom k-ad fokú tagjának együtthatója.
Erre a megoldásra gondoltál?
|
Előzmény: [1511] Cckek, 2006-11-14 19:03:42 |
|
[1512] nadorp | 2006-11-15 17:03:41 |
Félek tőle, hogy erre nincs zárt formula. Ha tévedtem, akkor annál jobb. Az az erős sejtésem ( bár ez is kétséges, úgyhogy ne dobáljatok meg kővel), hogy ha a keresett számot I(n,k)-val jelöljük, akkor az
fn(x)=(1+x)(1+x+x2)...(1+x+...xn-1) polinomban xk együtthatója éppen I(n,k)
|
Előzmény: [1511] Cckek, 2006-11-14 19:03:42 |
|
[1511] Cckek | 2006-11-14 19:03:42 |
Jó, részemről befejezve felejtsük el:)) Itt van egy megint csak érdekes feladat:)) Hány n-edrendű permutáció inverzióinak a száma k???
|
|
[1510] jenei.attila | 2006-11-14 16:29:21 |
Egyáltalán nem akartalak megsérteni, szerintem nem is volt rá okod, hogy megsértődj. A véleményemet pedig hadd mondjam már el, én teljesen jószándékúan kérdeztem, hogy mi a feladatban az érdekesség, trükk. Most, hogy már megvilágítottad a feladat hátterét, valóban érdekesebbnek találom, bár még mindíg kicsit "megcsinált" ízű. Egyébként engedd meg, hogy azzal a feladattal foglalkozzak, amelyik nekem tetszik, a versengéssel kapcsolatban meg nem értem mire gondolsz.
|
Előzmény: [1509] Cckek, 2006-11-14 15:49:20 |
|
[1509] Cckek | 2006-11-14 15:49:20 |
Kedves Attila. Eddig mintha starpás és mesterkélt lett volna. hmm:) Amúgy ez csak egy feladat, kitűztem mert reméltem, hogy van akinek örömet okoz a megoldása. Ha neked nem, hát akkor ne foglalkozz vele, ez itt nem verseny, és remélem még csak versengés sem.
|
Előzmény: [1504] jenei.attila, 2006-11-14 11:32:30 |
|
|
[1507] jenei.attila | 2006-11-14 12:25:38 |
Lehet, hogy erre gondolt, de ez szerintem kb. ugyanaz mint a stieltjes integrál, csak nem nevezzük nevén. Egyébként gondolom Te már előttem felismerted az integrál közelítő összeget. Te nem Stieltjes integrálra gondoltál?
|
Előzmény: [1506] nadorp, 2006-11-14 12:19:34 |
|
[1506] nadorp | 2006-11-14 12:19:34 |
Szerintem Cckek arra gondol, hogy kár belekeverni a példába a Stieltjes-integrált, mert ha az eredeti szummában észrevesszük a nyilvánvaló összefüggést, akkor mezei Riemann közelítő összeget kapunk, és azonnal adódik a nálam az x=tg y helyettesítés után kapott integrál.
|
Előzmény: [1505] Sirpi, 2006-11-14 11:40:26 |
|
|
[1504] jenei.attila | 2006-11-14 11:32:30 |
Kedves Cckek!
Először is maradjunk annyiban, tényleg érdekes a feladatot, csak kicsit másra számítottam. Másrészt nem egészen értem, mit is nem ismertünk fel? Azt, hogy Riemann-Stieltjes integrál közelítő összeg, észrevettük. Nadorp pedig megoldotta az integrálást, vagyis a feladat ezzel megoldódott.
|
Előzmény: [1498] Cckek, 2006-11-13 18:16:57 |
|