ÜBER DIE INVERSIONSSTATISTIKEN VON

MACMAHON UND GOULDEN–JACKSON

Peter Paule^{∗}

Einleitung

Gegeben sei eine geordnete Partition Π = (n_{1}, n_{2}, …, n_{k}) von n (das heißt ∑_{j=1}^{k} n_{j} = n). Die q-Multinomialkoeffizienten seien definiert durch

[ \begin{matrix}n \\ n_{1}, n_{2}, …, n_{k} \end{matrix} ] = \frac{[n]!}{[n_{1}]! [n_{2}]! ⋯ [n_{k}]!},

wobei [n]! = [n] · [n − 1] ⋯ [1], [0]! = 1, mit [n] = 1 + q + ⋯ + q^{n−1}.

Diese Polynome interpretierte MacMahon [4] unter anderem folgendermaßen:

(1)  [ \begin{matrix}n \\ n_{1}, n_{2}, …, n_{k} \end{matrix} ] = ∑_{m∈M_{Π}} q^{inv(m)},

dabei ist M_{Π} die Menge aller Permutationen der Multimenge {1^{n_{1}}, 2^{n_{2}}, …, k^{n_{k}}} und inv(m) die Anzahl der Inversionen von m ∈ M_{Π}.

Zum Beispiel: Für Π = (1, 2, 1) hat m = ( \begin{matrix}1 & 2 & 3 & 4 \\ 2 & 3 & 2 & 1 \end{matrix} ) ∈ M_{Π} die Inversionen

\binom{1}{2}\binom{4}{1}, \binom{2}{3}\binom{3}{2}, \binom{2}{3}\binom{4}{1} und \binom{3}{2}\binom{4}{1}; also inv(m) = 4.

Der Inversionsstatistik von MacMahon sei die von Goulden und Jackson [1] gegenübergestellt:

(2)  [ \begin{matrix}n \\ n_{1}, n_{2}, …, n_{k} \end{matrix} ] = ∑_{ρ∈R_{Π}} q^{inv(ρ)}.

Hier ist R_{Π} die Menge aller Permutationen von n = {1, 2, …, n}, das heißt aller Elemente aus S_{n}, welche auf den Blöcken Π_{j} (j = 1, 2, …, k),

Π_{j} = {(∑_{l=1}^{j−1} n_{l}) + 1, (∑_{l=1}^{j−1} n_{l}) + 2, …, ∑_{l=1}^{j} n_{l}},

monoton steigende Funktionen darstellen.

∗Unterstützt durch die Alexander von Humboldt–Stiftung.

Zum Beispiel: Für Π = (1, 2, 1) hat ρ = 4132 ∈ R_{Π} die Inversionen (4, 1), (4, 3), (4, 2) und (3, 2); also inv(ρ) = 4.

Wir werden nun sehen, daß diese beiden Statistiken ganz eng zusammenhängen. Es existiert nämlich eine natürliche Bijektion φ,

φ : M_{Π} → R_{Π} mit

(3) inv(m) = inv(φ(m)) für alle m ∈ M_{Π}.

Damit erhält man einen äußerst einfachen Beweis der klassischen MacMahon– Statistik (1), denn die Goulden–Jacksonsche Interpretation läßt sich leicht wie folgt einsehen:

Beweis von (2). R_{Π} ist eine Transversale der Linksnebenklassen von der Younguntergruppe S_{Π} in S_{n} (vgl. zum Beispiel [3]). Dabei ist

S_{Π} = {σ ∈ S_{n} : σ[Π_{j}] = Π_{j} für j = 1, 2, …, k}

kanonisch isomorph zum direkten Produkt

S_{n_{1}} × S_{n_{2}} × ⋯ × S_{n_{k}}.

Benützt man dazu noch die wohlbekannte Tatsache, daß

(4)  [n]! = ∑_{γ∈S_{n}} q^{inv(γ)}

(Beweis zum Beispiel durch vollständige Induktion nach n), so erhält man

[n]! = ∑_{γ∈S_{n}} q^{inv(γ)} = _{∑_{ρ∈R_{Π}} ; σ∈S_{Π}}q^{inv(ρσ)} = _{∑_{ρ∈R_{Π}} ; σ∈S_{Π}}q^{inv(ρ)+inv(σ)}

