Grundbegriffe der Wahrscheinlichkeitsrechnung: Binomialkoeffizienten, das Pascalsche Dreieck und der n-dimensionale Hyperwürfel

Binomialkoeffizienten und einige einfache Anwendungen in Abzählproblemen (wie die Anzahl der möglichen Ergebnisse beim Zahlenlotto) wurden bereits in den Begriffsbildungen der Kombinatorik vorgestellt. Hier werden die grundlegenden Eigenschaften der Binomialkoeffizienten diskutiert: die Pascalsche Rekursionsformel, der Aufbau des Pascalschen Dreiecks, der binomische Satz. Binomialkoeffizienten treten in unüberschaubar vielen Bereichen der Mathematik auf und ihr Auftreten sollte immer als Hinweis auf - mehr oder weniger offensichtliche - Querverbindungen verstanden werden. Als Beispiel einer dieser Querverbindungen wird der Zusammenhang der Binomialkoeffizienten mit dem n-dimensionalen Hyperwürfel diskutiert.

walter

07 Jun. 2021

Dualzahl Kombination ohne Wiederholungen fallende Faktorielle binomischer Satz Kombinatorik Rekursionsformel Abzählprobleme Hyperwürfel Binomialkoeffizient Fakultät Pascalsches Dreieck Potenzmenge Hamming-Abstand Pascalsche Rekursionsformel

Inhaltsverzeichnis

Einordnung des Artikels

Ausgewählte Kapitel der Mathematik (für Programmierer, Informatiker, Ingenieure und Naturwissenschaftler)
- Wahrscheinlichkeitsrechnung
  - Grundbegriffe der Wahrscheinlichkeitsrechnung: einfache Abzählprobleme
  - Grundbegriffe der Wahrscheinlichkeitsrechnung: Begriffsbildungen der Kombinatorik
  - Grundbegriffe der Wahrscheinlichkeitsrechnung: Binomialkoeffizienten, das Pascalsche Dreieck und der n-dimensionale Hyperwürfel

Anwendungen der Binomialkoeffizienten werden in Spezielle Abzählprobleme: Kombinationen mit Wiederholungen und die Beweismethode Stars and Bars und Spezielle Abzählprobleme: Ziehen ohne Zurücklegen behandelt.

Einführung

Binomialkoeffizienten wurden schon in Grundbegriffe der Wahrscheinlichkeitsrechnung: Begriffsbildungen der Kombinatorik eingeführt; dort wurden unter dem Stichwort Kombinationen ohne Wiederholungen bereits einfache Anwendungen vorgestellt, etwa das Zahlenlotto "6 aus 49" oder das Abzählen der k-elementigen Teilmengen einer n-elementigen Menge. Derart einfache Beispiele werden hier nicht wiederholt. Stattdessen soll hier gezeigt werden:

Welche einfachen Eigenschaften haben die Binomialkoeffizienten? Symmetrie, Rekursionsformel.
Was versteht man unter dem Pascalschen Dreieck und wie werden darin die Binomialkoeffizienten angeordnet?
Wie hängen die Binomialkoeffizienten und das Pascalsche Dreieck mit dem n-dimensionalen Hyperwürfel zusammen?

Die letzte Frage soll einen Aspekt der Binomialkoeffizienten aufzeigen, der hier nur angedeutet aber nicht in seiner Vielfalt ausgeführt werden kann: Binomialkoeffizienten treten in zahlreichen Teilgebieten der Mathematik und ihrer Anwendung auf, womit man ganze Bücher füllen kann. Oft sind dies Teilgebiete, die eigentlich nichts mit Abzählproblemen zu tun haben. Das Auftreten der Binomialkoeffizienten sollte immer als ein Hinweis darauf verstanden werden, dass zwischen den Teilgebieten – vielleicht verborgene – Zusammenhänge bestehen, die es lohnt aufzudecken, da sie zu tieferen Einsichten führen.

Mit der Beschreibung des n-dimensionalen Hyperwürfels wird hier ein Beispiel aus der Geometrie gewählt, das man keinesfalls der Wahrscheinlichkeitsrechnung oder Kombinatorik zuordnen würde.

Weitere Anwendungen der Binomialkoeffizienten – dann wieder im Zusammenhang mit Abzählproblemen – werden in Spezielle Abzählprobleme: Kombinationen mit Wiederholungen und die Beweismethode Stars and Bars und Spezielle Abzählprobleme: Ziehen ohne Zurücklegen behandelt.

Viele Aussagen über die Binomialkoeffizienten lassen sich mit Hilfe des binomischen Satzes herleiten, der hier ebenfalls vorgestellt wird. Es wird auch eine geometrische Fragestellung diskutiert – wie viele Kanten hat ein n-dimensionaler Hyperwürfel? –, die eine Methode zeigt, wie man aus dem binomischen Satz weitere Aussagen ableiten kann.

Zuletzt soll noch erwähnt werden, dass der binomische Satz Namensgeber für die Binomialkoeffizienten war und nicht umgekehrt.

In den R-Skripten finden sich dann weitere Illustrationen der besprochenen Themen:

Eine einfache rekursive Berechnung des Pascalschen Dreiecks.
Erzeugen von Abbildungen des n-dimensionalen Hyperwürfels.

Die Binomialkoeffizienten und das Pascalsche Dreieck

Die Definition des Binomialkoeffizienten

Zum Rechnen mit Binomialkoeffizienten benötigt man die Fakultät n! einer natürlichen Zahl n, die man entweder iterativ (Gleichung (1) in Abbildung 1) oder rekursiv (Gleichung (2) in Abbildung 1) definieren kann.

Der Binomialkoeffizient "k aus n" wird definiert durch die Anzahl der k-elementigen Teilmengen, die man aus einer Menge M mit n Elementen bilden kann. Notiert wird der Binomialkoeffizient durch die Klammer-Schreibweise wie in Gleichung (5) in Abbildung 1.

Man kann sich leicht überlegen, wie der Binomialkoeffizient durch Fakultäten ausgedrückt wird, siehe Gleichung (5) und (6) in Abbildung 1:

Für die Auswahl des ersten Elementes aus einer k-elementigen Menge bestehen n Möglichkeiten.
Für die Auswahl des zweiten Elementes stehen nur noch n-1 Elemente zur Verfügung.
...
Für die Auswahl des k-ten Elementes stehen noch n-k+1 Elemente zur Verfügung.

Damit erhält man – vorerst, denn das ist noch nicht die gesuchte Anzahl – die fallende Faktorielle (Gleichung (3) und (4) in Abbildung 1):

P(n, k) = n · (n-1) · ... · (n-k+1).

Da die ausgewählten k Elemente wieder eine Menge bilden sollen, müssen diejenigen Auswahlen, die sich lediglich in der Anordnung der Elemente unterscheiden, ausgeschlossen werden. Aber dadurch fallen k! Permutationen der k ausgewählten Elemente zu einer k-elementigen Teilmenge zusammen und man erhält für den Binomialkoeffizienten den Ausdruck (6) in Abbildung 1, den man entweder mit der fallenden Faktoriellen P(n, k) oder nur mit Fakultäten schreiben kann.

Abbildung 1: Definition der Fakultät, der fallenden Faktoriellen und des Binomialkoeffizienten; weiter sind einige Spezialfälle für den Binomialkoeffizienten angegeben.

