Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Fórum: Kombinatorika

Szeretnél hozzászólni? Jelentkezz be.
[9] bily712011-09-22 08:37:49

Az ábráról lemaradt az 1+6+6 partíció.

Előzmény: [8] bily71, 2011-09-22 00:05:56
[8] bily712011-09-22 00:05:56

Az út, ahogy idáig jutottam, inkább útvesztő, ezért csak a kész bizonyítást közlöm.

Bizonyítás: Az ábrán egy cimkézett irányított fa gráfot látunk. A fa gyökere az x-szel cimkézett csúcs, x értéke változó. A fa konkrétan n=13 partícióit reprezentálja a következő módon: bármely levéltől a gyökérig jutva egy partíciót kapunk, ha összeadjuk az érintett csúcsok cimkéin lévő számokat, az utolsó szám az x, melynek értéke szükség szerint változik. Ha letépünk egy levelet, újabb partíciót kapunk.

Jelölje |v| a v csúcs cimkéjének értékét. Az u csúcsból v csúcsba csak akkor vezet él, ha |u|\le|v|, így minden partíciót megkapunk és pontosan egyszer, pl.: 1+3+4+x=13, ahol értelemszerűen x=13-(1+3+4). Ez azt jelenti, hogy pontosan annyi partíció létezik, ahány csúcsa van a gráfnak.

Számunkra az x előtti szám az érdekes, jelöljük ezt i-vel. Ha i=1, akkor előtte csak 1-esek állhatnak, ilyen partícióból n-1 van, hiszen ezen az ágon ennyi csúcs van, ez pontosan annyi, ahány rácspont van az x1 tengelyen, melynek kordinátájára teljesül, hogy 0\lex1\len-2i=n-2

Ha i=2, akkor az ezen az ágon lévő csúcsok háromszögbe rendezhetők, ahol minden új sorban 2-vel kevesebb csúcs lesz, az elsőben n-3, vagyis pontosan annyi, ahány rácspontra teljesül a síkban, hogy 0\lex1,x2 és 1x1+2x2\len-2i=n-4.

Az i=3 esetben [n/3] háromszöget kapunk, mindegyikben, az i=2 esethez hasonlóan, minden sor 2-vel kevesebb csúcsot tartalmaz a felette lévőnél és minden háromszög első sora 3-mal kevesebb csúcsot az előtte lévő háromszög első soránál. A háromszögek "hasonlók", így egy tetraéderbe rendezhetők, mely pontosan annyi csúcsot tartalmaz, ahány rácspontra teljesül a térben, hogy 0\lex1,x2,x3 és 1x1+2x2+3x3\len-2i=n-6.

n=4 esetén is háromszögeket kapunk, ezekből tetraédereket, ezekből 4D-s testet, és így tovább.

Tehát azt kaptuk, hogy p(n)=1+\sum_{i=1}^{\left[\frac{n}2\right]}|A_i|, ahol A_i:=\{(x_1,x_2,...,x_i)\in{N^{i}}|\sum_{j=1}^{i}(jx_j)\le{n-2i}\}, ezzel beláttuk a tétel helyességét.

Megjegyzés: A szumma előtt álló 1-es a p1(n) számát jelöli, ahol i=0, ez az x cimkéjű csúcsnak felel meg, ekkor x=n, annyi mint a (0x0) a nulla dimenziójú tér rácspontjainak száma, ilyen pedig egy van. Azért vettem ki az 1-est a szummából, mert ha i nullától megy, akkor elromlik a képlet.

Előzmény: [7] bily71, 2011-09-20 07:04:17
[7] bily712011-09-20 07:04:17

Nem is én lennék, ha nem írtam volna el. Mégegyszer, de most már helyesen:

p(n)=1+\sum_{i=1}^{\left[\frac{n}2\right]}|A_i|,

ahol A_i:=\{(x_1,x_2,...,x_i)\in{N^{i}}|\sum_{j=1}^{i}(jx_j)\le{n}-2i\}, (N={0,1,2,...}).

Előzmény: [6] bily71, 2011-09-19 21:09:51
[6] bily712011-09-19 21:09:51

