Number of k-Cycles in Symmetric Group

Theorem

Let $n \in \N$ be a natural number.

Let $S_n$ denote the symmetric group on $n$ letters.

Let $k \in N$ such that $k \le n$.

The number of elements $m$ of $S_n$ which are $k$-cycles is given by:

$m = \paren {k - 1}! \dbinom n k = \dfrac {n!} {k \paren {n - k}!}$

Proof 1

Let $m$ be the number of elements of $S_n$ which are $k$-cycles.

From Cardinality of Set of Subsets, there are $\dfrac {n!} {k! \paren {n - k}!}$ different ways to select $k$ elements of $\set {1, 2, \ldots, n}$.

From Number of k-Cycles on Set of k Elements, each of these $\dfrac {n!} {k! \paren {n - k}!}$ sets with $k$ elements has $\paren {k - 1}!$ $k$-cycles.

It follows from Product Rule for Counting that:

 $\ds m$ $=$ $\ds \paren {k - 1}! \dfrac {n!} {k! \paren {n - k}!}$ $\ds$ $=$ $\ds \paren {k - 1}! \dbinom n k$ Definition of Binomial Coefficient $\ds$ $=$ $\ds \dfrac {n! \paren {k - 1}! } {k! \paren {n - k}!}$ $\ds$ $=$ $\ds \dfrac {n!} {k \paren {n - k}!}$

$\blacksquare$

Proof 2

Suppose $n \ge k$, and consider the number of $k$-cycles in $S_n$.

A $k$-cycle can be represented by a selection of $k$ elements from $n$ without any repeats.

From Number of Permutations, the number of permutations of $k$ elements from $n$ possible elements is $\dfrac {n!} {\paren {n - k}!}$.

However, each such string is merely a representation of an $k$-cycle; the $k$-cycle itself does not depend on the starting elements in the string.

Since there are $k$ possible starting elements, we must divide this number by $k$.

Hence, the number of $m$-cycles is

$\dfrac {n!} {k \paren {n - k}!}$

$\blacksquare$
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 2, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://proofwiki.org/wiki/Number_of_k-Cycles_in_Symmetric_Group", "fetch_time": 1695974732000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2023-40/segments/1695233510498.88/warc/CC-MAIN-20230929054611-20230929084611-00385.warc.gz", "warc_record_offset": 500515945, "warc_record_length": 11660, "token_count": 580, "char_count": 1642, "score": 3.921875, "int_score": 4, "crawl": "CC-MAIN-2023-40", "snapshot_type": "latest", "language": "en", "language_score": 0.738652765750885, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00042-of-00064.parquet"}