Fórum: Kombinatorika

Szeretnél hozzászólni? Jelentkezz be.

[9] bily71	2011-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] bily71	2011-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 x₁ tengelyen, melynek kordinátájára teljesül, hogy 0 $\le$ x₁ $\le$ n-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 $\le$ x₁,x₂ és 1x₁+2x₂ $\le$ n-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 $\le$ x₁,x₂,x₃ és 1x₁+2x₂+3x₃ $\le$ n-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 p₁(n) számát jelöli, ahol i=0, ez az x cimkéjű csúcsnak felel meg, ekkor x=n, annyi mint a (0x₀) 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] bily71

2011-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] bily71

2011-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] bily71

2011-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] bily71

2011-07-24 22:18:00

Az előző hozzászólásokban képletet kerestem p_k(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:

p₁(n)=p₁(n-1)=...=p₁(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] bily71	2011-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] bily71

2011-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] bily71

2011-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 p_k(n) az n $\in$ N szám k részre való partícióinak számát (3 $\le$ k)! 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 $\ge$ 0, egyébként [[x]]:=0.

Bizonyítás: A partíciókat a következőképp soroljuk fel: ha m₁+m₂+...+m_k=n egy partíció, akkor teljesüljön a következő: m₁ $\le$ m₂ $\le$ ... $\le$ m_k, 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 $\le$ b $\le$ k-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 A_a,b>0, ott a cellába tulajdonképp az abban felsorolt partíciók számát írjuk be, ahol A_a,b $\le$ 0, ott nincs partíció.

Összegezve azokat a cellákat, ahol A_a,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.

Már regisztráltál?
Új vendég vagy?