Addig alakítgattam, míg a következőt találtam:

Tétel:

p(n)=1+\sum_{i=1}^{\left[\frac{n}2\right]}|A_i|,

ahol A_i:=\{(x_1,x_2,...,x_i)\in{N^{i}}| \sum_{j=1}^{i}(jx_j)\le{n}-(2i-1)\}, (N={0,1,2,...}), vagyis a partíciók száma megegyezik az előbbi feltételeknek eleget tevő rácspontok számával.

Előzmény: [5] bily71, 2011-07-25 09:34:37
[5] bily712011-07-25 09:34:37

Elnézést, az utolsó képletnél a másolgatás után elfelejtettem kijavítani a felső indexeket,

hogy kiférjen egy sorba, a felső indexekbe és mindenfelé szummákat tettem,

helyesen:

p_k(n)=\sum_{i=1}^{\left[\frac{n}{k}\right]}\sum_{j_1=0}^{\left[\frac{n-ki}{k-1}\right]}\sum_{j_2=0}^{\left[\frac{n-ki-(k-1)j_1}{k-2}\right]}...\sum_{j_{k-3}=0}^{\left[\frac{n-ki-\sum_{\ell=1}^{k-4}(k-\ell)j_{k-\ell}}{3}\right]}\left[\frac{n-ki-\sum_{\ell=1}^{k-3}(k-\ell)j_{k-\ell}+2}{2}\right]
Előzmény: [4] bily71, 2011-07-24 22:18:00
[4] bily712011-07-24 22:18:00

Az előző hozzászólásokban képletet kerestem pk(n)-re, (ha ez megvan, akkor megvan p(n)-re is) csak eléggé naívan fogtam hozzá, miért ne lehetne az első k-2 szám k-2-féle? A következő rekurziót találtam, amire azután többek között a wikipédiában is ráleltem, ezért nem szükséges leírnom a bizonyítást, az összefüggés közismert.

p_k(n)=p_1(n-k)+p_2(n-k)+...+p_k(n-k)=\sum_{i=1}^{k}p_i(n-k)

Ezek szerint:

p1(n)=p1(n-1)=...=p1(n-n)=1.

p_2(n)=\sum_{i=1 }^{\left[\frac{n}2\right]}p_1(n-2i)=\left[\frac{n}2\right].

p_3(n)=\sum_{i=1}^{\left[\frac{n}3\right]}\big(p_1(n-3i)+p_2(n-3i)\big)=\sum_{i=1}^{\left[\frac{n}3\right]}\left(1+\left[\frac{n-3i}2\right]\right)=\sum_{i=1}^{\left[\frac{n}3\right]}\left[\frac{n-3i+2}2\right].

p_4(n)=\sum_{i=1}^{\left[\frac{n}4\right]}\big(p_1(n-4i)+p_2(n-4i)+p_3(n-4i)\big)=\sum_{i=1}^{\left[\frac{n}4\right]}\big(p_1(n-4i)+p_2(n-4i)\big)+ \sum_{i=1}^{\left[\frac{n}4\right]}p_3(n-4i)=

=\sum_{i=1}^{\left[\frac{n}4\right]}\left(1+\left[\frac{n-4i}2\right]\right)+\sum_{i=1}^{\left[\frac{n}4\right]}\sum_{j=1}^{\left[\frac{n-4i}3\right]}\left[\frac{n-4i-3j+2}2\right]=\sum_{i=1}^{\left[\frac{n}4\right]}\sum_{j=0}^{\left[\frac{n-4i}3\right]}\left[\frac{n-4i-3j+2}2\right].

Általánosan:

p_k(n)=\sum_{i=1}^{\left[\frac{n}k\right]}\sum_{j_1=0}^{\left[\frac{n-ki}{k-1}\right]}\sum_{j_2=0}^{\left[\frac{n-ki}{k-2}\right]}...\sum_{j_{k-3}=0}^{\left[\frac{n-ki}{3}\right]}\left[\frac{n-ki-(k-1)j_1-(k-2)j_2-...-3j_{k-3}+2}2\right]

