\documentclass[a4paper,11pt]{article}
\usepackage{graphics,graphicx}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage[polish]{babel}
\pagestyle{headings}
\usepackage[polish]{babel}
\usepackage{indentfirst}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[usenames]{color}
\usepackage{xcolor}
\usepackage{tikz}
\usepackage[left=1.5cm,top=1.5cm,right=1.5cm,bottom=1.5cm]{geometry}
\usepackage[normalem]{ulem}
\usetikzlibrary{arrows,shapes,fit,decorations.pathmorphing}

\newcommand{\myskip}{\vskip 0.4cm \noindent}

\newcommand{\calL}{{\mathcal L}}
\newcommand{\calM}{{\mathcal M}}
\newcommand{\calN}{{\mathcal N}}
\newcommand{\calO}{{\mathcal O}}
\newcommand{\calP}{{\mathcal P}}
\newcommand{\calQ}{{\mathcal Q}}
\newcommand{\calR}{{\mathcal R}}
\newcommand{\calS}{{\mathcal S}}
\newcommand{\calT}{{\mathcal T}}
\newcommand{\calU}{{\mathcal U}}
\newcommand{\calV}{{\mathcal V}}
\newcommand{\calW}{{\mathcal W}}
\newcommand{\calX}{{\mathcal X}}
\newcommand{\calY}{{\mathcal Y}}
\newcommand{\Z}{{\mathcal Z}}

