Multiplikative Partition

Eine multiplikative Partition (auch ungeordnete Faktorisierung ) einer natürlichen Zahl ${\displaystyle n>1}${\displaystyle n>1} ist eine Art, diese Zahl als Produkt natürlicher Zahlen größer als ${\displaystyle 1}${\displaystyle 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 ${\displaystyle n}${\displaystyle 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.^[1]

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

Die Zahl 30 hat 5 multiplikative Partitionen, nämlich ${\displaystyle 30=2\cdot 15=3\cdot 10=5\cdot 6=2\cdot 3\cdot 5}${\displaystyle 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 ${\displaystyle 81=3\cdot 27=9\cdot 9=3\cdot 3\cdot 9=3\cdot 3\cdot 3\cdot 3}${\displaystyle 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: ${\displaystyle 3^{4}}${\displaystyle 3^{4}}

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

Sei ${\displaystyle a_{n}}${\displaystyle a_{n}} die Anzahl aller multiplikativen Partitionen von ${\displaystyle n}${\displaystyle n}. Die ersten Werte von ${\displaystyle a_{n}}${\displaystyle a_{n}} lauten:

1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 5, 1, ... Folge A001055 in OEIS

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

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

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

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

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

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

${\displaystyle \exists p\in \mathbb {P} :n\equiv 0\mod p}${\displaystyle \exists p\in \mathbb {P} :n\equiv 0\mod p}

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 ${\displaystyle m}${\displaystyle m}. Dies ist eindeutig weil es die Primfaktorzerlegung ebenfalls ist.

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

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:

${\displaystyle \forall p\in \mathbb {P} ~\forall q\in \mathbb {P} \setminus \left\{p\right\}~\forall r\in \mathbb {P} \setminus \left\{p,q\right\}:\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}${\displaystyle \forall p\in \mathbb {P} ~\forall q\in \mathbb {P} \setminus \left\{p\right\}~\forall r\in \mathbb {P} \setminus \left\{p,q\right\}:\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 ${\displaystyle p}${\displaystyle p}, ${\displaystyle q}${\displaystyle q} und ${\displaystyle r}${\displaystyle r} – wie formalisiert – paarweise verschiedene Primzahlen sind, wobei ${\displaystyle \sigma _{0}}${\displaystyle \sigma _{0}} die Teileranzahlfunktion ist und wobei ${\displaystyle \sigma _{k}}${\displaystyle \sigma _{k}} die Teilerfunktion wäre. Dieses Beispiel wurde konstruiert aus den multiplikativen Partitionen ${\displaystyle 12=2\cdot 6=3\cdot 4=2\cdot 2\cdot 3}${\displaystyle 12=2\cdot 6=3\cdot 4=2\cdot 2\cdot 3}.

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

${\displaystyle n=\prod _{i=1}^{k}t_{i}}${\displaystyle n=\prod _{i=1}^{k}t_{i}}

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

${\displaystyle \prod _{i=1}^{k}p_{i}^{t_{i}-1}}${\displaystyle \prod _{i=1}^{k}p_{i}^{t_{i}-1}},

wobei alle ${\displaystyle p_{i}}${\displaystyle p_{i}} paarweise verschiedene Primzahlen sind.

1. ↑ "The American Mathematical Monthly > Vol. 90, No. 7, Aug. - Sep., 1983 > On the Number of Multiplicative Partitions". Abgerufen am 19. Mai 2014

• Zahlentheorie
• Primzahl