Ein kombinatorischer Satz. (Q2616604)

Für jedes Paar \(a_\varkappa \), \(a_\lambda \) \((\varkappa \neq \lambda )\) von Elementen einer endlichen Menge \(a_1, a_2, \dots, a_n\) gelte eine aber nur eine der beiden Relationen \(a_\varkappa \to a_\lambda \) und \(a_\lambda \to a_\varkappa \); über die Relation selbst wird nichts vorausgesetzt. Eine Variation \(a_1', a_2',\dots, a_k'\) der Elemente \(a_1, a_2, \dots, a_n\) heiße geordnet, wenn für jedes \(\lambda =1,2,\dots,k-1\) gilt: \(a'_\lambda \to a'_{\lambda +1}\). Die Anzahl der geordneten \(k\)-gliedrigen Variationen ist kongruent \(\dbinom {n}{k}\mod 2\) und mindestens gleich \(\dbinom {n}{k}\); es gibt also \((k=n)\) stets geordnete Permutationen, und ihre Anzahl ist ungerade. Für dieses kombinatorische Problem werden noch einige äquivalente Formulierungen gegeben.