\newcommand{\pp}{\widetilde{p}}
\newcommand{\eqn}[1]{\stackrel{#1}{=}}

\newtheorem*{fakt}{Fakt}
\newtheorem{lem}{Lemat}
\newtheorem{obs}{Obserwacja}
\newtheorem{tez}{Teza}
\newtheorem{tw}{Twierdzenie}
\newtheorem{stw}{Stwierdzenie}
\newtheorem{wnio}{Wniosek}
\tikzstyle{circ_node} = [shape = circle, fill = black, inner sep = 0pt, minimum
size = 2mm]

\date{}
\definecolor{MyDarkBlue}{rgb}{0.1,0,0.95}

\title{\bf Liczenie podziałów liczby: algorytm Eulera}
\author{Wojciech Rytter}

\begin{document}
\maketitle
\noindent Podziały liczb są bardzo skomplikowanymi obiektami kombinatorycznymi,
przedstawimy dwa algorytmy liczenia takich oblektów.
Pierwszy prosty algorytm będzie działał w czasie $O(n^2)$ i pamięci $O(n^2)$, natomiast drugi,
pochodzący od Eulera i
oparty na tzw. liczbach {\em pentagonalnych}, w czasie $O(n\sqrt{n})$ i pamięci $O(n)$.
\myskip
\noindent
Podział $\pi=(\lambda_1,\lambda_2,\ldots \lambda_r)$ to przedstawienie  liczby $n=\lambda_1+\lambda_2+\ldots \lambda_r$ w postaci
$$n=\lambda_1+\lambda_2+\ldots \lambda_r,\
\mbox{gdzie}  \ \lambda_1\ge \lambda_2\ge \ldots \lambda_r>0$$
\myskip
Wszystkie podziały liczby $n$, w porządku antyleksykograficznym, można wygenerować iteracyjnie następująco:

szukamy pierwszego $\lambda_i\ge 2$ od prawej strony, zastępujemy $\lambda_i$ przez $\lambda_i-1$, a pozostałe części
na prawo dajemy tak, aby sufiks na prawo od $\lambda_i$ był jak największy.
Na przykład podziały $n=5$ w porządku antyleksykograficznym to:
$$5,\ \ \ \  4+1,\ \ \ \  3+2,\ \ \ \  3+1+1,\ \ \ \  2+2+1,\ \ \ \  2+1+1+1,\ \ \ \  1+1+1+1+1.$$
Oznaczmy przez $p(n)$ liczbę podziałów liczby $n$, mamy:

\begin{center}
      \begin{tabular}{r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r}
        $n:$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7&8&9&10&11&12&13&14&15&16 \\ \hline
        %$w[i]$ & & $c$ & $a$ & $a$ & $b$ & $b$ & $c$ & $a$ & $b$ & $b$ & $c$ & $a$ & $a$ & $a$ \\\hline
        $p(n):$ & 1 & 1 & 2 & 3& 5 &7 & 11 & 15 & 22&30&42&56& 77&101&135 & 176&231
      \end{tabular}
    \end{center}

    \noindent Dla $n<0$ przyjmijmy, czysto formalnie, że $p(n)=0$, natomiast $p(0)=1$.
    \myskip
 Oznaczmy przez $p(n,k)$ liczbę podziałów liczby $n$ na $k$ częsci (niezerowych).
 Algorytm o czasie kwadratowym liczenia $p(n)$ polega na policzeniu ( kwadratowej  liczby )  wartości $p(n,k)$ na podstawie rekurencji:
 $$p(n,k)=0\ \mbox{dla}\ k<n \ \mbox{lub}\ k\le 0.$$
 $$p(n,k)\; =\; p(n-1,k-1)+p(n-k,k)$$
 Rekurencja wynika stąd, że mamy dwa przypadki:
 \begin{description}
 \item ($\lambda_k=1$) Wtedy mamy $p(n-1,k-1)$ podziałów pomijając $\lambda_k$;
 \item ($\lambda_k>1$)  Wtedy możemy odjąć jeden od każdego $\lambda_i$ otrzymując podział
 liczby $n-k$ na $k$ części.
 \end{description}
 \myskip
 W celu szybszego policzenia $p(n)$ rozważymy podziały na różne części, tzn.
 $$\lambda_1>\lambda_2>\ldots \lambda_1.$$
 Niech $\pp(n)$ będzie liczbą takich podziałów.  Przez $p_{even},\pp_{even}, p_{odd},\pp_{odd}$ oznaczmy liczbę podziałów
 na parzystą/nieparzystą liczbę części (o różnych rozmiarach w przypadku $ \pp$).
 \myskip
  Na przykład $\pp(15)=27,\pp_{odd}(15)=14, \pp_{even}(15)=13$, patrz Rysunek~\ref{bijekcja_euler3}.

  \noindent Zauważmy, że liczby $\pp(n)$ są przeważnie znacznie mniejsze od liczb $p(n)$ (chociaż na początku niewiele się różnią).
  \myskip
 Możemy rónież zdefiniować $\pp(n,k)$ - liczbę podziałów $n$ na różne części.
 Na przykład $\pp(50,7)=522$, co Euler policzył prawie 300 lat temu
 bez komputera (ani kalkulatora) tę konkretną wartość odpwiadając
 na pytanie matematyka  Ph. Naude.
 \myskip
 \noindent  {\bf Dygresja.} $p_{odd}(n)=\pp(n)$. 
\myskip
Kluczową wartością jest zdefiniowana poniżej funkcja:
$$\Delta(k)\; =\; \pp_{odd}(k)-\pp_{even}(k)$$
Funkcje $p(n),\; \pp(n)$ są bardzo skomplikowane, natomiast jest zadziwiające, że $\Delta$ jest 
bardzo prosta.
Początkowe wartości to:

\begin{center}
      \begin{tabular}{r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r}
        $k:$  & 1 & 2 & 3 & 4 & 5 & 6 & 7&8&9&10&11&12&13&14&15&16&17&18&19&20&21&22 \\ \hline
        %$w[i]$ & & $c$ & $a$ & $a$ & $b$ & $b$ & $c$ & $a$ & $b$ & $b$ & $c$ & $a$ & $a$ & $a$ \\\hline
        $\Delta(k):$ & 1 & 1 & 0 & 0& -1 &0 & -1 & 0 & 0&0&0&1&0&0&1& 0&0&0&0&0&0&-1
      \end{tabular}
    \end{center}

 \noindent Leonard Euler odkrył dwie istotne (dla liczenia $p(n)$) własności funkcji $\Delta$:
 \begin{description}
 \item{\bf Własność 1:} \mbox{ \ }\\
  $p(n)$ spełnia rekurencję:
 \begin{equation}\label{equation1}
 p(n)\;=\; \sum_{k= 1}^n\; \Delta(k)\cdot p(n-k)
 \end{equation}
 \item{\bf Własność 2:}  \mbox{ \ }\\
 jak widać z początkowych wartości $\Delta(k)$ jest ciągiem bardzo {\em rzadkim} (prawie same zera).\\
 Jest on obliczalalny łatwo za pomocą tzw. liczb pentagonalnch, wartości ciągu to zera, +1 lub -1.

 Z tego, że ciąg $\Delta(n)$ jest bardzo rzadki wynika, że dla policzenia $p(n)$ tylko
 $O(\sqrt{n})$ wartości $k$ jest niezerowych.
 
 \noindent Zatem $p(n)$ liczymy w czasie $O(\sqrt{n})$ znając
 $p(n-1),p(n-2),\ldots p(0)$. W sumie mamy algorytm działający w czasie $O(n\sqrt{n})$ i pamięci $O(n)$,
 o ile potrafimy łątwo wylistować niezerowe wartości $\Delta(k)$.

 Leonard Euler najpierw odkrył własności $\Delta$ heurystycznie, a dopiero po 10 latach znalazł dowód
 (być może wcześniej nie miał czasu).
 \end{description}

\noindent Zdefiniujmy liczby pentagonalne (pięciokątne) $$pent(i)=(3i-1)i/2$$
Nazwa pochodzi od interpretacji geometrycznej, podobnie jak dla liczb
trójkątnych.
Mamy:
$$pent(i) = pent(i-1)+3i+1$$
Liczby pentagonalne będziemy rónież nazywać liczbami trapezowymi pierwszego typu,
a liczby $pent(i)+i$ nazywamy liczbami trapezowymi drugiego typu,
patrz lewy/prawy trapez na Rysunku \ref{trapezy}.

\begin{center}
      \begin{tabular}{r|r|r|r|r|r|r|r|r|r|r|r|r|r|r}
        $i:$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline
        %$w[i]$ & & $c$ & $a$ & $a$ & $b$ & $b$ & $c$ & $a$ & $b$ & $b$ & $c$ & $a$ & $a$ & $a$ \\\hline
        $pent(i):$ & 1 & 5 & 12 & 22 &35 & 51 & 70
      \end{tabular}
    \end{center}

\noindent Ponadto zdefinujmy  współczynniki
pentagonalne:

\begin{equation}\label{wzor}
    e(k) =
      \left\{
      \begin{array}{cl} %1  & k=0\\
        (-1)^{i+1} & \mbox{if } k=pent(i)\ \textrm{lub}\ k=pent(i)+i\\
        0 & \mbox{w przeciwnym przypadku.}
      \end{array}
      \right.
  \end{equation}

  \noindent {\bf Lemat Kluczowy.}
  \begin{equation}\label{key-lemma}
  \Delta(k) \; =\; e(k).
  \end{equation}
  \myskip
  Możemy teraz zapisać algorytm (jedną iterację) liczenia $p(n)$ następująco:

  \begin{equation}
 p(n)\;=\; \sum_{i\ge 1}\; (-1)^{i+1}\cdot (\; p(n-pent(i))+p(n-pent(i)-i)\;)
 \end{equation}\label{equation2}
 W równaniu tym korzystamy jedynie z wartości $i$ takich, że $pent(i)\le n$, mamy jedynie $O(\sqrt{n})$ takich wartości.
 Liczby $pent(i)$ możemy łatwo policzyć.
 \myskip
{\bf Twierdzenie.}\ Liczby $p(1),p(2), ..p(n)$ możemy policzyć w czasie $O(n\sqrt{n})$ i pamięci $O(n)$.

\section*{Dowód równania~\ref{equation1}}
Uzasadnienie jest sprytną manipulacją algebraiczną, korzystającą z tego że dwa wielomiany będące tą samą funkcją
mają takie same współczynniki przy tych samych potęgach zmiennej.
Sztuczka polega na tym, żeby te same wielomiany przedstawić na dwa różne sposoby,
z jednego wymnożenia otrzymujemy wynik, który przyrównujemy do wymnożenia w innej formie.
Zdefiniujmy:
$$\phi(x)=(1+x+x^2+\ldots x^n),\ \psi(x)=1-x.$$
$$W_1(x)\ =\ \prod_{i=1}^n\;\phi(x^i),\ W_2(x)\ =\ \prod_{i=1}^n\;\psi(x^i).$$
Wprowadżmu notację $\eqn{n}$ dla równości wielomianów z dokładnością do potęg wyższych niż $n$, inaczej mówiąc 
bierzemy resztę z dzielenia przez $x^{n+1}$.
Zauważmy, że zachodzi dosyć łatwe równanie:
\begin{equation}\label{wielomany1}
W_1(x)\cdot W_2(x) \eqn{n}  1.
\end{equation}
Powyższa równość trochę przypomina sytuację w równości  $(1+x)(1-x)= 1-x^2$.
Przedstawimy teraz te same wielomiany w innej formie.
\begin{equation}\label{wielomiany2}
W_1(x)\;\eqn{n}\; p(0)x^0+p(1)x^1+p(2)x^2+..p(n)x^n,\ W_2(x)\;\eqn{n}\; 1-\Delta(1)x^2-\Delta(2)x^2...-\Delta(n)x^n.
\end{equation}
Z równania~\ref{wielomany1}   dla $n\ge 1$ wynika, że współczynnik przy $x^n$ w iloczynie $W_1(x)\cdot W_2(x)$ wynosi zero,
korzystając z  równania~\ref{wielomiany2} możemy ten współczynnik przedstawić jako kombinacje iloczynów
  $p(i),\Delta(j)$, gdzie $i+j=n$, w rezultacie
otrzymujemy:
$$p(n)\cdot 1 - p(n-1)\cdot \Delta(1)- p(n-2)\cdot \Delta(2)- p(n-3)\cdot \Delta(3)\ldots - \Delta(n)\cdot p(0)\ =\ 0$$
Stąd wynika bezpośrednio równanie~\ref{equation1}.

\section*{Dowód kluczowego lematu (równania~\ref{key-lemma})}

  \noindent W sekcji tej rozważamy tylko podziały o różnych częściach.
  \noindent Dwód kluczowego lematu wymaga rozważenia interpretacji geometrycznej podziałów.
  
Podział liczby może być przedstawiony w postaci diagramu zwanego diagramem Ferrersa,
w kolejnym wierszu liczba elementów odpowiada liczbie $\lambda_j$.
Diagramy Ferrersa dla przykładowych podziałów liczb 22 i 26 są przedstawione na rysunku \ref{trapezy}.
Są to bardzo szczególne podziały, które będziemy nazywać trapezowymi.


\noindent
Podział trapezowy rzędu $k$ pierwszego typu jest postaci $(k+k-1,\; k+k-2,\; k+k-3,\ldots , k)$ a drugiego typu
postaci $(k+k,\; k+k-1,\; k+k-1,\ldots , k+1)$.
\myskip {\bf Obserwacja}. Podział trapezowy mający $pen(k)$ lub $pen(k)+k$ elementów składa
się z $k$ części.
\myskip
\begin{figure}[h]
    \centering
    \includegraphics[width=.7\textwidth]{bijekcja_euler2.png}
    \caption{
      \label{trapezy}
      Trapezy rzędu $k$, gdzie $k=4$,  pierwszego typu ma $pen(k)$ elementów, a drugiego typu ma $pen(k)+k$ elementów.
      Podziały odpowiadające tego typu trapezom nazywamy podziałami trapezowymi.
      }
  \end{figure}
  
\noindent Liczbę $n$ nazywamy liczbą trapezową gdy
istnieje podział $n$ będący trapezowym, zawsze jest co najwyżej jeden taki podział dla danego $n$.
\myskip
\noindent {\bf Obserwacja.}\ Liczby trapezowe są postaci $pen(j)$ lub $pen(j)+j$.
\myskip
\noindent Dla trapezu $\pi$ przez $k(\pi)$ oznaczmy liczbę elementów na prawej diagonali poczynając od górnej prawej strony,
jeśłi odpowiadającym podziałem jest $(a_1,a_2,\ldots a_r)$ to $k(\pi)$ jest największą liczbą naturalną
taką, że  $a_i-1=a_{i+1}$ dla $i=1,2,\ldots k(\pi)-1$. Przez $h(\pi)=a_r$ oznaczmy liczbę elementów w najmniejszej części.
\myskip
Jeśli podział nie jest trapezowy oraz $h(\pi)\le k(\pi)$ to $F(\pi)$ jest podziałem powstającym z $\pi$ przez
dodanie do każdej z pierwszych $k(\pi)$ części po jednym elemencie i usunięcie
najmniejszej (dolnej) części, patrz Rysunek~\ref{funkcja_pi}.

  \begin{figure}[h]
    \centering
    \includegraphics[width=.7\textwidth]{bijekcja_euler.png}
    \caption{Działanie funkcji $F$.
           }\label{funkcja_pi}
  \end{figure}

Podziały o parzystej/nieparzystej liczbie częsci nazywamy parzystymi/nieparzystymi.
Zauważmy, że funkcja $F$ zmienia parzystość podziału. Zachodzi następujący dosyć oczywisty fakt.
\myskip
\noindent {\bf Własność funkcji $F$}.\ $F$ jest bijekcją między  nietrapezowymi podziałąmi $n$ z $h(p)\le k(\pi)$  i
 nietrapezowymi podziałami $n$ z $h(p)> k(\pi)$.
\begin{equation}
   \pp_{odd}(k)-\pp_{even}(k) =
      \left\{
      \begin{array}{cl} %1  & k=0\\
         1 & \mbox{gdy}\ n\ \textrm{jest nieparzystą liczbą trapezową}\\
         -1 & \mbox{gdy}\ n \ \textrm{jest parzystą liczbą trapezową}\\
        0 & \mbox{w przeciwnym przypadku.}
      \end{array}
      \right.
  \end{equation}

Z powyższej własności wynika:
$$\pp_{odd}(k)-\pp_{even}(k) \;=\; e(k)\ \mbox{dla kazdego} k.$$

\begin{figure}[h]
    \centering
    \includegraphics[width=.6\textwidth]{bijekcja_euler3.png}
    \caption{
      \label{bijekcja_euler2}
     Zgrupowanie podziałów nietrapezowych liczby $n=15$ korzystając z funkcji $F$ .
      }
  \end{figure}

\section*{Nieoczekiwana relacja między funkcjami $p(n)$ i $\sigma(n)$}
Jako ciekawostkę podamy, bez uzasadnienia, pewien związek dwóch pozornie
{\em odległych} funkcji $p(n), \sigma(n)$, gdzie $\sigma(n)$ oznacza sumę dzielników
liczby $n$ (włącznie z $n$). Mamy
\begin{center}
      \begin{tabular}{r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r}
        $n:$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7&8&9&10&11&12&13&14&15&16 \\ \hline
        %$w[i]$ & & $c$ & $a$ & $a$ & $b$ & $b$ & $c$ & $a$ & $b$ & $b$ & $c$ & $a$ & $a$ & $a$ \\\hline
        $\sigma(n):$ & 0 & 1 & 3 & 4& 7 &6 & 12 & 8 & 15&13&18&12& 28&14&24 & 24&31
      \end{tabular}
    \end{center}
   Dla funkcji $\sigma$ zachodzi prawie taka sama rekurencja jak dla $p(n)$, jedyna różnica to
   zastąpienie $p(0)$ przez $n$ we wzorze~\ref{equation1}.
  Funkcja  $\sigma(n)$ spełnia rekurencję:
 \begin{equation}\label{sigma}
 \sigma(n)\;=\; \sum_{k= 1}^{n-1}\; \Delta(k)\cdot \sigma(n-k)\;+\;\Delta(n)\cdot n.
 \end{equation}\label{equation}

 \noindent {\bf Przykład.}\ Dla $n=15$ mamy:
 $$\sigma(15)\;=\;\sigma(15-1)+\sigma(15-2)-\sigma(15-5)-\sigma(15-7)+\sigma(15-12)+15\;=\; 24+14-18-15+4+15\;=\;24.$$
 $$p(15)\;=\;p(15-1)+p(15-2)-p(15-5)-p(15-7)+p(15-12)+p(0)\;=\; 135+101-42-22+3+1\;=\;176.$$
 %
 Ponieważ wartości $\Delta(k)$ są związane z liczbami pentagonalnymi tak jak poprzednio, to
 wszystkie wartości $\sigma(n),\sigma(n-1),\ldots \sigma(1)$ można policzyć
 w czasie $O(n\sqrt{n})$ i pamięci $O(n)$ tak jak poprzednio zrobiliśmy to
 dla wartości $p(n)$.
 \
 \noindent Zachodzi również inny zadziwiający związek:
 \begin{equation}
 \sigma(n)\;=\; \sum_{k= 1}^{n}\; k\cdot \Delta(k)\cdot p(n-k).
 \end{equation}\label{suprise}
 %
 Jesli $n=\prod\; p_i^{m_i}$, gdzie $p_i$ liczby pierwsze to $$\sigma(n)\;=\; \prod\; (p_i^{m_i+1}-1)\;/\; \prod\; (p_i-1)$$
 Wydaje sie ze liczenie $\sigma$ dla wszystkich liczb $1,2,\ldots n$ jednak jest szybsze korzystajac ze wzoru~\ref{sigma}
 i liczb pentagonalnych niż korzystając z ostatnego wzoru.
\myskip
{\bf Dygresja.}
\
 Liczby $\sigma(n)$ są związane z tzw. liczbami {\em doskonałymi}, tzn. takimi że $\sigma(n)=2n$.
Wiadomo, ze  $n$ parzyste  jest doskonałe wtw. gdy $n=2^{p-1}(2^p-1)$, gdzie $p, 2^p-1$ są
pierwsze, np. dla $p=11213$, $p=30402456$ (43-cia liczba doskonała).
Pierwsze 7 liczb doskonałych to:

\centerline{ 6, 28, 496, 8128, 33550336,  8 589 869 056, 137 438 691 328.}
Pierwsze 4 liczby doskonałe policzył już Euklides. Kilka następnych Euler. Potem już był potrzebny komputer.
\noindent
Nie wiadomo czy  liczb parzystych doskonałych jest nieskonczenie wiele ani też czy istnieje
choćby jedna nieparzysta liczba doskonała.
\myskip\myskip
{\bf Więcej informacji} na temat liczenia podziałów można znależć w:
\vskip 0.5cm
http://www.math.psu.edu/vstein/alg/antheory/preprint/andrews/chapter.pdf

http://www.rowan.edu/colleges/csm/departments/math/facultystaff/osler/

89\%20Surprising\%20Connection\%20Between\%20Partitions\%20and\%20Divisors.pdf.pdf

http://hkumath.hku.hk/~mks/EulerHeuristicReasoning.pdf
\end{document} 