%This is the AmS-TeX file for an 3 page paper.

\input amstex
\input amsppt.sty

\magnification1200
\hsize12cm
\vsize18.7cm

\nologo

\def\3{\ss}
\def\si{\sigma}
\def\ph{\varphi}
\def\inv{\operatorname{inv}}

\topmatter 
\title \"Uber die Inversionsstatistiken von MacMahon und
Goulden--Jackson
\endtitle 
\author Peter Paule\footnote"$^*$"{\hbox{Unterst\"utzt durch die
Alexander von Humboldt--Stiftung.}}
\endauthor 
\address \noindent\hskip-12pt
Derzeitige Adresse des Autors:\newline
Lehrstuhl II f\"ur Mathematik, Universit\"at Bayreuth, \newline
Postfach 3008, D-8580 Bayreuth.
\endaddress
%\email \endemail
%\dedicatory \enddedicatory
%\date \enddate
%\thanks \endthanks
%\subjclass Primary ;
% Secondary 
%\endsubjclass
%\keywords \endkeywords
%\abstract 
%\endabstract
\endtopmatter
\document

\leftheadtext{Peter Paule}
\rightheadtext{Inversionsstatistiken von MacMahon und
Goulden--Jackson}

\head \bf Einleitung\endhead

Gegeben sei eine geordnete Partition $\Pi=(n_1,n_2,\dots,n_k)$ von $n$
(das hei\3t $\sum _{j=1} ^{k}n_j=n$). Die {\it
$q$-Multinomialkoeffizienten} seien definiert durch
$$\bmatrix n\\n_1,n_2,\dots,n_k\endbmatrix=\frac {[n]!}
{[n_1]!\,[n_2]!\cdots [n_k]!},$$
wobei $[n]!=[n]\cdot [n-1]\cdots [1]$, $[0]!=1$, mit
$[n]=1+q+\dots+q^{n-1}$.

Diese Polynome interpretierte {\it MacMahon} \cite{4} unter anderem
fol\-gen\-der\-ma\-\3en:
$$\bmatrix n\\n_1,n_2,\dots,n_k\endbmatrix=\sum _{m\in M_\Pi}
^{}q^{\inv(m)},\tag1$$
dabei ist $M_\Pi$ die Menge aller Permutationen der Multimenge
$\{1^{n_1},2^{n_2},\dots,\mathbreak k^{n_k}\}$ und $\inv(m)$ die Anzahl der
Inversionen von $m\in M_\Pi$. 

Zum Beispiel: F\"ur $\Pi=(1,2,1)$ hat
$m=\left(\smallmatrix 1&2&3&4\\2&3&2&1\endsmallmatrix\right)\in M_\Pi$
die Inversionen $\binom 12 \binom 41$, $\binom 23\binom 32$, $\binom
23\binom 41$ und $\binom 32\binom 41$; also $\inv(m)=4$.

\medskip
Der Inversionsstatistik von MacMahon sei die von {\it Goulden} und
{\it Jackson} \cite{1} gegen\"ubergestellt:
$$\bmatrix n\\n_1,n_2,\dots,n_k\endbmatrix=\sum _{\rho\in R_\Pi}
^{}q^{\inv(\rho)}.\tag2$$
Hier ist $R_\Pi$ die Menge aller Permutationen von $\bold
n=\{1,2,\dots,n\}$, das hei\3t aller Elemente aus $S_{\bold n}$,
welche auf den Bl\"ocken 
$\Pi_j$ ($j=1,2,\dots,k$),
$$\textstyle
\Pi_j=\{(\sum _{l=1} ^{j-1}n_l)+1,
(\sum _{l=1} ^{j-1}n_l)+2,\dots,
\sum _{l=1} ^{j}n_l\},$$ 
monoton steigende Funktionen darstellen.

Zum Beispiel: F\"ur $\Pi=(1,2,1)$ hat $\rho=4132\in R_{\Pi}$ die
Inversionen $(4,1)$, $(4,3)$, $(4,2)$ und $(3,2)$; also
$\inv(\rho)=4$.

