Auf Klassen reihenfolgenlose Anordnungen

18.05.2022, 02:55

Finn_

Auf Klassen reihenfolgenlose Anordnungen

Die Zahl $\begin{eqnarray*} \frac{n!}{(n-k)!} \end{eqnarray*}$ ist bekanntlich die Anzahl der injektiven Abbildungen $\begin{eqnarray*} X\to Y \end{eqnarray*}$ mit $\begin{eqnarray*} |X|=k \end{eqnarray*}$ und $\begin{eqnarray*} |Y|=n. \end{eqnarray*}$
Dies ist die Anzahl der Anordnungen von $\begin{eqnarray*} k \end{eqnarray*}$ Elementen aus $\begin{eqnarray*} n. \end{eqnarray*}$ Man bezeichnet eine solche Anordnung üblicherweise als Variation.

Spielt die Reihenfolge der Elemente von $\begin{eqnarray*} X \end{eqnarray*}$ dabei keine Rolle, ergeben sich stattdessen $\begin{eqnarray*} \binom{n}{k} \end{eqnarray*}$ Möglichkeiten.

Sei nun eine Zerlegung $\begin{eqnarray*} \textstyle X = \bigcup_{i=1}^m X_i \end{eqnarray*}$ in paarweise disjunkte $\begin{eqnarray*} X_i \end{eqnarray*}$ mit $\begin{eqnarray*} |X_i|=k_i \end{eqnarray*}$ gegeben. Wie groß ist die Anzahl der injektiven Abbildungen $\begin{eqnarray*} X\to Y, \end{eqnarray*}$ wobei die Reihenfolge der Elemente nicht mehr auf ganz $\begin{eqnarray*} X \end{eqnarray*}$ , sondern nur noch auf der jeweiligen Klasse $\begin{eqnarray*} X_i \end{eqnarray*}$ keine Rolle spielt?

18.05.2022, 07:18

HAL 9000

Auf diesen Beitrag antworten »

@Finn

Du weißt schon, dass du besser in einem der drei Threads

Mathe-Marathon Schule
Übergangs-Marathon Mathematik
Mathe-Marathon Uni

posten solltest, wenn du auf eine dir interessant vorkommende Problemstellung stößt, deren Lösung du aber bereits kennst?

18.05.2022, 20:30

Finn_

Auf diesen Beitrag antworten »

Es handelt sich eigentlich nicht um eine als Herausforderung gestellte Aufgabe, sondern um eine allgemeine Erwägung zur Schaffung von mehr Klarheit. Dann möchte ich nun voranschreiten und meine Ausführungen in den kühleren Abendstunden darlegen. Der Ansatz meiner Methodik ist derselbe wie der in 10 Buchstaben aus doppeltem Alphabet beschriebene.

Das Vergessen der Reihenfolge auf der jeweiligen Klasse geschieht, indem man zwei Injektionen identifiziert, wenn die eine durch Permutation der Elemente der Klasse aus der anderen hervorgeht. Die Ansammlung aller auf $\begin{eqnarray*} X_i \end{eqnarray*}$ eingeschränkten Permutationen konstituiert die symmetrische Gruppe $\begin{eqnarray*} S(X_i). \end{eqnarray*}$ Sind sämtliche Elemente außerhalb von $\begin{eqnarray*} X_i \end{eqnarray*}$ Fixpunkte, bildet $\begin{eqnarray*} S(X_i) \end{eqnarray*}$ in diesem Sinne eine Untergruppe der symmetrischen Gruppe $\begin{eqnarray*} S(X) \end{eqnarray*}$ des gesamten Definitionsbereichs $\begin{eqnarray*} X. \end{eqnarray*}$ Bildet man nun das Erzeugnis $\begin{eqnarray*} \textstyle G=\langle\bigcup_{i=1}^m S(X_i)\rangle, \end{eqnarray*}$ also die Menge der Verkettungen frei gewählter Permutationen, entsteht abermals eine Untergruppe $\begin{eqnarray*} G\le S(X). \end{eqnarray*}$

Weil eine Permutation auf der jeweiligen Klasse unabhängig von der Außenwelt festlegbar ist, findet sich für die Größe der Untergruppe die Faktorisierung

$\begin{eqnarray*} |G| = \prod_{i=1}^m |S(X_i)| = \prod_{i=1}^m |X_i|! = \prod_{i=1}^m k_i!. \end{eqnarray*}$

Die Identifizierung ist ferner eine Äquivalenzrelation

$\begin{eqnarray*} f\sim g\iff \exists\pi\in G\colon f = g\circ\pi. \end{eqnarray*}$

