Online-Bibliothek

Combinationslehre

[290] Combinationslehre (Ars combinatoria, Combinatorik, Syntaktik, Math.), die Wissenschaft von den Gesetzen der Zusammenstellung gegebener Dinge (Elemente), so daß keine unter einer gegebenen Bedingung mögliche Zusammenstellung weder fehlt, noch wiederholt vorkommt. Zur Bezeichnung der Elemente, die ganz beliebig sind, wählt man Ziffern u. kleine lateinische Buchstaben, weil diese die geläufigsten sind u. weil man ihre Aufeinanderfolge kennt. Bei der Zusammenstellung dieser Elemente abstrahirt man nun gänzlich davon, ob siewirklich auf irgend eine Art, z.B. durch Multiplication, verknüpft werden sollen; man berücksichtigt vielmehr nur das unmittelbare Folgen der Elemente nach einander u. bezeichnet dies beim Schreiben durch Nebeneinandersetzen ohne zwischentretende Zeichen. Gleiche Elemente werden natürlich mit denselben Zeichen angedeutet, die man wohl auch, um das wiederholte Schreiben zu ersparen, mit einem Exponenten behaftet, den man in diesem Falle Wiederholungsexponenten nennt. Der Inbegriff mehrerer zusammengestellter Elemente heißt eine Form od. eine Complexion, die wohlgeordnet ist, wenn die Elemente in der natürlichen Ordnung auf einander folgen, z.B. 01234; sofern eine Complexion gegeben ist, um andere daraus herzuleiten, nennt man sie Zeiger (Index). Die Complexionen müssen der Übersicht wegen nach bestimmten Regeln geordnet werden, u. zwar entweder a) lexikographisch, wenn man sie ohne Berücksichtigung der Anzahl ihrer Elemente so auf einander folgen läßt, wie sie in einem Lexikon stehen würden, z.B. sind die Complexionen badc, abc, aae, da, a, c, bc auf diese Weise lexikographisch geordnet: a, aac, abc, badc, bc, c, da; od. b) arithmographisch, wenn man mit Berücksichtigung der Anzahl ihrer Elemente die, welche aus einem bestehen, zuerst schreibt, die welche zwei Elemente enthalten, folgen läßt etc. u. jede dieser Klassen, die bezüglich die 1., 2., 3. etc. Klasse genannt werden, nun noch lexikographisch ordnet; z.B. die vorigen Complexionen sind so arithmographisch geordnet: a, c, bc, da, aae, abc, bade; bei Vergleichung zweier Formen nennt man hiernach diejenige in lexikographischem Sinne höher, in welcher früher als in der anderen ein höheres Element gesetzt worden ist, z.B. ist acbd höher als abcd, in arithmographischem Sinne aber diejenige, welche aus einer größeren Anzahl von Elementen besteht. Es gibt drei combinatorische Operationen: A) Permutiren (Versetzen) besteht in allen möglichen Versetzungen der Elemente eines gegebenen Zeigers. Jede durch Permutiren erhaltene Complexion heißt eine Permutation. Man unterscheidet: a) Permutationen ohne Wiederholung, wo in einer Complexion jedes Element nur einmal vorkommt; Beispiele: vom Zeiger abcd P (abcd) =

Man stellt alle möglichen Permutationen einer gegebenen Zahl von Elementen dar, indem man diese erst wohlgeordnet hinschreibt, dann von rechts nach links gehend das erste Element aufsucht, welches niedriger ist, als das rechts neben ihm stehende, dasselbe mit dem nächst höheren derjenigen Elemente vertauscht, welche überhaupt noch rechts von ihm stehen, dann die übrigen Elemente rechts gut geordnet setzt, die links aber unberührt läßt; so folgt z.B. auf cadb, cbad; b) Permutationen mit Wiederholung, wo in einer Complexion der Zeiger mehrmals vorkommen kann, so vom Zeiger aabcc P' (aabcc) =

