Perfekte Partition

In der Additiven Zahlentheorie, einem der Teilgebiete der Mathematik innerhalb der Zahlentheorie
(Weitergeleitet von Satz von MacMahon)

In der Additiven Zahlentheorie, einem der mathematischen Teilgebiete innerhalb der Zahlentheorie, wie auch im Teilgebiet der Kombinatorik untersucht man, ob eine zu einer natürlichen Zahl gegebene Partition so beschaffen ist, dass jede kleinere natürliche Zahl sich ebenfalls als Summe von einzelnen Summanden dieser Partition eindeutig darstellen lässt. Diese Fragestellung und das zugehörige Konzept gehen zurück auf den Mathematiker Percy Alexander MacMahon (1854–1929).[1]

Definition

Bearbeiten

Es sei eine natürliche Zahl  [A 1] gegeben und weiter eine Partition

  mit   und  .

Genügt diese Partition zusätzlich der Bedingung, dass

jede der Zahlen   sich stets aus gewissen der in dieser Partition auftretenden Summanden   auf genau eine Art als Summe darstellen lässt,

so bezeichnet man sie als perfekt oder auch als vollkommen (englisch perfect partition).[2][1][3][4]

Eigenschaften und Beispiele

Bearbeiten
  • In einer perfekten Partition tritt die   stets als kleinster Summand auf.
  • Für jedes   ist die aus exakt   Summanden   aufgebaute Partition   stets perfekt. Weiter ist für jede ungerade Zahl   die aus einem einzigen Summanden   und aus exakt   Summanden   aufgebaute Partition   stets perfekt.[A 2]
  • Für die Zahl   sind die Partitionen   ,   ,   und   perfekt.[5]
  • Für die Zahl   ist   keine perfekte Partition, denn es gibt etwa für die darunter liegende Zahl   die beiden Partitionen   und  .
  • Für die Zahl   ist   keine perfekte Partition, denn es gibt etwa für die darunter liegende Zahl   die beiden Partitionen   und  .

Satz von MacMahon

Bearbeiten

Die perfekten Partitionen stehen in unmittelbarer Beziehung zu den sogenannten geordneten Faktorisierungen von natürlichen Zahlen.

Eine solche geordnete Faktorisierung ist für eine natürliche Zahl   mit   genau dann gegeben, wenn ein   sowie ein aus  -Teilern   bestehendes  -Tupel   vorliegen, so dass   der Produktdarstellung   genügt.[A 3]

Hier gilt nun ein grundlegender Satz, der dem Mathematiker James Joseph Tattersall zufolge auf MacMahon zurückgeht[5] und sich darstellen lässt wie folgt:[6][3][5]

Für jede natürliche Zahl   stimmen die Anzahl der perfekten Partitionen von   einerseits und die Anzahl der geordneten Faktorisierungen der Folgezahl   andererseits stets überein.

Korollar

Bearbeiten

Aus dem MacMahon'schen Satz gewinnt man eine direkte Folgerung:[7][8]

Ist für eine natürliche Zahl   die Folgezahl   eine Primzahl, so besitzt   genau eine perfekte Partition, nämlich die aus den   Summanden   aufgebaute triviale Partition   .

Anzahlfunktion

Bearbeiten

Mit den perfekten Partitionen ist die Frage nach den zugehörigen Anzahlen verbunden. Es geht also für jedes   um die Anzahl aller Möglichkeiten,   in Form einer perfekten Partition darzustellen.

Diese Zahlenfolge der   beginnt mit folgenden Werten:[A 4]

  (Folge A002033 in OEIS).

Dabei gelten für diese Anzahlen oft interessante Kongruenzbeziehungen, die denen ähneln, die schon Srinivasa Ramanujan für die gewöhnliche Partitionsfunktion gefunden hat. So ist etwa für je zwei natürliche Zahlen   und jede Primzahl   stets die Kongruenz

 

gegeben.[9]

Verallgemeinerungen

Bearbeiten

Das Konzept der perfekten Partition ist weiter verallgemeinert worden. So legten etwa A. K. Agarwal und R. Sachdeva in 2018 die sogenannten n-color perfect partitions (deutsch etwa: n-gefärbte perfekte Partitionen) vor.[10][11]

Literatur

Bearbeiten
Bearbeiten

Einzelnachweise

Bearbeiten
  1. a b J. J. Tattersall: Elementary number theory in nine chapters. 1999, S. 300 ff.
  2. Halder-Heise: Elementary number theory in nine chapters. 1999, S. 300 ff.
  3. a b Martin Aigner: Combinatorial Theory. 1979, S. 84
  4. John Riordan: An Introduction to Combinatorial Analysis. 1978, S. 123–124
  5. a b c Tattersall, op. cit., S. 300.
  6. Halder/Heise, op. cit., S. 83
  7. Halder/Heise, op. cit., S. 84
  8. Riordan, op. cit., S. 124
  9. Agarwal/Subbarao: Some properties of perfect partitions. In: Indian J. Pure Appl. Math. 22, S. 737–743
  10. Agarwal/Sachdeva: Combinatorics and n-color perfect partitions. In: Ars Combin. 136, S. 29–43
  11. Augustine O. Munagi: Perfect compositions of numbers. In: J. Integer Seq. 23 , Art. 20.5.1

Anmerkungen

Bearbeiten
  1. Hier ist stets  .
  2. Bei diesen beiden Arten von perfekten Partitionen spricht man auch von den trivialen perfekten Partitionen; vgl.: Wang, E Fang: Perfect partitions. In: Chinese Ann. Math. Ser. B 7, S. 267–272
  3. Von dem trivialen Teiler   wird hier also stets abgesehen. Der andere triviale Teiler   wird hier indes nicht ausgeschlossen.
  4. Oft wird auch für   ein Wert gesetzt, nämlich  . Die hier genannten Komponenten dieser Zahlenfolge reichen bis   und dem Wert   .