Number of Distinct Functions on n Variables obtained by Permutation

Theorem

Let $\map f {x_1, x_2, \ldots, x_n}$ be a function on $n$ independent variables where $n > 4$.

Let $\nu$ denote the number of distinct functions that can be obtained when $\tuple {x_1, x_2, \ldots, x_n}$ are permuted.

Then:

$\nu > 2 \implies \nu \ge n$

Proof

This theorem requires a proof. In particular: Probably uses Index of Proper Subgroup of Symmetric Group, as this looks suggestive You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by crafting such a proof. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{ProofWanted}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.

Historical Note

The general problem of the number of different distinct functions obtained on permutation of the variables was one of the motivating questions that inspired group theory.

Results of this type were supplied by many early group theorists, including Joseph Louis Lagrange, Paolo Ruffini, Niels Henrik Abel, Augustin Louis Cauchy and Évariste Galois.

Sources

• 1971: Allan Clark: Elements of Abstract Algebra ... (previous) ... (next): Chapter $2$: The Symmetric Groups: $\S 85 \alpha$