\medskip
Wir werden nun sehen, da\3 diese beiden Statistiken ganz eng
zu\-sam\-men\-h\"an\-gen. Es existiert n\"amlich eine nat\"urliche Bijektion
$\ph$, 
$$\align  &\ph: M_\Pi\to R_\Pi\quad \text {mit}\\
&\inv(m)=\inv(\ph(m))\quad \text {f\"ur alle $m\in M_\Pi$}.\tag3
\endalign$$
Damit erh\"alt man einen \"au\3erst einfachen Beweis der klassischen
MacMahon--Statistik (1), denn die Goulden--Jacksonsche Interpretation
l\"a\3t sich leicht wie folgt einsehen:
\demo{Beweis von (2)} 
$R_\Pi$ ist eine Transversale der Linksnebenklassen von der
Younguntergruppe $S_\Pi$ in $S_{\bold n}$ (vgl\. zum Beispiel
\cite{3}). Dabei ist 
$$S_\Pi=\{\si\in S_{\bold n}:\si[\Pi_j]=\Pi_j\text { f\"ur
}j=1,2,\dots,k\}$$
kanonisch isomorph zum direkten Produkt
$$S_{\bold n_1}\times S_{\bold n_2}\times\dots\times S_{\bold n_k}.$$
Ben\"utzt man dazu noch die wohlbekannte Tatsache, da\3
$$[n]!=\sum _{\gamma\in S_{\bold n}} ^{}q^{\inv(\gamma)}\tag4$$
(Beweis zum Beispiel durch vollst\"andige Induktion nach $n$), so
erh\"alt man
$$\align [n]!&=\sum _{\gamma\in S_{\bold n}} ^{}q^{\inv(\gamma)}=
\underset \si\in S_\Pi\to{\sum _{\rho\in R_{\Pi}}
^{}}q^{\inv(\rho\si)}=
\underset \si\in S_\Pi\to{\sum _{\rho\in R_{\Pi}}
^{}}q^{\inv(\rho)+\inv(\si)}\\
&=\bigg(\sum _{\rho\in R_{\Pi}} ^{}q^{\inv(\rho)}\bigg)
\bigg(\sum _{\si_1\in S_{\bold n_1}} ^{}q^{\inv(\si_1)}\bigg)
\cdots
\bigg(\sum _{\si_k\in S_{\bold n_k}} ^{}q^{\inv(\si_k)}\bigg)\\
&=[n_1]!\,[n_2]!\cdots [n_k]!
\bigg(\sum _{\rho\in R_{\Pi}} ^{}q^{\inv(\rho)}\bigg)
\quad \quad \text {(nach (4))},
\endalign$$
und damit die G\"ultigkeit von (2).
\enddemo

\head \bf Die Bijektion $\ph:M_\Pi\to R_\Pi$\endhead

Wir schreiben $m\in M_\Pi$ als $m=s(1)s(2)\dots s(n)$ mit $s:\bold
n\to \bold k$, wobei $\vert
s^{-1}[\{j\}]\vert=\vert\{x_{j,1},x_{j,2},\dots,x_{j,n_j}\}\vert=n_j$
und $x_{j,1}<x_{j,2}<\dots<x_{j,n_j}$ f\"ur $j=1,2,\dots,k$.
In der Zweizeilenschreibweise
$$m=\pmatrix 1&2&\dots&j&\dots&n\\ s(1)&s(2)&\dots&s(j)&\dots&s(n)\endpmatrix$$
denken wir uns die Spalten $\binom j{s(j)}$ als fest.

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

Nach Ausf\"uhrung aller m\"oglichen Transpositionen in (5) erreicht man
$$\left(\matrix\format\c\ &\c\ &\c\ &\c\ &
\c\ &\c\ &\c\ &\c\ &\c\ &\c\ &\c\ &\c\ &\c\\
x_{1,1}&x_{1,2}&\dots&x_{1,n_1}&
x_{2,1}&x_{2,2}&\dots&x_{2,n_2}&\dots&
x_{k,1}&x_{k,2}&\dots&x_{k,n_k}\\
1&1&\dots&1&2&2&\dots&2&\dots &k&k&\dots&k
\endpmatrix.$$

Nun definieren wir
$$\ph(m):=x_{1,1}x_{1,2}\dots x_{1,n_1}
\dots x_{k,1}x_{k,2}\dots x_{k,n_k}\in R_\Pi.$$
Die Bijektivit\"at und die inversionserhaltende Eigenschaft (3) von
$\ph$ sind wegen der Konstruktion klarerweise erf\"ullt.

Zum Beispiel: $\Pi=(1,2,1)$, $m=2321\in M_\Pi$ mit $\inv(m)=4$:
$$\multline \textstyle 
m=\binom 12\binom 23\binom 32\binom 41\to \binom 12\binom 23\binom
41\binom 32\to \binom 12\binom 41\binom 23\binom 32\\
\textstyle 
\to \binom 41\binom 12\binom 23\binom 32\to
\binom 41\binom 12\binom 32\binom 23=\ph(m).
\endmultline$$
Also ist $\ph(m)=4132\in R_\Pi$ mit $\inv(\ph(m))=4$.
\remark{Bemerkung} Im Falle $k=n$ und $n_1=n_2=\dots=n_k=1$ ist
$\ph(m)=m^{-1}$ die {\it inverse} Permutation zu $m\in M_\Pi=S_{\bold
n}$. Das hei\3t, unsere Bijektion verallgemeinert die Beobachtung von
{\it Rothe} in \cite{2}: {\it F\"ur alle $\si\in S_{\bold n}$} gilt:
$\inv(\si)=\inv(\si^{-1})$.

\Refs\nofrills{Literatur}

\ref\key 1\by I. P. Goulden and D. M. Jackson\book Combinatorial
Enumeration\publ John Wiley \& Sons\publaddr New York\yr 1983\endref

\ref\key 2\by K. F. Hindenburg (Ed.)\book Sammlung
combinatorisch--analytischer Abhandlungen 2\publ \publaddr Leip\-zig\yr
1800\endref

\ref\key 3\by A. Kerber and K.--J. Th\"urlings\book Symmetrieklassen
von Funktionen und ihre Ab\-z\"ahl\-the\-o\-rie, Teil~II\publ Bayreuther Math.
Schriften\publaddr Heft~15\yr 1983\endref

\ref\key 4\by P. A. MacMahon\paper Two applications of general
theorems in combinatory analysis\jour Proc. London Math. Soc. (2)
\vol 15\yr 1916\pages 314--321\endref

\endRefs
\endremark

\enddocument