Multiplikative Partition

Eine multiplikative Partition (auch ungeordnete Faktorisierung) einer natürlichen Zahl $n>1$ ist eine Art, diese Zahl als Produkt natürlicher Zahlen größer als $1$ darzustellen. Dabei sind zwei Faktorisierungen gleich, wenn jeder Faktor einer Faktorisierung auch in der anderen vorkommt und sie sich nur in der Reihenfolge unterscheiden. Dabei wird die Zahl $n$ selbst auch als Partition von sich selbst betrachtet. Multiplikative Partitionen werden spätestens seit dem Jahre 1923 erforscht, damals allerdings unter dem lateinischen Namen „factorisatio numerorum“. Der heutige Name entstand vermutlich durch einen im Jahre 1983 veröffentlichten Artikel von Jeffrey Shallit und John F. Hughes in der Zeitschrift „American Mathematical Monthly“ über dieses Thema.

Beispiele

Die Zahl 20 hat 4 multiplikative Partitionen, nämlich $20=2\cdot 10=4\cdot 5=2\cdot 2\cdot 5$.

Die Zahl 30 hat 5 multiplikative Partitionen, nämlich $30=2\cdot 15=3\cdot 10=5\cdot 6=2\cdot 3\cdot 5$. Die Zahl 30 ist quadratfrei.

Die Zahl 81 hat 5 multiplikative Partitionen, nämlich $81=3\cdot 27=9\cdot 9=3\cdot 3\cdot 9=3\cdot 3\cdot 3\cdot 3$. Die Zahl 81 lässt sich als Primzahlpotenz darstellen: $3^4$

Die Zahl 109 hat nur eine multiplikative Partition, nämlich sich selbst. Sie ist zugleich eine Primzahl.

Anzahl

Sei $a_n$ die Anzahl aller multiplikativen Partitionen von $n$. Die ersten Werte von $a_n$ lauten:

1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 5, 1, … Vorlage:OEIS

Percy Alexander MacMahon und A. Oppenheim bemerkten, dass die Dirichletreihen-generierende Funktion $f(s)$ ebenfalls die folgende Produktdarstellung hat:

$f(s)=\sum _{n=1}^{\mathrm{\infty }}\frac{a_n}{n^s}=\prod _{k=2}^{\mathrm{\infty }}\frac{1}{1-k^{-s}}$

Spezialfälle

Ist $n$ quadratfrei – enthält also keine Primzahl mehr als ein Mal in der Primfaktorzerlegung, bzw. $\mu (n)\ne 0$, wobei $\mu (n)$ für die Möbiusfunktion steht –, so ist die Anzahl der multiplikativen Partitionen $B_{\omega (n)}$, wobei $B_i$ die $i$-te Bellsche Zahl und $\omega (n)$ die Anzahl der einzigartigen Primfaktoren von $n$ ist.

Der zweite Spezialfall setzt voraus, dass die Zahl $n$ das Resultat einer Potenz mit einer Primzahl als Basis und mit einem natürlichen Exponenten ist. Formal:

$\mathrm{\exists }p\in \mathbb{P}\mathrm{\exists }m\in \mathbb{N}:n=p^m$

Wobei $\mathbb{P}$ für die Menge aller Primzahlen steht. Diese Vorbedingung lässt sich auch als Kongruenz notieren:

$\mathrm{\exists }p\in \mathbb{P}:n\equiv 0modp$

Ist eine dieser Bedingungen erfüllt – wenn es eine ist, so ist es die andere automatisch auch –, dann ist die Anzahl der möglichen multiplikativen Partitionen gleich wie die additive Partition des Exponenten $m$. Dies ist eindeutig weil es die Primfaktorzerlegung ebenfalls ist.

Der dritte Spezialfall ist der trivialste. Er setzt voraus, dass $n$ selbst eine Primzahl ist, also dass $n\in \mathbb{P}$ gilt. Aufgrund der Definition von Primzahlen kann $n$ nur eine Faktorisierung haben, nämlich sich selbst.

Anwendung

In ihrem Artikel, den sie im Jahre 1983 veröffentlicht haben, beschrieben Jeffrey Shallit und John F. Hughes eine Anwendung multiplikativer Partitionen zur Klassifikation natürlicher Zahlen anhand der Teileranzahl. Beispielsweise:

$\mathrm{\forall }p\in \mathbb{P}\mathrm{\forall }q\in \mathbb{P}\setminus \left\{p\right\}\mathrm{\forall }r\in \mathbb{P}\setminus \{p,q\}:{\sigma }_0(p^{11})={\sigma }_0(p^5\cdot q)={\sigma }_0(p^3\cdot q^2)={\sigma }_0(p^2\cdot q\cdot r)=12$

Wobei $p$, $q$ und $r$ – wie formalisiert – paarweise verschiedene Primzahlen sind, wobei ${\sigma }_0$ die Teileranzahlfunktion ist und wobei ${\sigma }_k$ die Teilerfunktion wäre. Dieses Beispiel wurde konstruiert aus den multiplikativen Partitionen $12=2\cdot 6=3\cdot 4=2\cdot 2\cdot 3$.

Allgemein lässt sich sagen, für jede multiplikative Partition von $n$ mit $k$ Faktoren (wobei $t_i$ ein Faktor ist für $1\le i\le k$)

$n=\prod _{i=1}^k{t}_i$

gibt es dazugehörig eine Menge natürlicher Zahlen mit genau $n$ Teiler. Jede dieser Zahlen hat die Form

$\prod _{i=1}^k{p}_i^{t_i-1}$,

wobei alle $p_i$ paarweise verschiedene Primzahlen sind.