Партиције природних бројева

Дефиниција 1. Партиција природног броја је представљање тог броја у облику збира неколико природних бројева, при чему је распоред сабирака небитан и сам тај број представља једну партицију.

Лајбниц (Gottfried Wilhelm Leibniz) је у писму Бернулију (Jacob Bernoulli) 1674. први пут поставио питање о броју партиција {p(n)} природног броја {n}.

Примјер 1. Партиције броја 2 су 2 и 1+1 (2 партиције); броја 3 су 3, 2+1 и 1+1 (3 партиције); броја 4 су 4, 3+1, 2+2, 2+1+1, 1+1+1+1 (5 партиција); лако се провјери да има 7 партиција броја 5 и 11 партиција броја 6.

На основу претходног примјера могао би се извести погрешан закључак да је број партиција природног броја увијек прост. Међутим, број 7 има 15 партиција, а {15=3\cdot 5} није прост број. Још увијек није познат одговор на питање: „Да ли постоји бесконачно много природних бројева чији је број партиција прост?“

Више од пола вијека касније, 1740. године, Philippe Naudé jе послао писмо Ојлеру (Leonhard Paul Euler), у коме га је упитао да ли нешто зна о броју различитих начина на које се неки број може написати као сума међусобно различитих сабирака (питање је било споредно, у писму се распитивао о Ојлеровом недавном успјеху у сумирању реда {\sum_{k=1}^\infty \frac{1}{k^2}}). Ојлер му је послао одговор за пар седмица, правдајући се да касни(!) због ослабљеног вида. Овдје ћу да изложим један дио његовог писма, доказ сљедеће теореме.

Теорема 1. (Ојлер) Број начина на које се дати природан број може написати као сума међусобно различитих природних бројева једнак је броју начина на које се тај исти број може написати као сума непарних бројева.

Означимо број начина на које се природан број {n} може написати као сума међусобно различитих природних бројева са {R(n)} а број начина на које се природан број {n} може написати као сума непарних бројева са {N(n)}.

Примјер 2. За {n=5} имамо да је {5=4+1=} {3+2} и {5=3+1+1} {=1+1+1+1+1}; видимо да вриједи једнакост {R(5)=N(5)=3}. За {n=8} имамо да је {8=7+1=} {6+2=5+3=} {5+2+1=} {4+3+1} и {7+1=} {5+3=} {5+1+1+1=} {3+3+1+1=} {3+1+1+1+1+1=1+1+1+1+1+1+1+1}; видимо да и у овом случају вриједи једнакост {R(8)=N(8)=6}.

Да би доказали тврђење теореме, треба да покажемо да вриједи {R(n)=N(n)} за свако {n\in N}. Доказ ћемо провести у три корака.

ДОКАЗ:

Посматрајмо бесконачан производ бинома:

{P(x)=(1+x)\cdot(1+x^2)\cdot(1+x^3)\cdot(1+x^4)\cdot(1+x^5)\cdot\cdot\cdot=} {1+x^1+x^2+(x^3+x^{2+1})+(x^4+x^{3+1})+(x^5+x^{4+1}+x^{3+2})+\cdot\cdot\cdot=} {1+1\cdot x^1+1\cdot x^2+2\cdot x^3+2\cdot x^4+3\cdot x^4+\cdot\cdot\cdot}.

Јасно је да вриједи формула:

\displaystyle  P(x)=1+\sum_{n=1}^\infty R(n)\cdot x^n\ \ \ \ \ (1)

.

Прије него што пређемо на сљедећи корак, подсјетимо се формуле за суму геометријског реда:

\displaystyle  1+a+a^2+a^3+\cdot\cdot\cdot=\frac{1}{1-a}\ \ \ \ \ (2)

.

Посматрајмо сада бесконачан производ алгебарских разломака:

{Q(x)=\displaystyle\frac{1}{1-x}\cdot\frac{1}{1-x^3}\cdot\frac{1}{1-x^5}\cdot\cdot\cdot\stackrel{(2)}{=} (1+x+x^2+x^3+\cdot\cdot\cdot)\cdot} {(1+x^3+x^6+x^9+\cdot\cdot\cdot)\cdot (1+x^5+x^{10}+x^{15}+\cdot\cdot\cdot)\cdot\cdot\cdot=} {(1+x+x^{1+1}+x^{1+1+1}+\cdot\cdot\cdot)\cdot(1+x^3+x^{3+3}+x^{3+3+3}+\cdot\cdot\cdot)\cdot} {(1+x^5+x^{5+5}+x^{5+5+5}+\cdot\cdot\cdot)\cdot\cdot\cdot= 1+x^1+x^{1+1}+(x^{1+1+1}+x^3)+} {(x^{3+1}+x^{1+1+1+1})+(x^5+x^{3+1+1}+x^{1+1+1+1+1})+\cdot\cdot\cdot=} {1+1\cdot x^1+1\cdot x^2+2\cdot x^3+2\cdot x^4+3\cdot x^4+\cdot\cdot\cdot}.

Јасно је да вриједи формула:

\displaystyle  Q(x)=1+\sum_{n=1}^\infty N(n)\cdot x^n\ \ \ \ \ (3)

.

Ако покажемо да вриједи једнакост {P(x)=Q(x)}, показаћемо (на основу формула (1) и (3)) да вриједи и једнакост

\displaystyle \sum_{n=1}^\infty R(n)\cdot x^n=\sum_{n=1}^\infty N(n)\cdot x^n

из које слиједи тврђење теореме.

Покажимо сада да вриједи једнакост {P(x)=Q(x)}. Ако израз за {P(x)} посматрамо као алгебарски разломак (допишемо именилац 1), можемо да извршимо његово проширивање а након одређених алгебарских трансформација и скраћивање.

{P(x)=\displaystyle\frac{(1+x)\cdot \mathit{(1-x)}\cdot (1+x^2)\cdot \mathit{(1-x^2)}\cdot (1+x^3)\cdot \mathit{(1-x^3)}\cdot\cdot\cdot}{\mathit{(1-x)\cdot (1-x^2)\cdot (1-x^3)\cdot (1-x^4)\cdot (1-x^5)\cdot (1-x^6)}\cdot\cdot\cdot}=}
{\displaystyle\frac{(1-x^2)\cdot (1-x^4)\cdot (1-x^6)\cdot\cdot\cdot}{(1-x)\cdot (1-x^2)\cdot (1-x^3)\cdot (1-x^4)\cdot (1-x^5)\cdot (1-x^6)\cdot\cdot\cdot}=}
{\displaystyle\frac{1}{(1-x)\cdot (1-x^3)\cdot (1-x^5)\cdot\cdot\cdot}=Q(x)}

Вриједи једнакост {P(x)=Q(x)}, што је и требало доказати. \Box

Напомена 1. Чланак је написан у LaTeX -у, затим је конвертован у wordpress.com на начин који ћу описати у сљедећем чланку.

Advertisements

Оставите одговор

Попуните детаље испод или притисните на иконицу да бисте се пријавили:

WordPress.com лого

Коментаришет користећи свој WordPress.com налог. Одјавите се / Промени )

Слика на Твитеру

Коментаришет користећи свој Twitter налог. Одјавите се / Промени )

Фејсбукова фотографија

Коментаришет користећи свој Facebook налог. Одјавите се / Промени )

Google+ photo

Коментаришет користећи свој Google+ налог. Одјавите се / Промени )

Повезивање са %s