= ( ∑_{ρ∈R_{Π}} q^{inv(ρ)})( ∑_{σ_{1}∈S_{n_{1}}} q^{inv(σ_{1})}) ⋯ ( ∑_{σ_{k}∈S_{n_{k}}} q^{inv(σ_{k})})

= [n_{1}]! [n_{2}]! ⋯ [n_{k}]!( ∑_{ρ∈R_{Π}} q^{inv(ρ)}) (nach (4)),

und damit die Gültigkeit von (2).

Die Bijektion φ : M_{Π} → R_{Π}

Wir schreiben m ∈ M_{Π} als m = s(1)s(2) … s(n) mit s : n → k, wobei |s^{−1}[{j}]| = |{x_{j,1}, x_{j,2}, …, x_{j,n_{j}}}| = n_{j} und x_{j,1} < x_{j,2} < ⋯ < x_{j,n_{j}} für j = 1, 2, …, k. In der Zweizeilenschreibweise

m = ( \begin{matrix}1 & 2 & … & j & … & n \\ s(1) & s(2) & … & s(j) & … & s(n) \end{matrix} )

INVERSIONSSTATISTIKEN VON MACMAHON UND GOULDEN–JACKSON 3

denken wir uns die Spalten \binom{j}{s(j)} als fest.

Eine Transposition sei das Vertauschen benachbarter Spalten \binom{y}{b}\binom{x}{a} mit b > a in \binom{x}{a}\binom{y}{b}. Wegen y < x verringert jede Transposition die Anzahl der Inversionen in der zweiten Zeile und erhöht die Anzahl der Inversionen in der ersten Zeile jeweils um genau 1.

Nach Ausführung aller möglichen Transpositionen in (5) erreicht man

( \begin{matrix}x_{1,1} & x_{1,2} & … & x_{1,n_{1}} & x_{2,1} & x_{2,2} & … & x_{2,n_{2}} & … & x_{k,1} & x_{k,2} & … & x_{k,n_{k}} \\ 1 & 1 & … & 1 & 2 & 2 & … & 2 & … & k & k & … & k \end{matrix} ) .

Nun definieren wir

φ(m) := x_{1,1}x_{1,2} … x_{1,n_{1}} … x_{k,1}x_{k,2} … x_{k,n_{k}} ∈ R_{Π}.

Die Bijektivität und die inversionserhaltende Eigenschaft (3) von φ sind wegen der Konstruktion klarerweise erfüllt.

Zum Beispiel: Π = (1, 2, 1), m = 2321 ∈ M_{Π} mit inv(m) = 4:

m = \binom{1}{2}\binom{2}{3}\binom{3}{2}\binom{4}{1} → \binom{1}{2}\binom{2}{3}\binom{4}{1}\binom{3}{2} → \binom{1}{2}\binom{4}{1}\binom{2}{3}\binom{3}{2}

→ \binom{4}{1}\binom{1}{2}\binom{2}{3}\binom{3}{2} → \binom{4}{1}\binom{1}{2}\binom{3}{2}\binom{2}{3} = φ(m).

Also ist φ(m) = 4132 ∈ R_{Π} mit inv(φ(m)) = 4.

Bemerkung. Im Falle k = n und n_{1} = n_{2} = ⋯ = n_{k} = 1 ist φ(m) = m^{−1} die inverse Permutation zu m ∈ M_{Π} = S_{n}. Das heißt, unsere Bijektion verallgemeinert die Beobachtung von Rothe in [2]: Für alle σ ∈ S_{n} gilt: inv(σ) = inv(σ^{−1}).

Literatur

[1] I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley & Sons, New York, 1983.

[2] K. F. Hindenburg (Ed.), Sammlung combinatorisch–analytischer Abhandlungen 2, Leipzig, 1800.

[3] A. Kerber and K.–J. Thürlings, Symmetrieklassen von Funktionen und ihre Abzähltheorie, Teil II, Bayreuther Math. Schriften, Heft 15, 1983.

[4] P. A. MacMahon, Two applications of general theorems in combinatory analysis, Proc. London Math. Soc. (2) 15 (1916), 314–321.

Derzeitige Adresse des Autors: Lehrstuhl II für Mathematik, Universität Bayreuth, Postfach 3008, D-8580 Bayreuth.