Um den Binomialkoeffizienten zweifelsfrei zu definieren, muss man einige Spitzfindigkeiten klären. Da der Binomialkoeffizient die Anzahl der k-elementigen Teilmengen einer n-elementigen Menge beschreibt, wird er null gesetzt, falls

k größer ist als n,
k oder n negativ sind (siehe Gleichung (7) in Abbildung 1).

Für k = n muss der Binomialkoeffizient "n aus n" gleich 1 sein, da die Menge M die einzige n-elementige Teilmenge von sich selbst ist. Man definiert dann auch "0 aus n" gleich 1, um anzudeuten, dass dann auch ihre Komplementmenge (die leere Menge) eindeutig bestimmt ist und die einzige 0-elementige Teilmenge von M darstellt (siehe Gleichung (8) in Abbildung 1).

Schwer zu interpretieren ist hingegen der Binomialkoeffizient "0 aus n", der ebenfalls gleich 1 gesetzt wird; nur diese Definition ist konsistent mit 0! = 1 (siehe Gleichung (9) in Abbildung 1).

Eigenschaften des Binomialkoeffizienten das Pascalsche Dreieck

Aus der Darstellung des Binomialkoeffizienten durch Fakultäten (Gleichung (6) in Abbildung 1) folgt die Symmetrie-Eigenschaft (1) in Abbildung 2. Die Gleichungen (8) in Abbildung 1 kann man als Spezialfall dieser Symmetrie lesen.

Die vermutlich wichtigste Eigenschaft der Binomialkoeffizienten ist die Pascalsche Rekursionsformel Gleichung (2) in Abbildung 2. Sie gilt für k, n ≥ 0. Setzt man zusätzlich zu dieser Rekursionsformel die Gleichung (7) in Abbildung 1 voraus, so kann man ausgehend von "0 aus 0" = 1 (Gleichung (9) in Abbildung 1) alle Binomialkoeffizienten berechnen. Sie lassen sich dann im sogenannten Pascalschen Dreieck anordnen, das weiter unten gezeigt wird.

Abbildung 2: Eigenschaften des Binomialkoeffizienten, nämlich die Symmetrie beim Übergang von k zu n-k, die Pascalsche Rekursionsformel und ihre Begründung sowie die Summe aller Binomialkoeffizienten "k aus n" zu gleichem n.

Zum Beweis der Rekursionsformel werden die beiden Binomialkoeffizienten auf der rechten Seite von Gleichung (2) mit Hilfe von Fakultäten dargestellt (Gleichung (3)) und auf gemeinsamen Nenner gebracht (Gleichung (4)), womit sich die linke Seite von Gleichung (2) ergibt.

Diese formale Beweis erscheint etwas unbefriedigend, wenn man Binomialkoeffizienten mit Abzählproblemen assoziiert. Es ist aber nicht schwer die Rekursionsformel in diesem Sinne zu interpretieren und einen kombinatorischen Beweis anzugeben.

Dazu geht man von einer Menge M mit n Elementen aus und spaltet ein Element x ab.

Die linke Seite von Gleichung (2) beschreibt die Anzahl aller k-elementigen Teilmengen von M. Diese lassen sich nun in 2 Gruppen einteilen (jede Teilmenge von M gehört genau einer Gruppe an):

k-elementige Teilmengen von M, die das Element x nicht enthalten und
k-elementige Teilmengen von M, die das Element x enthalten.

Man muss jetzt nur fragen, wie viele Teilmengen die beiden Gruppen enthalten.

Jeder Vertreter der ersten Gruppe ist eine k-elementige Teilmenge von M \ {x}.
Jeder Vertreter der zweiten Gruppe erzeugt – indem man x aus der Menge entfernt – eine (k-1)-elementige Teilmenge von M \ {x}.

Und da M \ {x} genau n-1 Elemente hat, ergeben sich die zwei Summanden auf der rechten Seite von Gleichung (2) in Abbildung 2.

Eine Teilmenge einer n-elementigen Menge M kann entweder 0 Elemente (die leere Menge), eine Element (die Elemente von M), 2 Elemente, ..., n Elemente (die Menge M selbst) haben. Auf der linken Seite von Gleichung (5) in Abbildung 2 werden die Anzahlen dieser Teilmengen addiert. Man kann Gleichung (5) somit als die Behauptung lesen, dass die Anzahl aller Teilmengen von M mit 2ⁿ übereinstimmt.

Für den Beweis gibt es viele Varianten; eine davon, die auf die Rekursionsformel für die Binomialkoeffizienten zurückgreift, ist in Gleichung (6) bis (8) gezeigt.

Der Beweis verwendet vollständige Induktion. Für n = 0 ist Gleichung (5) erfüllt, da auf beiden Seiten 1 steht.

Man geht jetzt davon aus, dass die Gleichung (5) für n gilt und versucht sie für n+1 zu beweisen. Dazu wird in Gleichung (6) die linke Seite von Gleichung (5) angesetzt (mit n+1 anstelle von n) und die Rekursionsformel verwendet, wodurch zwei Summen entstehen (jeweils über k von 0 bis n+1). Aus der ersten Summe wird der letzte Summand explizit aufgeführt, der 0 ergibt. In der zweiten Summe wird der neue Summationsindex k' = k-1 eingeführt und der erste Summand explizit aufgeführt (der auch 0 ergibt), siehe Gleichung (7). Für die beiden Summen mit jeweils n+1 Summanden kann die Induktionsvoraussetzung eingesetzt werden und man erkennt, dass Gleichung (5) auch für n+1 erfüllt ist, siehe Gleichung (8).

Aufgaben:

1. Veranschaulichen Sie sich den zuletzt gezeigten Beweis mit einer dreielementigen Menge M und geben Sie alle Teilmengen von M explizit an.

2. Jede Teilmenge A einer n-elementigen Menge M kann eindeutig mit einer n-stelligen Dualzahl identifiziert werden. Dazu durchläuft man die Elemente von M und schreibt eine 0 auf, wenn das Element nicht in A enthalten ist, beziehungsweise eine 1, wenn das Element in A enthalten ist.

Beweisen Sie durch Abzählen von Dualzahlen, dass Gleichung (5) in Abbildung 2 richtig ist.

Das Pascalsche Dreieck

Zu gegebenem n sind nur diejenigen Binomialkoeffizienten "k aus n" relevant, bei denen k = 0, 1, ..., n (für andere k sind die Binomialkoeffizienten gleich 0 und lassen sich nicht im Sinne einer "Anzahl k-elementiger Teilmengen" interpretieren). Das sind gerade n+1 Binomialkoeffizienten, deren Summe 2ⁿ ergibt.

Im Pascalschen Dreieck werden jetzt die Binomialkoeffizienten zeilenweise angeordnet: Der Zeilenindex durchläuft die Werte von n, der Spaltenindex durchläuft die relevanten Werte von k. Und da die Anzahl der Spalten mit n zunimmt, ergibt sich kein rechteckiges Schema (Matrix), sondern ein dreieckiges Schema, das üblicherweise wie in Abbildung 3 dargestellt wird und als Pascalsches Dreieck bezeichnet wird.

Im oberen Pascalschen Dreieck sind die Binomialkoeffizienten eingetragen, im unteren Pascalschen Dreieck die entsprechenden Zahlenwerte.

Abbildung 3: Das Pascalsche Dreieck, oben mit den Binomialkoeffizienten "k aus n"; in jeder Zeile stehen die Binomialkoeffizienten zu gleichem n und mit aufsteigendem k. Unten die mit Gleichung (5) beziehungsweise (6) aus Abbildung 1 berechneten Binomialkoeffizienten.

