Perfekte Partition

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

Es sei eine natürliche Zahl $n \in ℕ$ ^{[A 1]} gegeben und weiter eine Partition

(n = n_{1} + n_{2} + \dots + n_{k})

mit

k, n_{1}, n_{2}, \dots, n_{k} \in ℕ

und

n_{1} \geq n_{2} \geq \dots \geq n_{k}

.

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

jede der Zahlen

m = 1, 2, \dots, n - 1

sich stets aus gewissen der in dieser Partition auftretenden Summanden

n_{1}, n_{2}, \dots, n_{k}

auf genau eine Art als Summe darstellen lässt,

so bezeichnet man sie als perfekt oder auch als vollkommen (Vorlage:EnS).^[2]^[1]^[3]^[4]

Eigenschaften und Beispiele

In einer perfekten Partition tritt die $1$ stets als kleinster Summand auf.
Für jedes $n \in ℕ$ ist die aus exakt $n$ Summanden $1$ aufgebaute Partition $(n = 1 + 1 + \dots + 1)$ stets perfekt. Weiter ist für jede ungerade Zahl $n = 2 \cdot k + 1 (k \in ℕ)$ die aus einem einzigen Summanden $1$ und aus exakt $k$ Summanden $2$ aufgebaute Partition $(n = 1 + 2 + 2 + \dots + 2)$ stets perfekt.^{[A 2]}
Für die Zahl $7$ sind die Partitionen $(7 = 4 + 2 + 1)$ , $(7 = 4 + 1 + 1 + 1)$ , $(7 = 2 + 2 + 2 + 1)$ und $(7 = 1 + 1 + 1 + 1 + 1 + 1 + 1)$ perfekt.^[5]
Für die Zahl $4$ ist $(4 = 2 + 1 + 1)$ keine perfekte Partition, denn es gibt etwa für die darunter liegende Zahl $2$ die beiden Partitionen $(2 = 2)$ und $(2 = 1 + 1)$ .
Für die Zahl $9$ ist $(9 = 4 + 2 + 2 + 1)$ keine perfekte Partition, denn es gibt etwa für die darunter liegende Zahl $5$ die beiden Partitionen $(5 = 4 + 1)$ und $(5 = 2 + 2 + 1)$ .

Satz von MacMahon

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 $f \in ℕ$ mit $f > 1$ genau dann gegeben, wenn ein $t \in ℕ$ sowie ein aus $f$ -Teilern $f_{1} > 1, \dots, f_{t} > 1$ bestehendes $t$ -Tupel $(f_{1}, \dots, f_{t})$ vorliegen, so dass $f$ der Produktdarstellung $f = f_{1} \cdot \dots \cdot f_{t}$ 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 $n \in ℕ$ stimmen die Anzahl der perfekten Partitionen von $n$ einerseits und die Anzahl der geordneten Faktorisierungen der Folgezahl $f = n + 1$ andererseits stets überein.

Korollar

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

Ist für eine natürliche Zahl $n \in ℕ$ die Folgezahl $f = n + 1$ eine Primzahl, so besitzt $n$ genau eine perfekte Partition, nämlich die aus den $n$ Summanden $1$ aufgebaute triviale Partition $(n = 1 + 1 + \dots + 1)$ .

Anzahlfunktion

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

Diese Zahlenfolge der $P e r (n)$ beginnt mit folgenden Werten:^{[A 4]}

(P e r (n))_{n = 1, 2, 3, \dots} = (1, 1, 2, 1, 3, 1, 4, 2, 3, 1, 8, \dots)

(Vorlage: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 $k \geq 2, n$ und jede Primzahl $p$ stets die Kongruenz

P e r (n \cdot p^{k} - 1) \equiv 0 (\mod 2^{k - 1})

gegeben.^[9]

Verallgemeinerungen

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 (Vorlage:DeS) vor.^[10]^[11]

Literatur

Weblinks

Einzelnachweise

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

Anmerkungen

↑ Hier ist stets $ℕ = {1, 2, 3, \dots}$ .
↑ 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
↑ Von dem trivialen Teiler $1$ wird hier also stets abgesehen. Der andere triviale Teiler $f$ wird hier indes nicht ausgeschlossen.
↑ Oft wird auch für $n = 0$ ein Wert gesetzt, nämlich $P e r (0) = 1$ . Die hier genannten Komponenten dieser Zahlenfolge reichen bis $n = 11$ und dem Wert $P e r (11) = 8$ .

[JJT-a-1] 1,0 ^1,1 J. J. Tattersall: Elementary number theory in nine chapters. 1999, S. 300 ff.

[HRH-WH-a-3] Halder-Heise: Elementary number theory in nine chapters. 1999, S. 300 ff.

[MA-a-4] 3,0 ^3,1 Martin Aigner: Combinatorial Theory. 1979, S. 84

[JR-a-5] John Riordan: An Introduction to Combinatorial Analysis. 1978, S. 123–124

[JJT-b-7] 5,0 ^5,1 ^5,2 Tattersall, op. cit., S. 300.

[HRH-WH-b-9] Halder/Heise, op. cit., S. 83

[HRH-WH-c-10] Halder/Heise, op. cit., S. 84

[JR-b-11] Riordan, op. cit., S. 124

[RHH-KSW-1-13] Agarwal/Subbarao: Some properties of perfect partitions. In: Indian J. Pure Appl. Math. 22, S. 737–743

[AKA-RS-1-14] Agarwal/Sachdeva: Combinatorics and n-color perfect partitions. In: Ars Combin. 136, S. 29–43

[AOM-1-15] Augustine O. Munagi: Perfect compositions of numbers. In: J. Integer Seq. 23 , Art. 20.5.1

[2] Hier ist stets $ℕ = {1, 2, 3, \dots}$ .

[6] 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

[8] Von dem trivialen Teiler $1$ wird hier also stets abgesehen. Der andere triviale Teiler $f$ wird hier indes nicht ausgeschlossen.

[12] Oft wird auch für $n = 0$ ein Wert gesetzt, nämlich $P e r (0) = 1$ . Die hier genannten Komponenten dieser Zahlenfolge reichen bis $n = 11$ und dem Wert $P e r (11) = 8$ .

[1]

[A 1]

[2]

[3]

[4]

[A 2]

[5]

[A 3]

[6]

[7]

[8]

[A 4]

[9]

[10]

[11]

Perfekte Partition

Inhaltsverzeichnis

Definition

Eigenschaften und Beispiele

Satz von MacMahon

Korollar

Anzahlfunktion

Verallgemeinerungen

Literatur

Weblinks

Einzelnachweise

Anmerkungen

Navigationsmenü

Perfekte Partition

Definition

Eigenschaften und Beispiele

Satz von MacMahon

Korollar

Anzahlfunktion

Verallgemeinerungen

Literatur

Weblinks

Einzelnachweise

Anmerkungen

Navigationsmenü

Suche