[290] In a) ist die Anzahl (num od. Z) der Permutationen (P), wenn der Zeiger m Elemente hat, 1. 2. 3_.... m, was man in Zeichen so ausdrückt: num P (^m) = m. (m – 1 (m – 2)_.... 2. 1:

P' (m = μ + ν + π + ...) heißt nämlich Permutation mit Wiederholung (') eines Zeigers, der m Elemente hat, unter denen μ gleiche Elemente a, ν gleiche Elemente b u.s.f. vorkommen. B) Combiniren (Verbinden) heißt von gegebenen Elementen eine gewisse Anzahl so oft als möglich nehmen, so daß in keiner Zusammenstellung durchaus dieselben Dinge wie in einer anderen vorkommen, d.h. daß alle Zusammenstellungen materiell verschieden sind. Jede hierdurch erhaltene Zusammenstellung heißt eine Combination. Alle Combinationen der 1., 2., 3. u. 4. Klasse heißen beziehungsweise Unionen, Binionen, Ternionen, Quaternionen etc., oft auch von der 2. an: Amben, Ternen, Quaternen etc. Man unterscheidet ebenfalls: a) Combinationen ohne Wiederholung (C). Beispiel: C (a, b, c, d); der Zeiger selbst enthält die Combinationen 1. Klasse; 2. Klasse ab, ac, ad 3. Klasse abc, abd

4. Klasse abcd; b) Combinationen mit Wiederholung (C'). Beispiel: C' (a, b, c) die Verbindungen von 2,3 etc. Elementen zur 2., 3. etc. Klasse, wobei jedes Element mit sich u. allen folgenden, mit Weglassung aller Permutationen, zusammengestellt wird:

In a) ist die Anzahl der Combinationen zur nten Klasse von m Elementen:

in b) dagegen unter denselben Voraussetzungen:

n, welches die Klassen angibt, heißt Klassenexponent. Es gibt auch Combinationen mit Wiederholung zu bestimmten Summen. In diesem Falle sind die Elemente Zahlen, deren Summen eine vorgeschriebene Größe haben. Es sind hier wieder 2 Fälle zu unterscheiden: aa) der Zeiger ist bestimmt, z.B. Combinationen mit Wiederholung zur 5. Klasse u. Summe 7 vom Zeiger (0, 1, 2,3)

bb) der Zeiger ist unbestimmt, die übrigen Voraussetzungen dieselben, dann ist:

Die 7, welche die bestimmte Summe angibt u. über das C' gesetzt wird, heißt der Summenexponent. C) Variiren, ist eine Verbindung der beiden genannten Operationen, indem man erst alle möglichen Combinationen einer gegebenen Anzahl von Elementen aufsucht u. nachher jede Combination permutirt. Die so erhaltenen Zusammenstellungen heißen Variationen. Man unterscheidet hier ebenfalls: a) Variationen ohne Wiederholung (V). Beispiel: V (a, b, c, d) = 1. Klasse a b c d;

die vierte Klasse stimmt genau mit den oben angeführten Permutationen ohne Wiederholung vom Zeiger abcd überein. b) Variationen mit Wiederholung (V'). Beispiel: V' (a, b, c) =

etc. Unsere dekadischen Zahlen sind Variationen mit Wiederholung aus den 10 Ziffern 0–9 bis zur unendlichen Klasse fortgesetzt. Den vorigen Bezeichnungen analog, hat man für

a) num V^(m)_n = m (m – 1)_... (m – n + 1) u. für b) num V'^(m)_n = m. Auch hier lassen sich, wenn Zahlen die Elemente sind, Variationen mit Wiederholung zu bestimmten Summen bilden u. zwar aa) mit bestimmtem Zeiger:

V⁵⁽³⁾₄ (0,1,2), d.h. Variationen mit Wiederholung der 4. Klasse aus den 3 Elementen 0, 1, 2 mit der

[291] bb) mit unbestimmtem Zeiger:

Beim Permutiren wird also nur die Ordnung der Elemente, beim Combiniren der Gehalt u. beim Variiren Beides verändert. Man unterscheidet bei den 3 Operationen einen construirenden Theil, wo verlangt wird, alle möglichen Complexionen von den verlangten Eigenschaften darzustellen, u. einen rechnenden Theil, wo nur anzugeben ist, wie viel Permutationen, Combinationen od. Variationen unter gegebenen Bedingungen zu erwarten sind. Was den construirenden Theil anlangt, so ist die einfache Regel zur Bildung von Permutationen ohne Wiederholung oben mitgetheilt; auch für die übrigen Operationen beruhen die Regeln auf Beobachtung einer gewissen Ordnung, in welcher man allmälig die Elemente zu den einzelnen Complexionen zusammenfügt, so daß die daraus hervorgehenden Formen in Absicht ihrer Aufeinanderfolge eine in sich selbst erkennbare Gesetzmäßigkeit beobachten. Diese für die einzelnen Fälle häufig nicht anders als mit den Worten auseinander zu setzenden Regeln gehen im Allgemeinen davon aus, daß man zuerst, wenn unter den verlangten Complexionen solche vorkommen, die sich durch die Zahl der Elemente unterscheiden, diesen Umstand zu einem vorläufigen Unterscheidungsgrund für eine Eintheilung in Klassen benutzt, innerhalb jeder Klasse aber bei Besetzung der successiven Stellen lexikographisch verfährt. Etwas abweichend hiervon ist ein zweites Verfahren, das sogenannte involutorische, nach welchem man z.B. bei der Ableitung der Permutationen von 4 Elementen damit beginnt, die zwei letzten allein zu permutiren, darauf das drittletzte vorn an jeder der gefundenen Permutationen anfügt, sodann dasselbe auch mit jedem folgenden vertauscht u. die übrigen aufs neue permutirt, endlich das erste Element vor jede der Complexionen dritter Klasse setzt u. auf gleiche Weise wie vorhin verfährt. Ein analoges Verfahren gibt es für die Ableitung der Combinationen u. Variationen; involutorisch heißt es, aber, weil dabei z.B. die Entwickelung der Permutationen für 4 Elemente die für 3 u. 2 Elemente abgesondert mit einschließt. Jeder solche Inbegriff der niederen Complexionen heißt eine Involution. Die Anwendungen der C. auf die Mathematik u. das Leben sind höchst mannichfaltig. Wir combiniren Laute, wenn wir sprechen, Begriffe, wenn wir urtheilen, u. Urtheile, wenn wir schließen. Sie läßt sich auf Stoffe, Farben, Töne, Klänge (Orgelregister), Muster etc. sogar auf Speisen anwenden. (Vgl. Semler, Versuche über die combinatorische Methode, Dresd. 1811.) Am wichtigsten jedoch ist sie für die gesammte Analysis, wo es, wie bei allem Vorhergenannten vorzugsweise darauf ankommt, gewisse combinatorische Arbeiten wirklich zu verrichten, u. für die Wahrscheinlichkeitsrechnung (s.d.), welche mehr der Anzahl gewisser Zusammenstellungen bedarf. – Im Alterthum findet sich keine Spur von dieser Wissenschaft. Der erste bekannte Versuch ist von I. von Buteo (1559), welcher die mit 4 Würfeln möglichen Würfe darstellte u. alle Combinationen der 4 ersten Klassen von 6 Elementen untersuchte. Ausführlicher behandelte sie Vieta (1615); dieser u. noch mehr Harriot (1621) wandte sie auf die Algebra an; Pascal u. Fermat auf Spiele; Mersenne auf die Töne; Guldin berechnete die Menge der Wörter, die sich aus 23 Buchstaben bilden lassen. Ihren vollen Werth erkannte erst Leibnitz. Er wollte sie auch anwenden, philosophische Wahrheiten aufzufinden etc., hat es aber nie ausgeführt. Nach ihm bildeten sie weiter aus Wallis, Jac. Bernoulli u. Euler. Hindenburg, der eigentliche Erfinder der combinatorischen Analysis, gab zuerst, da seine Vorgänger sich fast ausschließlich auf die Bestimmung der Anzahl der in gewissen Fällen möglichen Zusammenstellungen beschränkt hatten, einfache Regeln für die wirkliche Darstellung derselben. Kramp, Kästner u. Lagrange waren viele Jahre lang die Einzigen, die seine Entdeckung würdigten. Bei den Franzosen hat die C. bis heute noch, ihrer Zeichen wegen, wenig Eingang gefunden. In Deutschland bearbeiteten sie mit großem Erfolge in neuerer Zeit Pfaff, Eschenbach, Rothe, Prasse u. A. Vgl. Stahl, Einleitung in die C., 1800; Weingärtner, Lehrbuch der combinatorischen Analysis, 1800–1801, 2 Thle.; Thibaut, Analysis, Gött. 1830; Spehr, Vollständiger Lehrbegriff der reinen C., mit Anwendung auf Analysis u. Wahrscheinlichkeitsrechnung, Braunschw. 1824; Eytelwein, Grundlehren der höheren Analysis, Berl. 1825, 2 Bde.