Die Rekursionsformel kann jetzt verwendet werden, um das Pascalsche Dreieck ausgehend von der oberen Spitze aufzubauen. Die Vorgehensweise wird in Abbildung 4 dargestellt:

In der nullten Zeile des Pascalschen Dreiecks wird der Binomialkoeffizient "0 aus 0" = 1 eingetragen.
Die beiden benachbarten (links und rechts) Binomialkoeffizienten sind gleich 0.
Aus der Kenntnis dieser drei Binomialkoeffizienten können die beiden relevanten Binomialkoeffizienten der ersten Zeile berechnet werden.
Dazu wird die Rekursionsformel angewendet: die Summe zweier nebeneinander liegender Binomialkoeffizienten liefert den darunter liegenden Binomialkoeffizient (siehe Abbildung 4 rechts).

Abbildung 4: Vorgehensweise zur sukzessiven Berechnung der Einträge im Pascalschen Dreieck (genauere Erklärung im Text).

Unten in den R-Skripten wird gezeigt, wie man die in Abbildung 4 gezeigte Berechnung der Binomialkoeffizienten mit wenigen Zeilen Quelltext realisieren kann.

Der binomische Satz

Der binomische Satz verallgemeinert die binomische Formel (siehe Gleichung (1) in Abbildung 5). Es gibt 2 Lesarten für den binomischen Satz:

Man kann ihn als algebraische Gleichheit auffassen, die die Potenz einer Summe a + b mit Hilfe von Potenzen von a beziehungsweise b ausgedrückt (siehe Gleichung (2) in Abbildung 5).
Man kann als eine Aussage über das Polynom n-ten Grades auf der linken Seite von Gleichung (3) in Abbildung 5 auffassen, in dem der Faktor 1 + x genau n-mal auftritt. Das Polynom auf der rechten Seite ist dagegen in Normalform geschrieben, also als Summe von Potenzen von x.

Abbildung 5: Der binomische Satz in 2 Lesarten: entweder als algebraische Gleichheit wie in (2) oder als Aussage über spezielle Polynome in (3). In beiden Fälen werden rechts die Binomialkoeffizienten verwendet, um eine Darstellung als Summe von Potenzen zu ermöglichen.

Gemeinsam ist beiden Lesarten, dass die Binomialkoeffizienten verwendet werden, um den Term auf der linken Seite (Potenz einer Summe) als Summe von Potenzen zu schreiben. Dass die Binomialkoeffizienten dabei auftreten, kann man an Gleichung (1) "erraten": Die Vorfaktoren vor a², ab und b² lauten

1 2 1

und bilden gerade die Zeile des Pascalschen Dreiecks zu n = 2.

Egal welche Lesart man bevorzugt, der binomische Satz stammt nicht aus dem Kontext von Abzählproblemen und sein Beweis kann entweder rein algebraisch oder durch geeignetes Abzählen von Termen erfolgen – wodurch wieder der Zusammenhang zu Abzählproblemen hergestellt wird.

In Abbildung 6 sind zwei Beweise des binomischen Satzes gezeigt:

Ein Beweis mit vollständiger Induktion, in dem nur die Pascalsche Rekursionsformel eingeht, ansonsten werden die Summanden nur neu sortiert.
Ein Beweis durch Abzählen der identischen Summanden, wenn die linke Seite des binomischen Satzes vollständig ausmultipliziert wird.

Abbildung 6: Zwei Beweise des binomischen Satzes in der Form (1). Der erste Beweis erfolgt mit vollständiger Induktion und verwendet die Pascalsche Rekursionsformel. Der zweite Beweis zählt die Summanden ab, wenn die linke Seite von (1) ausmultipliziert wird.

Binomialkoeffizienten und der n-dimensionale Hyperwürfel

Ein Beispiel zur Einführung

In Abbildung 7 sind links die Zeilen des Pascalschen Dreiecks zu n = 0 bis n = 3 gezeigt. Rechts davon sind die n-dimensionalen Würfel mit n = 0, 1, 2, 3 dargestellt, also Punkt, Strecke, Quadrat und Würfel. Dabei sind die Punkte der jeweiligen Objekte farbig gekennzeichnet, nämlich nach folgender Regel, die für den Würfel leichter zu formulieren sind, da die anderen Objekte als Spezialfälle nur besondere Eigenschaften zeigen:

Zuerst werden der Ursprung (0, 0, 0) und der Punkt (1, 1, 1) eingezeichnet und jeder mit einer Farbe versehen (rot und blau).
Ausgehend vom Ursprung kann man sich in jeder der drei Raumdimensionen entlang einer Kante bewegen und erreicht drei Punkte, die orange eingetragen sind.
Bewegt man sich von je einem der Punkte in eine andere Richtung als beim ersten Schritt (wieder entlang einer Kante), so erreicht man einen der drei türkis gezeichneten Punkte.
Jetzt sind alle Eckpunkte des Würfels außer (1, 1, 1) erreicht. Wegen der Symmetrie des Würfels kann man dieses Vorgehen auf verschiedene Arten realisieren, man erhält aber immer vier Farben, mit denen 1, 3, 3, 1 Punkte gekennzeichnet werden.

Für die Dimension n gilt entsprechend:

Man benötigt n+1 Farben.
Die Anzahl der Punkte pro Farbe ist durch die Binomialkoeffizienten der n-ten Zeile des Pascalschen Dreiecks gegeben.

