Eine multiplikative Partition (auch ungeordnete Faktorisierung) einer natürlichen Zahl ist eine Art, diese Zahl als Produkt natürlicher Zahlen größer als 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 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]

Beispiele

Bearbeiten

Die Zahl 20 hat 4 multiplikative Partitionen, nämlich  .

Die Zahl 30 hat 5 multiplikative Partitionen, nämlich  . Die Zahl 30 ist quadratfrei.

Die Zahl 81 hat 5 multiplikative Partitionen, nämlich  . Die Zahl 81 lässt sich als Primzahlpotenz darstellen:  

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

Sei   die Anzahl aller multiplikativen Partitionen von  . Die ersten Werte von   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   ebenfalls die folgende Produktdarstellung hat:

 

Spezialfälle

Bearbeiten

Ist   quadratfrei – enthält also keine Primzahl mehr als ein Mal in der Primfaktorzerlegung, bzw.  , wobei   für die Möbiusfunktion steht –, so ist die Anzahl der multiplikativen Partitionen  , wobei   die  -te Bellsche Zahl und   die Anzahl der einzigartigen Primfaktoren von   ist.

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

 

Wobei   für die Menge aller Primzahlen steht. Diese Vorbedingung lässt sich auch als Kongruenz notieren:

 

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  . Dies ist eindeutig weil es die Primfaktorzerlegung ebenfalls ist.

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

Anwendung

Bearbeiten

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:

 

Wobei  ,   und   – wie formalisiert – paarweise verschiedene Primzahlen sind, wobei   die Teileranzahlfunktion ist und wobei   die Teilerfunktion wäre. Dieses Beispiel wurde konstruiert aus den multiplikativen Partitionen  .

Allgemein lässt sich sagen, für jede multiplikative Partition von   mit   Faktoren (wobei   ein Faktor ist für  )

 

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

 ,

wobei alle   paarweise verschiedene Primzahlen sind.

Einzelnachweise

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