Die Bahnen $\begin{eqnarray*} f\circ G \end{eqnarray*}$ sind die Äquivalenzklassen dieser Relation. Die Fixgruppe $\begin{eqnarray*} G_f \end{eqnarray*}$ ist hier trivial, denn aus $\begin{eqnarray*} f\circ\pi = f \end{eqnarray*}$ folgt $\begin{eqnarray*} \pi = \operatorname{id}, \end{eqnarray*}$ da $\begin{eqnarray*} f \end{eqnarray*}$ als Injektion linkskürzbar ist. Es gilt für jedes $\begin{eqnarray*} f \end{eqnarray*}$ die Bahnformel $\begin{eqnarray*} |G| = |f\circ G|\cdot |G_f|. \end{eqnarray*}$ Wir haben also $\begin{eqnarray*} |G| = |f\circ G|, \end{eqnarray*}$ womit jede Bahn die gleiche Größe $\begin{eqnarray*} |G| \end{eqnarray*}$ besitzt. Ergo findet sich die Faktorisierung

$\begin{eqnarray*} |\mathrm{Inj}(X,Y)| = |G|\cdot |\mathrm{Inj}(X,Y)/G|, \end{eqnarray*}$

wobei $\begin{eqnarray*} \mathrm{Inj}(X,Y)/G \end{eqnarray*}$ die Quotientenmenge zur Relation, also der Bahnenraum ist. Die gesuchte Anzahl ist demzufolge

$\begin{eqnarray*} |\mathrm{Inj}(X,Y)/G| = \frac{|\mathrm{Inj}(X,Y)|}{|G|} = \frac{n^{\underline k}}{k_1!\ldots k_m!} = \binom{n}{k}\binom{k}{k_1,\ldots,k_m}. \end{eqnarray*}$

Sind die Klassen $\begin{eqnarray*} X_i \end{eqnarray*}$ als Urbilder $\begin{eqnarray*} X_i=p^{-1}(a_i) \end{eqnarray*}$ vermöge einer Surjektion $\begin{eqnarray*} p\colon X\to A \end{eqnarray*}$ gegeben, nimmt die gefundene Formel die Gestalt

$\begin{eqnarray*} |\mathrm{Inj}(X,Y)/G| = \frac{|Y|^{\underline{|X|}}}{\prod_{a\in A}|p^{-1}(a)|!} \end{eqnarray*}$

an.

Zur Zählung am Computer betrachten wir ein Beispiel:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

X  = {0, 1, 2}
X1 = {0}
X2 = {1, 2}
Y  = {a, b, c, d}

Hier hat man beispielsweise die beiden miteinander identifizierten Injektionen:

{0} {1, 2}    {0} {2, 1}
 |   |  |      |   |  |
 a   b  c      a   b  c

Die beiden Tupel (a, b, c) und (a, c, b) ersetzen wir daher durch
({a}, {b, c}).

Das Programm dazu:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:

from math import prod, factorial
from itertools import islice, permutations

def ff(n, k):
    return factorial(n)//factorial(n - k)

def count1(n, kvec):
    return ff(n, sum(kvec))//prod(factorial(ki) for ki in kvec)

def split_into_sets(t, kvec):
    it = iter(t)
    return tuple(frozenset(islice(it, i)) for i in kvec)

def count2(n, kvec):
    perm = permutations(range(n), sum(kvec))
    return len(set(split_into_sets(t, kvec) for t in perm))

n = 4
kvec = [1, 2]
print(count1(n, kvec))
print(count2(n, kvec))

Es folgt ein kurzes Testprogramm. Die Funktion partitions hab ich mir kurzerhand auf Stackoverflow aus Elegant Python code for Integer Partitioning stibitzt.

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

def partitions(n, I=1):
    yield [n]
    for i in range(I, n//2 + 1):
        for p in partitions(n - i, i):
            yield [i] + p

for n in range(7):
    for k in range(1, n + 1):
        for kvec in partitions(k):
            assert count1(n, kvec) == count2(n, kvec)

18.05.2022, 21:13

HAL 9000

Auf diesen Beitrag antworten »

Da fasse ich mich eher kurz:

Für mich sind das einfach Permutationen mit Wiederholung von $\begin{eqnarray*} n \end{eqnarray*}$ Elementen, von denen je $\begin{eqnarray*} k_1, k_2, \ldots, k_m, n-k \end{eqnarray*}$ gleich sind, das ergibt direkt $\begin{eqnarray*} \frac{n!}{k_1!\cdot \ldots \cdot k_m!\cdot (n-k)!} \end{eqnarray*}$ .

Neue Frage »

Antworten »

Auf Klassen reihenfolgenlose Anordnungen

Verwandte Themen