Abbildung 7: Links die ersten vier Zeilen des Pascalschen Dreiecks, rechts die 0- bis 3-dimensionalen Würfel (Punkt, Strecke, Quadrat und Würfel. Die Punkte sind farbig gekennzeichnet und stellen eine Beziehung zu den Binomialkoeffizienten her.

Das Beispiel wirft sofort einige Fragen auf:

Lässt sich die oben beschriebene Vorgehensweise auf beliebige Dimensionen n verallgemeinern?
Wenn ja: wie werden die Punktmengen definiert, deren Anzahlen durch die Binomialkoeffizienten der n-ten Zeile des Pascalschen Dreiecks gegeben sind?
Welche Rolle spielt in dieser Interpretation der Binomialkoeffizienten die Pascalsche Rekursionsformel?

In den folgenden Unterabschnitten werden diese Fragen näher untersucht. Die Charakterisierung der Punktmengen erfolgt mit Hilfe des Hamming-Abstandes. Und die Pascalsche Rekursionsformel wird zu einem Konstruktionsverfahren, mit dem man aus dem n-dimensionalen Würfel den (n+1)-dimensionalen Würfel erhält.

Die Koordinaten der Eckpunkte eines n-dimensionalen Hyperwürfels

In n Dimensionen gibt es n Einheitsvektoren, die das Koordinatensystem aufspannen; jeder dieser Vektor besitzt eine Komponente, die gleich 1 ist, alle anderen Komponenten sind gleich 0:

e₁ = (1, 0, 0, ..., 0)

e₂ = (0, 1, 0, ..., 0)

...

e_n = (0, 0, 0, ..., 1)

Die Kanten des n-dimensionalen Hyperwürfels sind parallel zu diesen n Einheitsvektoren. Er besitzt 2ⁿ Eckpunkte. Die n Koordinaten eines Eckpunktes sind entweder gleich 0 oder 1. Somit kann jeder Eckpunkt des n-dimensionalen Hyperwürfels eindeutig mit einer n-stelligen Dualzahl identifiziert werden; dabei wird die Dualzahl üblicherweise mit führenden Nullen dargestellt.

Das folgende Listing zeigt die Koordinaten der 8 Eckpunkte des dreidimensionalen Würfels in lexikographischer Anordnung; die Koordinaten der Punkte sind wie Dualzahlen dargestellt:

Um die Eckpunkte des n-dimensionalen Hyperwürfels darzustellen, können die Dualzahlen von 0 bis 2ⁿ-1 verwendet werden.

Die lexikographische Anordnung ist nicht geeignet, um die Eckpunkte in Mengen einzuteilen wie es die Färbung der Punkte in Abbildung 7 suggeriert; dazu wird der Hamming-Abstand zweier Dualzahlen eingeführt.

Der Hamming-Abstand zweier Dualzahlen

Abbildung 8 oben zeigt nochmals den dreidimensionalen Würfel mit der Färbung der Eckpunkte wie in Abbildung 7 rechts unten. In Abbildung 8 unten werden die Eckpunkte anders angeordnet; und zwar nicht entsprechend ihrer geometrischen Lage, sondern gemäß der Anordnung im Pascalschen Dreieck:

Ausgehend vom Ursprung (0, 0, 0) erreicht man die orange gefärbten Punkte, indem man sich entlang einer Kante bewegt.
Geht man von einem orangefarbenen Punkt entlang einer anderen Richtung als im ersten Schritt, so erreicht man einen türkisfarbenen Punkt.
Jetzt gibt es nur noch eine Richtung, in die man sich nicht bewegt hat und auf ihr erreicht man den blauen Punkt (1, 1, 1).

Abbildung 8: Oben ist der dreidimensionale Würfel dargestellt, wobei die Eckpunkte wie in Abbildung 7 gefärbt sind. Unten wird der Würfel als Graph dargestellt: Jeder Eckpunkt ist ein Knoten des Graphen. Die Anordnung der Knoten soll jetzt nicht mehr die räumliche Vorstellung des Würfels unterstützen, sondern soll die Abstände der Punkte gleicher Farbe vom Ursprung andeuten.

Betrachtet man die entsprechenden Dualzahlen, kann man leicht das Kriterium formulieren, wie diese vier Punktmengen gebildet werden, die bisher umständlich mit Farben und Richtungen beschrieben wurden:

Der Hamming-Abstand d_H (a, b) zweier Dualzahlen a und b wird definiert durch die Anzahl der Stellen, in denen sich a und b unterscheiden. (Falls die Anzahl der Stellen unterschiedlich ist, wird die kürzere Zahl mit einer geeigneten Anzahl an führenden Nullen dargestellt.)

Somit kann der Abstand d_H (a, b) zweier n-stelliger Dualzahlen a und b nur die Werte 0, 1, ..., n annehmen.

Identifiziert man die Eckpunkte des Würfels mit den Dualzahlen, kann man den Hamming-Abstand auch für die Eckpunkte des n-dimensionalen Würfels definieren. Und die 4 Punktmengen in Abbildung 6 sind die Eckpunkte, die vom Ursprung (0, 0, 0) die Abstände 0, 1, 2, 3 haben.

Es soll hier nicht diskutiert werden, dass der Hamming-Abstand tatsächlich die Eigenschaften einer Metrik erfüllt, also:

d_H (a, b) = 0 gilt genau dann 0, wenn a = b.
Symmetrie: d_H (a, b) = d_H (b, a) für alle Dualzahlen a, b.
Dreiecksungleichung: d_H (a, c) ≤ d_H (a, b) + d_H (b, c) für alle Dualzahlen a, b, c.

Zur Veranschaulichung des Hamming-Abstandes zeigt das folgende Listing nochmals die 8 Eckpunkte des dreidimensionalen Würfels sowie den Hamming-Abstand d_H zu 000:

a:      d(a, 000)
000     0
001     1
010     1 
011     2
100     1 
101     2 
110     2 
111     3

Das Pascalsche Dreieck und der n-dimensionale Hyperwürfel

Mit Hilfe des Hamming-Abstandes lässt sich allgemein formulieren, was in Abbildung 7 für die Dimensionen 0 bis 3 dargestellt wurde, nämlich dass die Binomialkoeffizienten einer Zeile des Pascalschen Dreiecks die Mächtigkeit gewisser Mengen von Eckpunkten des Würfels beschreiben.

Die Aussage lautet allgemein (also für beliebige Dimension):

Die Binomialkoeffizienten "k aus n" der n-ten Zeile des Pascalschen Dreiecks beschreiben die Anzahl der Eckpunkte des n-dimensionalen Hyperwürfels, die vom Ursprung (0, 0, ..., 0) den Hamming-Abstand k besitzen.

Die Symmetrie der Binomialkoeffizienten (Gleichung (1) in Abbildung 2) besagt, dass man anstelle des Ursprungs auch vom Punkt (1, 1, ..., 1) ausgehen kann.

Der Beweis der Aussage kann jetzt durch Abzählen geführt werden, wozu die Eckpunkte wieder mit Dualzahlen identifiziert werden.

Ist k eine ganzen Zahl mit 0 ≤ k ≤ n und P ein Eckpunkt des n-dimensionalen Hyperwürfels mit Hamming-Abstand k von (0, 0, ..., 0), so sind k Koordinaten von P gleich 1 und die anderen n-k Koordinaten sind gleich 0. Um die Anzahl der Eckpunkte P mit derartigen Koordinaten zu berechnen, muss man fragen, wie viele Möglichkeiten es gibt, k von n Stellen mit einer 1 und die anderen Stellen mit einer 0 zu besetzen. Es handelt sich hier um Kombinationen ohne Wiederholungen und es gibt "k aus n" Eckpunkte.

Die Konstruktion des Hyperwürfels

Wenn sich die Eckpunkte des n-dimensionalen Hyperwürfels so einfach charakterisieren lassen, ist es naheliegend nach seiner Veranschaulichung zu fragen und Abbildung 7 für höhere Dimensionen fortzusetzen. Aber es ist klar, dass unsere Anschauung an den dreidimensionalen Raum gebunden ist und man bestenfalls Projektionen des Hyperwürfels in die zweidimensionale Zeichenebene erzeugen kann – ähnlich wie in Abbildung 7 rechts unten der dreidimensionale Würfel in die Zeichenebene projiziert wurde.

Dazu wird in Abbildung 9 ein Verfahren gezeigt, wie man aus einem gegeben n-dimensionalen Würfel einen (n+1)-dimensionalen Würfel konstruieren kann, wobei es vorerst nur für die uns vertrauten Dimensionen n = 0, 1, 2 angewendet wird.

Abbildung 9: Das Verfahren zur Konstruktion eines (n+1)-dimensionalen Würfels aus einem n-dimensionalen Würfel, hier dargestellt für Strecke, Quadrat und Kreis.

1. n = 0 → n = 1:

In Abbildung 1 oben wird gezeigt, wie man aus einem 0-dimensionalen Würfel (schwarzer Punkt) einen 1-dimensionalen Würfel (Strecke in x₁-Richtung mit einem schwarzen und einem roten Punkt) konstruiert. Dazu wird der schwarze Punkt zunächst verdoppelt; der neue rote Punkt ist "hinter" dem schwarzen Punkt sichtbar. Der rote Punkt wird anschließend um die Länge 1 in x₁-Richtung verschoben; der Verschiebungsvektor ist dann die einzige Kante des neuen Würfels.

2. n = 1 → n = 2:

Jetzt geht man von der Strecke aus (1-dimensionaler Würfel) und verdoppelt diese (angedeutet durch die rote Umrandung der schwarzen Punkte). Die Strecke mit den roten Punkten wird in x₂-Richtung um die Länge 1 verschoben; wieder sind die Verschiebungsvektoren neue Kanten des 2-dimensionalen Würfels – also eines Quadrates mit 4 begrenzenden Kanten.

3. n = 2 → n = 3:

Völlig analog geht man jetzt vom Quadrat in der x₁-x₂-Ebene aus, verdoppelt es und verschiebt es in x₃-Richtung. Es entsteht der dreidimensionale Würfel. Dabei stammen 4 Kanten vom ursprünglichen (schwarzen) Quadrat, 4 Kanten vom verdoppelten Quadrat (mit den roten Punkten) sowie 4 Kanten entlang der Verschiebungsvektoren (rot, in x₃-Richtung).

Um die nächste Konstruktion (des 4-dimensionalen Hyperwürfels) besser zu verstehen, muss betont werden, dass der dreidimensionale Würfel in Abbildung 9 perspektivisch dargestellt ist, da man die x₃-Richtung nicht senkrecht zu den anderen beiden Achsen zeichnen kann – unser dreidimensionales Vorstellungsvermögen kann in der Darstellung aber leicht einen räumlichen Körper erkennen.

In Abbildung 10 werden die Konstruktionen aus Abbildung 9 um eine Dimension fortgeführt, wobei der Deutlichkeit halber eine leicht veränderte Farbkonvention eingesetzt wird.

Die neue x₄-Richtung wird jetzt ebenfalls in die x₁-x₂-Ebene projiziert – zur Unterscheidung von x₃ lediglich in einer etwas veränderten Richtung.

Der ursprüngliche dreidimensionale Würfel ist schwarz gezeichnet (sowohl die Eckpunkte als auch die Kanten); die Verdopplung des Würfels ist jetzt nicht mehr dargestellt. Rechts ist sofort das Ergebnis der Verdopplung und Verschiebung zu sehen. Dabei besitzt der verdoppelte Würfel rote Eckpunkte und blaue Kanten. Die Kanten, die durch die Verschiebung neu entstehen, sind wie in Abbildung 9 rot dargestellt

Abbildung 10: Die Konstruktion des Würfels aus Abbildung wird analog übertragen auf die Konstruktion des vierdimensionalen Hyperwürfels aus einem dreidimensionalen Würfel.

Um besser entscheiden zu können, welche Eigenschaften lediglich durch die spezielle Wahl der Projektionsrichtung erscheinen, wird der Hyperwürfel aus Abbildung 10 in der folgenden Abbildung mit einer anderen x₄-Achse dargestellt:

Abbildung 11: Darstellung des vierdimensionalen Hyperwürfels, wobei für die x<sub>4</sub>-Achse eine andere Projektionsrichtung gewählt wird als in Abbildung 10.

Abbildung 11: Darstellung des vierdimensionalen Hyperwürfels, wobei für die x₄-Achse eine andere Projektionsrichtung gewählt wird als in Abbildung 10.

Egal ob man den vierdimensionalen Hyperwürfel in Abbildung 10 0der 11 betrachtet, auf den ersten Blick fällt es schwer die Punkte mit gleichem Hamming-Abstand k vom Ursprung zu identifizieren, um nachzuprüfen, ob ihre Anzahl tatsächlich durch die Binomialkoeffizienten "k aus 4" gegeben ist. Dies soll Abbildung 12 erleichtern. In ihr werden die Würfel nicht entsprechend unserer geometrischen Vorstellung dargestellt, sondern wie in Abbildung 8 unten als Graphen, die Punkte mit gleichem Hamming-Abstand besser kennzeichnen. Genauer werden zuerst zwei Würfel gezeichnet (dies entspricht der Verdopplung und Verschiebung des dreidimensionalen Würfels): einer mit schwarzen Punkten und Kanten, einer mit roten Punkten und blauen Kanten. Verbindet man jetzt die entsprechenden Punkte der beiden dreidimensionalen Würfel durch rote Kanten, so hat man genau die Konstruktion wie in Abbildung 10 beziehungsweise 11 durchgeführt. Das Ergebnis ist der vierdimensionale Hyperwürfel unten in Abbildung 12, der geometrisch noch schwerer zu interpretieren ist als in Abbildung 10 und 12, aber die Punkte mit gleichem Hamming-Abstand vom Ursprung liegen jetzt übereinander und lassen sich leicht abzählen:

1 4 6 4 1.

Abbildung 12: Darstellung des vierdimensionalen Hyperwürfels, in der sich die Punkte mit gleichem Hamming-Abstand vom Ursprung leicht identifizieren lassen.

Wenn man jetzt noch fragt, wie sich die Anzahlen 1 4 6 4 1 für den vierdimensionalen Würfel aus den Anzahlen 1 3 3 1 des dreidimensionalen Würfels zusammensetzen, so erkennt man in Abbildung 12 sofort, dass hier die Pascalsche Rekursionsformel eingeht:

1 = 1 + 0

4 = 3 + 1

6 = 3 + 3

4 = 1 + 3

1 = 0 + 1.

Dabei bezieht sich jeweils der erste Summand auf den schwarzen Würfel und der zweite Summand auf den blauen Würfel.

Die Abbildung 14 unten versucht den vierdimensionalen Hyperwürfel und seine Konstruktion so darzustellen, dass die beiden Ausgangswürfel leicht geometrisch interpretiert werden können und die Mengen von Eckpunkten mit gleichem Hamming-Abstand zum Ursprung gut erkennbar sind (die Koordinaten der Eckpunkte wurden als Dualzahlen notiert). Dazu werden in Abbildung 13 nochmals die beiden dreidimensionalen Würfel gezeigt, aus denen der Hyperwürfel konstruiert wird – hier sind die Koordinaten der Eckpunkte noch in der üblichen geometrischen Notation gezeigt.

Abbildung 13: Darstellung des dreidimensionalen Würfels, die leicht geometrisch interpretiert werden kann und in der Punkte mit gleichem Hamming-Abstand zum Ursprung leicht erkennbar sind.

Abbildung 14: Geometrisch verzerrte Darstellung des vierdimensionalen Hyperwürfels und des Konstruktionsverfahrens, die aber die Punkte mit gleichem Hamming-Abstand zum Ursprung leicht erkennen lässt.

Abzählen der Kanten des n-dimensionalen Würfels

Es gibt zahlreiche Methoden, wie man die Kanten eines n-dimensionalen Hyperwürfels abzählen kann, einige davon sollen hier vorgestellt werden; insbesondere die letzte Methode wird eine wichtige Anwendung des binomischen Satzes liefern.

Aufgabe: Geben Sie eine möglichst einfache Überlegung an, wie man die Anzahl der Eckpunkte beziehungsweise der Kanten eines n-dimensionalen Würfels berechnen kann.

Bezeichnungen

In den folgenden Unterabschnitten werden folgende Bezeichnungen verwendet:

n: Dimension, n ≥ 0.
E(n): Anzahl der Ecken des n-dimensionalen Würfels.
K(n): Anzahl der Kanten des n-dimensionalen Würfels.

Da man die Eckpunkte des n-dimensionalen Würfels mit den Dualzahlen identifizieren kann, gilt: E(n) = 2ⁿ.

Dieses Ergebnis kann man einfacher aus der Konstruktion der Würfel in Abbildung 9 ablesen: Da beim Übergang von n zu n+1 die Anzahl der Eckpunkte verdoppelt wird und E(n = 0) = 1 ist, muss E(n) = 2ⁿ gelten.

Direktes Abzählen der Kanten

Die naheliegende Methode, die Anzahl der Kanten zu bestimmen, besteht darin, sie direkt abzuzählen: Da man von jedem Eckpunkt aus in n Richtungen zu einem anderen Eckpunkt gehen kann und es E(n) Eckpunkte gibt, gibt es n · E(n) Kanten. Weil aber jede Kante zwei Eckpunkte verbindet, wird damit jede Kante doppelt gezählt. Folglich ist:

K(n) = n · E(n) / 2 = n · 2^n-1.

Damit ist das Problem gelöst und die zweite Tabelle in Abbildung 15 zeigt E(n) und K(n) für n = 1, ..., 10.

Abbildung 15: Berechnung der Anzahl der Kanten K(n) beziehungsweise Ecken E(n) eines n-dimensionalen Würfels.

Berechnung der Anzahl der Kanten aus dem Konstruktionsverfahren

Eine typische Methode zur Lösung von Abzählproblemen besteht darin, eine Rekursionsformel aufzustellen, die mit einer Anfangsbedingung eindeutig gelöst werden kann. Das Konstruktionsverfahren aus Abbildung 9 liefert eine derartige Rekursionsformel: Denn der n-dimensionale Würfel wird aus zwei (n-1)-dimensionalen Würfeln aufgebaut, wobei die entsprechenden Eckpunkte dieser beiden Würfeln mit Kanten verbunden werden.

Zählt man die Kanten des n-dimensionale Würfels ab, so erhält man Gleichung (2) in Abbildung 15: Auf der rechten Seite stehen

die Anzahl der Kanten der beiden (n-1)-dimensionalen Würfel (schwarze Kanten in Abbildung 9) und
die Anzahl der Ecken eines (n-1)-dimensionalen Würfels (rote Kanten in Abbildung 9).

Setzt man für E(n-1) = 2^n-1 ein, kann man aus der Rekursionsformel leicht den expliziten Ausdruck für K(n) herleiten.

Aufgabe: Zeigen Sie durch vollständige Induktion, dass Gleichung (2) in Abbildung 15 mit K(0) = 0 von K(n) = n · 2^n-1 gelöst wird.

Berechnung der Anzahl der Kanten mit Hilfe der Binomialkoeffizienten

Die letzte Methode zum Abzählen der Kanten wirkt sehr umständlich, sie liefert aber eine wichtige Einsicht, wie man mit dem binomischen Satz umgeht. Man geht dazu vom Graphen in Abbildung 8 unten aus. Dieser Graph beschreibt den dreidimensionalen Würfel. Man muss sich jetzt nur fragen, wie der entsprechende Graph für den n-dimensionalen Würfel aussieht und wie man mit ihm die Kanten zählen kann.

Ganz links wird der Ursprung als Eckpunkt gewählt, nach rechts werden die Eckpunkte mit Hamming-Abstand 1, 2, ... aufgetragen, deren Anzahl durch die Binomialkoeffizienten "k aus n", k = 1, 2, ..., n berechnet wird.

Vom Ursprung aus kann man sich in n Richtungen bewegen, daher gehen vom Ursprung n Kanten aus.
Befindet man sich auf einem Eckpunkt mit Hamming-Abstand 1 vom Ursprung, kann man sich nur noch in (n-1) Richtungen bewegen, um zu einem Punkt mit Hamming-Abstand 2 vom Ursprung zu gelangen. Daher gehen von diesen Eckpunkten (n-1) · "k aus n" Kanten aus.
Und so weiter.
Befindet man sich auf einem Eckpunkt mit Hamming-Abstand (n-1) vom Ursprung, kann man sich nur noch in einer Richtung bewegen; von diesen Eckpunkten gehen also n Kanten aus.

Um die Anzahl aller Kanten des Würfels zu berechnen, muss man die so berechneten Kanten addieren. Verwendet man jetzt noch die Symmetrie der Binomialkoeffizienten, so liefert die soeben beschriebene Summen Gleichung (3) in Abbildung 15.

Eine derartige Summe ist bisher nicht aufgetreten; in Abbildung 15 wird gezeigt, wie man sie mit Hilfe des binomischen Satzes berechnet: Dazu werden die Polynome im binomischen Satz links und rechts nach x differenziert (Gleichung (5) in Abbildung 15). Anschließend wird x = 1 gesetzt (Gleichung (6) in Abbildung 15), wodurch man das bereits bekannte Ergebnis erhält.

R-Skripte

Berechnung der Binomialkoeffizienten und der Zeilen des Pascalschen Dreiecks

Die folgende R-Funktion pascal() erzeugt zu gegebenem n iterativ n + 1 Zeilen des Pascalschen Dreiecks. Dabei ist folgende Konvention zu beachten:

Die oberste Zeile des Pascalschen Dreiecks wird üblicherweise die nullte Zeile bezeichnet, da hier der Binomialkoeffizient zu n = 0 berechnet wird (siehe Abbildung 3).
In R beginnt die Zählung der Komponenten eines Vektors (oder einer Liste) stets mit 1. Im folgenden Skript werden die Zeilen des Pascalschen Dreiecks berechnet und jede Zeile als Komponente einer Liste abgespeichert; daher ist die oberste Zeile des Pascalschen Dreiecks hier die erste Komponente der Liste.

Wird die Funktion pascal() mit dem Eingabewert n aufgerufen, so ist der Rückgabewert eine Liste mit n+1 Komponenten, nämlich die nullte bis n-te Zeile des Pascalschen Dreiecks. Berechnet werden die Binomialkoeffizienten mit Hilfe der Rekursionsformel, die entsprechende Zeile im folgenden Listing dazu ist Zeile 7, die unten näher erklärt wird.

pascal <- function(n){
  bc <- vector(mode = "list", length = n + 1)
  bc[[1]] <- 1
  bc[[2]] <- c(1, 1)
  
  for(i in (2:n)){
    bc[[i + 1]] <- c(1, bc[[i]][-i] + bc[[i]][-1], 1)
  }
  return(bc)
}

str(pascal(n = 5))
# List of 6
# $ : num 1
# $ : num [1:2] 1 1
# $ : num [1:3] 1 2 1
# $ : num [1:4] 1 3 3 1
# $ : num [1:5] 1 4 6 4 1
# $ : num [1:6] 1 5 10 10 5 1

Zur Erklärung:

Zeile 2: Es wird eine Liste bc (binomial coefficients) mit n+1 Komponenten vorbereitet, die später zurückgegeben wird. Jede Komponente der Liste ist ein Vektor mit je einer Zeile des Pascalschen Dreiecks (dies ist vermutlich leichter am Test in Zeile 12 und der zugehörigen Ausgabe zu verstehen).

Zeile 3: Die erste Komponente der Liste bc ist die nullte Zeile des Pascalschen Dreiecks, also ein Vektor der Länge 1 mit dem Zahlenwert 1 (siehe auch die Ausgabe in Zeile 14).

Zeile 4: Die zweite Komponente der Liste bc ist die erste Zeile des Pascalschen Dreiecks, also ein Vektor der Länge 2 mit den Zahlenwerten (1, 1), siehe Zeile 15.

Zeile 6 bis 8: In der for-Schleife werden die weiteren Komponenten der Liste bc gesetzt. Die Anweisung in Zeile 7 vermag zunächst verwirren. Man kann sie leicht für i = 2 durchspielen: bc[[2]] stimmt mit dem Vektor (1, 1) überein. Durch bc[[i]][-i] wird die zweite Komponente des Vektors entfernt, es bleibt die Zahl 1. Entsprechend wird mit bc[[i]][-1] die erste Komponente des Vektors entfernt, es bleibt ebenfalls die 1. Die Summe bc[[i]][-i] + bc[[i]][-1] ergibt 2; somit wird auf der rechten Seite von Zeile 7 insgesamt der Vektor (1, 2, 1) gebildet.

Man kann die Anweisung c(1, bc[[i]][-i] + bc[[i]][-1], 1) daher so lesen: Es wird ein Vektor gebildet, dessen erste und letzte Komponente gleich 1 gesetzt werden, die inneren Komponenten werden aus der Pascalschen Rekursionsformel aus den Binomialkoeffizienten der vorhergehenden Zeile berechnet.

Aufgabe: Spielen Sie die Anweisung bc[[i + 1]] <- c(1, bc[[i]][-i] + bc[[i]][-1], 1) für i = 3 durch.

Zeile 9: Die Liste bc wird zurückgegeben.

Zeile 12: Zum Test der Aufruf von pascal() mit n = 5.

Man beachte, dass man sowohl für n = 0 und n = 1 die ersten beiden Zeilen des Pascalschen Dreiecks erhält – hier lässt sich die Funktion verbessern.

Aufgabe: Die Funktion pascal(n) erzeugt das Pascalsche Dreieck mit n+1 Zeilen, wobei jede Zeile in einem Vektor abgespeichert wird und diese Zeilen zu einer Liste zusammengefasst werden. Für große n wird dann auch ein sehr großes Objekt erzeugt. Möchte man nur eine Zeile des Pascalschen Dreiecks weiterverarbeiten, wird hier sehr viel Speicherplatz verschwendet.

Schreiben Sie die Funktion pascal() zu einer Funktion um, die als Eingabewert eine natürliche Zahl n erhält und die (n+1)-te Zeile des Pascalschen Dreiecks als Vektor zurückgibt. Die 0-te bis n-te Zeile des Pascalschen Dreiecks sollen zwar wie in pascal() berechnet werden (also mit der Vorgehensweise, die in der Schleife in Zeile 6 bis 8 angewendet wird), aber nicht gespeichert werden.

Darstellung des n-dimensionalen Würfels als Graph

Grober Überblick

Unten wird eine Funktion plotHypercube() entwickelt, mit deren Hilfe ein n-dimensionaler Würfel als Graph dargestellt werden kann (in den Abbildungen unterhalb des Quelltextes sind die Ergebnisse zu sehen, Abbildung ?? bis ??). Dazu wird die Bibliothek igraph eingesetzt, die zahlreiche Funktionalitäten zum Umgang mit Graphen bereitstellt.

Die Aufgaben zum Erstellen eines Plots werden auf 4 Funktionen verteilt:

adj(dim)
is.neighbour(x, y, dim)
as.graph(adj)
plotHypercube(n)

Die Funktion adj(dim) berechnet die Adjazenz-Matrix des Graphen, der den Hyperwürfel beschreibt; der Eingabewert dim ist die Dimension (die bisher mit n bezeichnet wurde).

Die Adjazenz-Matrix A beschreibt die "Nachbarschaft" der Eckpunkte des Würfels. Sie ist eine quadratische, symmetrische Matrix und besitzt 2^dim Zeilen (und Spalten), also pro Eckpunkt eine Zeile (und Spalte). Das Matrix-Element A_ij ist gleich 1, wenn die Eckpunkte i und j benachbart sind, andernfalls gleich 0; benachbart heißt hier, dass sie durch eine Kante verbunden sind – mit Hilfe des Hamming-Abstandes ausgedrückt: d_H (i, j) = 1.

Um die Adjazenz-Matrix aufzubauen, wird eine weitere Funktion is.neighbour() implementiert, die feststellt, ob zwei Eckpunkte benachbart sind (im soeben beschriebenen Sinn).

Die Funktion as.graph(adj) erzeugt aus der Adjazenz-Matrix einen Graphen wie er in der Bibliothek igraph verwendet wird; dabei werden noch weitere Eigenschaften gesetzt (wie Farben der Eckpunkte). Der Plot des Graphen wird von der Funktion as.graph(adj) erstellt

Zuletzt wird eine plotHypercube(n) implementiert, die als Eingabewert die Dimension n erhält und lediglich as.graph() aufruft. Sie ist also nur ein Wrapper, der dem Nutzer verbirgt, wie intern aus der gegebenen Dimension n eine Adjazenz-Matrix und ein igraph-Objekt erzeugt wird.

Die Implementierung der Funktionen

1. Die Funktion is.neighbour(x, y, dim) :

Die Funktion is.neighbour(x, y, dim) erhält als Eingabewerte zwei Dualzahlen x und y, die als Vektoren übergeben werden, und die Dimension dim. Der Rückgabewert ist ein logischer Wert, also entweder TRUE oder FALSE.

is.neighbour <- function(x, y, dim){
  stopifnot( dim > 1, identical(length(x), length(y)), identical(dim, length(x)) )
  result <- FALSE
  if( identical(sum(x == y), as.integer(dim - 1)) ){
    result <- TRUE
  }
  return(result)
}

Zur Erklärung:

Zeile 2: Es werden zuerst einige Prüfungen der Eingabewerte vorgenommen (die Dimension muss größer als 1 sein, die Vektoren x und y müssen gleiche Länge haben und die Länge der Vektoren muss mit der Dimension dim übereinstimmen). Es wird nicht geprüft, ob x und y tatsächlich Dualzahlen sind.

Zeile 4: Um zu prüfen, ob die Dualzahlen x und y benachbart sind, wird zuerst festgestellt, für welche Komponenten x == y gilt. Die Anzahl dieser Komponenten wird mit sum(x == y) berechnet und mit as.integer(dim - 1) verglichen (Übereinstimmung bedeutet, dass sich x und y in einer Komponente unterscheiden und somi benachbart sind).

2. Die Funktion adj(dim) :

Eingabewert ist die Dimension, Rückgabewert die Adjazenz-Matrix für den Hyperwürfel zur gegebenen Dimension.

adj <- function(dim){
  stopifnot(dim > 1)
  
  lst.01 <- vector(mode = "list", length = 1)
  lst.01[[1]] <- c(0L, 1L)
  lst <- rep(x = lst.01, times = dim)
  
  dualNumbers <- as.matrix( expand.grid(lst) )
  
  adj.length <- 2^dim
  ADJ <- diag(x = 0L, nrow = adj.length)
  
  for(i in (1:adj.length)){
    for(j in (1:adj.length)){
      if( is.neighbour(x = dualNumbers[i, ], y = dualNumbers[j, ], dim = as.integer(dim)) ){
        ADJ[i, j] <- 1
      }
    }    # Ende for(j)
  }   # Ende for(i)
  return(ADJ)
}

Zur Erklärung:

Zeile 2: Es wird wieder geprüft, ob die Dimension dim größer als 1 ist. Weitere Prüfungen der Eingabewerte sind hier nicht nötig.

Zeile 4 bis 8: Zur gegebenen Dimension dim müssen alle Dualzahlen der Länge dim berechnet werden. Da es nicht auf die Reihenfolge der Dualzahlen ankommt, wird hier ein sehr einfacher Ansatz gewählt: Es wird eine Liste lst gebildet, die dim-mal den Vektor (0, 1) enthält. Dazu wird der Vektor (0, 1) in eine Liste verpackt (Zeile 4 und 5) und mit rep() dim-mal wiederholt (Zeile 6). Die Funktion expand.grid() in Zeile 8erhält nun als Eingabewert diese Liste lst mit dim Komponenten. Es werden dann alle möglichen Kombinationen der Länge dim gebildet, wobei jedes Element der Kombination aus der entsprechenden Komponente der Liste gewählt wird.

Zum besseren Verständnis zeigt das folgende Listing die Struktur der Liste lst und die Ausgabe der Dualzahlen dualNumbers, wobei die Funktion adj() mit dim = 3 aufgerufen wurde (dazu wurden entsprechende debug-Ausgaben in die Funktion eingebaut):

str(lst)
# List of 3
# $ : int [1:2] 0 1
# $ : int [1:2] 0 1
# $ : int [1:2] 0 1

print(dualNumbers)
#     Var1 Var2 Var3
# [1,]    0    0    0
# [2,]    1    0    0
# [3,]    0    1    0
# [4,]    1    1    0
# [5,]    0    0    1
# [6,]    1    0    1
# [7,]    0    1    1
# [8,]    1    1    1

Zeile 10 und 11: Die Adjazenz-Matrix wird vorbereitet: Sie ist eine quadratische Matrix mit 2^dim Zeilen (und Spalten), da für jede Dualzahl eine Zeile benötigt wird.

Zeile 13 bis 19: In den verschachtelten for-Schleifen wird für jede Dualzahl festgestellt, welche Dualzahl mit ihr benachbart ist. Dazu wird die Funktion is.neighbour() eingesetzt.

Zeile 20: Rückgabewert ist die Adjazenz-Matrix.

Aufgabe: Da die Adjazenz-Matrix symmetrisch ist, kann man die for-Schleifen auch über weniger Elemente iterieren lassen und das symmetrisch gelegene Matrix-Element im Schleifenkörper setzen. Implementieren Sie diese schnellere Version der for-Schleifen.

3. Die Funktion as.graph <- function(adj) :

Eingabewerte sind die Adjazenz-Matrix adj und ein logischer Wert ret, der angibt, ob das erzeugte igraph-Objekt zurückgegeben werden soll; die Funktion besitzt keinen Rückgabewert. Sie erzeugt ein igraph-Objekt und erstellt den Plot des Graphen.

as.graph <- function(adj, ret = FALSE){
  N <- nrow(adj)    # Anzahl der Knoten
  dim <- log2(N)    # Dimension
  
  # Farben der Knoten vorbereiten:
  vert.cols <- c()

  # Farbpalette:
  colors <- heat.colors(dim + 1)
  
  # Farben der Knoten setzen:
  for(i in (0:dim)){
    vert.cols <- append( x = vert.cols, 
                        values = rep( colors[i+1], times = choose(n = dim, k = i) ) )
  }
  # Farbe der Umrandung der Knoten:
  vert.frame.cols <- vert.cols
  vert.frame.cols[1] <- "black"
  vert.frame.cols[N] <- "black"

  # Graph aus Adjazenz-Matrix erzeugen
  g <- graph_from_adjacency_matrix(adjmatrix = adj, mode = "undirected")
  
  # alternative Layouts
  # l_fr <- layout_with_fr(g)    # default
  # l_circle <- layout_in_circle(g)   # auf Kreis: besser geeignet zum Abzählen der Knoten
  # l_sphere <- layout_on_sphere(g)   # erst für dim > 4 sinnvoll
  
  # Plot des Graphen:
  plot(g, vertex.color = vert.cols, vertex.frame.color = vert.frame.cols, 
       vertex.size = 8, edge.width = 1, 
       frame = TRUE, main = paste0("dim = ", dim) )
  # mit Angabe eines Layout (hier l_sphere)
  # plot(g, vertex.color = vert.cols, vertex.size = 8, edge.width = 1, 
  #      frame = TRUE, main = paste0("dim = ", dim), layout = l_sphere )
  
  if(ret){
    return(g)
  } else {
    return()
  }
}

Zeile 2 und 3: Da nur die Adjazenz-Matrix gegeben ist, muss man aus ihr zuerst die Anzahl der Knoten und die Dimension des Hyperwürfels berechnen.

Zeile 22: Das igraph-Objekt g wird erzeugt; dazu wird die Funktion graph_from_adjacency_matrix(adjmatrix) eingesetzt, der die Adjazenz-Matrix übergeben wird.

Zeile 30 bis 32: Die eigentliche Aufgabe der Funktion as.graph() besteht darin, den Graphen zu plotten. Dies geschieht mit der Funktion plot(), der als erstes Argument das igraph-Objekt g übergeben wird; daher wird die plot()-Funktion für igraph-Objekte aufgerufen. Die weiteren Argumente beziehen sich auf die Farben der Knoten und weitere Konfigurationen des Plots.

Zeile 37 bis 41: Je nachdem wie die Funktion as.graph() eingesetzt werden soll, kann das igraph-Objekt g zurückgegeben werden oder nicht; dies hängt vom Eingabewert ret ab.

Im Quelltext sind (auskommentiert) weitere Layouts angegeben, um die Knoten des Graphen anders anzuordnen. Weitere Details dazu sind us der Dokumentation zu igraph zu entnehmen.

4. Die Funktion plotHypercube(n = 3) :

Die Fun k-1 plotHypercube() ist lediglich ein Wrapper, um die Implementierungen vor dem Nutzer zu verbergen; sie wird mit der Dimension n aufgerufen. Die Implementierung sorgt dafür, dass die zugehörige Adjazenz-Matrix erzeugt und ein Plot des Hyperwürfels erzeugt wird.

plotHypercube <- function(n = 3){
  as.graph(adj = adj(dim = n))
}

Beispiele für Graphen

Das folgende Skript setzt den Wrapper plotHypercube() ein, um die (Hyper)-würfel zu den Dimensionen 3, 4 und 5 zu plotten (siehe Abbildungen 16 bis 18). Für Abbildung 19 wurde der Quelltext von as.graph() abgeändert, um die Knoten kreisförmig anzuordnen mit layout = l_sphere .

# dreidimensionaler Würfel:
plotHypercube()
# vierdimensionaler Würfel
plotHypercube(n = 4)
# fünfdimensionaler Würfel:
plotHypercube(n = 5)

Der Ursprung (0, ..., 0) und der gegenüberliegende Eckpunkt (1, ..., 1) lassen sich in den Abbildungen an der schwarzen Umrandung des Knotens erkennen. Punkte mit gleichem Hamming-Abstand zum Ursprung sind jeweils gleich gefärbt – bei höheren Dimensionen sind allerdings die Kontraste nur noch sehr schwach, so dass sie schwer zu erkennen sind.

Abbildung 16: Der dreidimensionale Würfel wie er mit dem default-Layout für Graphen im Paket igraph erzeugt wird.

Abbildung 17: Analog zu Abbildung 16 der vierdimensionale Hyperwürfel.

Abbildung 18: Analog zu Abbildung 16 der fünfdimensionale Hyperwürfel.

Abbildung 19: Der fünfdimensionale Hyperwürfel mit einem Layout, das die Knoten auf einer Kugel anordnet.