A fenti összefüggés teljes indukcióval bizonyítható. Látszólag nem tudunk mit kezdeni ezzel a "szörnyűséggel", de csak látszólag. Ne feletsük el, hogy a szummák kibonthatók, mint a zárójelek, a tagok összevonásával, így olyan (explicit) képletet kapunk, mely csak n-től és k-tól függ.

[3] bily712011-07-17 07:16:25

Nem, mégsem jó, így nem kapjuk meg az összes partíciót, ezért ez csak egy alsó becslés. Ha valahogy rendezni tudom a kimaradt eseteket, akkor megvan a képlet.

Előzmény: [2] bily71, 2011-07-16 15:34:05
[2] bily712011-07-16 15:34:05

Az utolsó képlet javítva:

p(n)=\sum_{k=3}^{n}\sum_{b=1}^{k-2}\sum_{a=1}^{\infty}\left[[\frac{n-(k-2)-a(3+b)}{2}]\right]+\left[\frac{n}2\right]\left[\frac{n+1}2\right]+1

Az lenne a kérdésem, hogy ismert-e a fenti formula. Azt tanultuk és mindenhol azt olvasom, hogy nincs képlet a partíciók számát illetően, nos, itt van egy. Mi a véleményetek?

Előzmény: [1] bily71, 2011-07-15 22:58:49
[1] bily712011-07-15 22:58:49

Üdv mindenkinek!

Nem találtam ilyen jellegű témát, ezért nyitottam újat, ha mégis felesleges volt, megkérem a moderátorokat, hogy a hozzászólásomat helyezzék át a megfelelő helyre.

Jelölje pk(n) az n\inN szám k részre való partícióinak számát (3\lek)! Ekkor igaz a következő állítás:

p_k(n)=\sum_{b=1}^{k-2}\sum_{a=1}^{\infty}\left[[\frac{n-(k-2)-a(3+b)}{2}]\right]+\left[\frac{n-(k-2)}2\right],

ahol [[x]]:=[x] (egészrész), ha x\ge0, egyébként [[x]]:=0.

Bizonyítás: A partíciókat a következőképp soroljuk fel: ha m1+m2+...+mk=n egy partíció, akkor teljesüljön a következő: m1\lem2\le...\lemk, azután rendezzük táblázatba úgy, hogy egy oszlopba kerüljenek azok a partíciók, ahol az első k-2 helyen csak 1-esek és a+1-esek állnak és ha ezen számok között ugyanannyi 1-es és a+1-es van, akkor kerüljenek egy cellába, így minden partíciót megkapunk, pontosan egyszer. Hogy érthetőbb legyen, lássunk egy konkrét példát:

Legyen n=15, k=5!

0 1 2 3
1 \matrix{1+1+1+1+11\cr1+1+1+2+10\cr1+1+1+3+9\cr1+1+1+4+8\cr1+1+1+5+7\cr1+1+1+6+6} \matrix{(1+1+2+1+10)\cr1+1+2+2+9\cr1+1+2+3+8\cr1+1+2+4+7\cr1+1+2+5+6} \matrix{(1+1+3+1+9)\cr(1+1+3+2+8)\cr1+1+3+3+7\cr1+1+3+4+6\cr1+1+3+5+5} \matrix{(1+1+4+1+8)\cr(1+1+4+2+7)\cr(1+1+4+3+6)\cr1+1+4+4+5}
2 \matrix{(1+2+2+1+9)\cr1+2+2+2+8\cr1+2+2+3+7\cr1+2+2+4+6\cr1+2+2+5+5} \matrix{(1+3+3+1+7)\cr(1+3+3+2+6)\cr1+3+3+3+5\cr1+3+3+4+4}  
3 \matrix{(2+2+2+1+8)\cr2+2+2+2+7\cr2+2+2+3+6\cr2+2+2+4+5} \matrix{(3+3+3+1+5)\cr(3+3+3+2+4)\cr3+3+3+3+3}  

A 0-adik oszlopban felsorolt partíciók száma pontosan \left[\frac{n-(k-2)}2\right], hiszen az első k-2 helyen álló számok nem változnak, elhagyva azokat az utolsó két szám összegének két tagú partícióit kapjuk, ezek száma pedig: \forall m\in {N}:p_2(m)=\left[\frac{m}2\right], itt m=n-(k-2).

Az a-adik oszlop b-edik sorában lévő cellában felsorolt partíciók száma: \left[\frac{n-(k-2)-a-ab}2\right]-a=\left[\frac{n-(k-2)-a(3+b)}2\right], ugyanis, ha a zárójelben lévő partíciókat is beírjuk, akkor egy cellában a partíciók száma ugyannyi lesz, mint az utolsó két szám összegének két tagú partícióinak száma, kivonva ebből az a számot, megkapjuk a cellában ténylegesen lévő partíciók számát.

A 0-adik oszlopban csak az első sorba kerülnek partíciók, a többi oszlop legfeljebb k-2 sorból áll, vagyis 0\leb\lek-2.

Írjuk át az előző táblázatot úgy, hogy az a-adik oszlop b-edik cellájába A_{a,b}=\left[\frac{n-(k-2)-a(3+b)}2\right]-t írunk, így ahol Aa,b>0, ott a cellába tulajdonképp az abban felsorolt partíciók számát írjuk be, ahol Aa,b\le0, ott nincs partíció.

Összegezve azokat a cellákat, ahol Aa,b>0, a fenti képletet kapjuk, ami állításunkat igazolja.

A fenti képletből:

p(n)=\sum_{k=3}^{n}\left(\sum_{b=1}^{k-2}\sum_{a=1}^{\infty}\left[[\frac{n-(k-2)-a(3+b)}{2}]\right]+\left[\frac{n-(k-2)}2\right]\right)+p_2(n)+p_1(n)=

=\sum_{k=3}^{n}\sum_{b=1}^{k-2}\sum_{a=1}^{\infty}\left[[\frac{n-(k-2)-a(3+b)}{2}]\right]+\sum_{k=3}^{n}\left[\frac{n-(k-2)}2\right]+\left[\frac{n}2\right]+1=

=p(n)=\sum_{k=3}^{n}\sum_{b=1}^{k-2}\sum_{a=1}^{\infty}\left[[\frac{n-(k-2)-a(3+b)}{2}]\right]+\sum_{k=2}^{n}\left[\frac{n-(k-2)}2\right]+1.

A képlet egyszerűsíthető: \sum_{k=2}^{n}\left[\frac{n-(k-2)}2\right]=\left[\frac{n}2\right]+\left[\frac{n+1}2\right]+...+\left[\frac{n-(n-2)}2\right], ebből, felhasználva az \forall m\in{N}:\left[\frac{m-1}2\right]+\left[\frac{m}2\right]=m-1 összefüggést, 2|n esetén \sum_{k=2}^{n}\left[\frac{n-(k-2)}2\right]=\sum_{i=0}^{\frac{n-2}2}2i+1=\left(\frac{n}2\right)^2=\left[\frac{n}2\right]\left[\frac{n+1}2\right], 2£n esetén \sum_{k=2}^{n}\left[\frac{n-(k-2)}2\right]=\sum_{i=0}^{\frac{n-1}2}2i=\left[\frac{n}2\right]^2+\left[\frac{n}2\right]=\left[\frac{n}2\right]\left(\left[\frac{n}2\right]+1\right)=\left[\frac{n}2\right]\left[\frac{n+2}2\right]=\left[\frac{n}2\right]\left[\frac{n+1}2\right].

Tehát

(n)=\sum_{k=3}^{n}\sum_{b=1}^{k-2}\sum_{a=1}^{\infty}\left[[\frac{n-(k-2)-a(3+b)}{2}]\right]+\left[\frac{n}2\right]\left[\frac{n+1}2\right]+1.

A képlet tovább is egyszerűsíthető további összevonásokkal, vagy például megnézzük meddig mehet az a, így kiküszöbölhetjük az [[x]] függvényt, de ahhoz már fáradt vagyok.