nyuuzyou/wikis huggingface dataset:
Number of Components after Removal of Bridge

== Theorem ==
Let $G = \struct {V, E}$ be a graph.
Let $e \in E$ be a bridge.
Let $m$ be the number of components of $G$.
Then when $e$ is removed from $G$, the number of components in the remaining graph is $m + 1$.
== Proof ==
It is clear, by definition of a bridge, that removing $e$ increases the number of components.
So after $e$ is removed from $G$, the number of components in the remaining graph is at least $m + 1$.
Suppose that removing $e$ disconnects $G$ into more than $m + 1$ components.
Since $e$ joins only two vertices of $G$, it can link at most two of these components.
So there is at least one extra component when $e$ is put back into $G$.
So $G$ has more than $m$ components.
This contradicts the fact that $G$ has $m$ components.
Hence the result.
Category:Graph Theory
Number of Compositions

== Theorem ==
A $k$-composition of a positive integer $n$ is an ordered $k$-tuple: $c = \tuple {c_1, c_2, \ldots, c_k}$ such that $c_1 + c_2 + \cdots + c_k = n$ and $c_i $ are strictly positive integers.
The number of $k$-composition of $n$ is $\dbinom {n - 1} {k - 1}$ and the total number of compositions of $n$ is $2^{n - 1}$ (that is for $k = 1, 2, 3, \ldots, n$).
== Proof ==
Consider the following array consisting of $n$ ones and $n - 1$ blanks:
:$\begin{bmatrix} 1 \ \_ \ 1 \ \_ \ \cdots \ \_ \ 1 \ \_ \ 1 \end{bmatrix}$
In each blank we can either put a comma or a plus sign.
Each way of choosing $,$ or $+$ will give a composition of $n$ with the commas separating the individual $c_i$'s.
It follows easily that there are $2^{n-1}$ ways of doing this, since there are two choices for each of $n-1$ blanks.
The result follows from the Product Rule for Counting.
Similarly if we want specifically $k$ different $c_i$'s then we are left with choosing $k - 1$ out of $n - 1$ blanks to place the $k - 1$ commas.
The number of ways of doing so is $\dbinom {n - 1} {k - 1}$ from the Binomial Theorem.
Category:Combinatorics
Number of Conjugates is Number of Cosets of Centralizer

== Theorem ==
Let $G$ be a group.
Let $\map {C_G} a$ be the centralizer of $a$ in $G$.
Then the number of different conjugates of $a$ in $G$ equals the number of different (left) cosets of $\map {C_G} a$:
:$\card {\conjclass a} = \index G {\map {C_G} a}$
where:
:$\conjclass a$ is the conjugacy class of $a$ in $G$
:$\index G {\map {C_G} a}$ is the index of $\map {C_G} a$ in $G$.
Consequently:
:$\card {\conjclass a} \divides \order G$
== Proof ==
Let $x, y \in \conjclass a$.
By definition of $\conjclass a$:
:$x a x^{-1} = y a y^{-1}$
By Conjugates of Elements in Centralizer, this is the case $x$ and $y$ belong to the same left coset of $\map {C_G} a$.
Hence:
:$\card {\conjclass a} = \index G {\map {C_G} a}$
It follows from Lagrange's Theorem that:
:$\card {\conjclass a} \divides \order G$
== Sources ==
* : $\S 48.2$ Conjugacy
Category:Conjugacy
Category:Centralizers
Category:Cosets
Number of Cusps of Hypocycloid from Integral Ratio of Circle Radii

== Theorem ==
Let $H$ be a hypocycloid $H$ generated by a circle $C_1$ of radius $b$ rolling within a circle $C_2$ of (larger) radius $a$.
Let $a = n b$ where $n$ is an integer.
Then $H$ has $n$ cusps.
== Proof ==
The length of the arc of $C_2$ between two adjacent cusps of $H$ is $2 \pi b$.
The total length of the circumference of $C_1$ is $2 \pi a$.
Thus the total number of cusps of $H$ is:
:$\dfrac {2 \pi a} {2 \pi b} = \dfrac {2 \pi n b} {2 \pi b} = n$
== Sources ==
* : Chapter $\text {B}.21$: The Cycloid
Category:Hypocycloids
Number of Cusps of Hypocycloid from Rational Ratio of Circle Radii

== Theorem ==
Consider the hypocycloid $H$ generated by a circle $C_1$ of radius $b$ rolling within a circle $C_2$ of (larger) radius $a$.
Let $k = \dfrac a b$ be a rational number.
Let $k$ be expressed in canonical form:
:$k = \dfrac p q$
where $p$ and $q$ are coprime.
Then $H$ has $p$ cusps.
== Proof ==
== Sources ==
* : Chapter $\text {B}.21$: The Cycloid
Category:Hypocycloids
Number of Derangements on Finite Set/Examples/10

== Example of Number of Derangements on Finite Set ==
A correspondent writes $10$ letters and addresses $10$ envelopes, one for each letter.
In how many ways can all the letters be placed in the wrong envelopes?
== Solution ==
From Number of Derangements on Finite Set:
== Sources ==
* : The misaddressed letters: $130$
Category:Number of Derangements on Finite Set
Number of Derangements on Finite Set/Examples/7

== Example of Number of Derangements on Finite Set ==
A correspondent writes $7$ letters and addresses $7$ envelopes, one for each letter.
In how many ways can all the letters be placed in the wrong envelopes?
== Solution ==
From Number of Derangements on Finite Set:
== Sources ==
* : The misaddressed letters: $130$
Category:Number of Derangements on Finite Set
Number of Derangements on Finite Set/Mistake

== Source Work ==
: 
:The Puzzles:
::The misaddressed letters
:::$130$
== Mistake ==
:A correspondent writes ten letters and addresses ten envelopes, one for each letter. In how many ways can all the letters be placed in the wrong envelopes?
The solution given is:
:Bernoulli posed the problem in terms of $n$ letters wrongly placed into $n$ envelopes, but the principle is the same. ...
:When $n = 7$, the value is $1854$.
== Correction ==
The question was asked of $10$ envelopes, but the answer was given of $7$ envelopes.
== Sources ==
* : The misaddressed letters: $130$
Category:Mistakes/Curious and Interesting Puzzles
Number of Different Ways to play First n Moves in Chess

== Theorem ==
The sequence formed from the number of ways to play the first $n$ moves in chess begins:
:$20, 400, 8902, 197 \, 742, \ldots$
The count for the fourth move is already ambiguous, as it depends on whether only legal moves count, or whether all moves, legal or illegal, are included.
The count as given here does include illegal moves in addition to legal ones.
== Proof ==
There are $20$ ways to make the $1$st move by White:
:Each of the $8$ pawns may be moved either $1$ or $2$ squares forward, making $16$ moves
:Each of the $2$ knights may be moved to either of $2$ squares before it, making $4$ moves.
For each of those $20$ first moves by White, Black has the same $20$ options.
Thus there are $20 \times 20$ possible different games after the $2$nd move.
To count the $3$rd moves, one needs to consider cases.
First note that after the $1$st move, whatever it was, there are $7$ pawns on the $2$nd rank, each of which can be moved $1$ or $2$ squares forward, making $14$ moves for each of those $400$ possibilities.
Note that if a knight was one of the pieces to have moved first, the pawn in the square behind where it ends up cannot move -- hence the $7$ pawns on the $2$nd rank that can move.
Thus there are $400 \times 14 = 5600$ possible moves involving a so-far unmoved pawn.
For each of the $400$ positions, there are exactly $8$ which consist of two pawns in opposition on the $4$th and $5$th rank.
There are also another $4 \times 20 = 80$ positions in which white moved a knight.
For all other $400 - 88 = 312$ positions, the already-moved pawn has the option of moving another square forward.
This gives another $312$ options for the $3$rd move.
We now need to take into account the possibility that White may be able to capture a Black pawn.
== Sources ==
* : $8902$
Category:Chess
Number of Different Ways to play First n Moves in Chess/Mistake

== Source Work ==
:
:The Dictionary
::$8902$
== Mistake ==
:There are $8902$ ways of playing the first $4$ moves at chess.
This is in fact the number of possible ways of playing the first $3$ moves at chess.''
== Sources ==
* : $8902$
Category:Mistakes/Curious and Interesting Numbers
Number of Different n-gons that can be Inscribed in Circle

== Theorem ==
Let $C$ be a circle on whose circumference $n$ points are placed which divide $C$ into $n$ equal arcs.
The number of different $n$-gons (either stellated or otherwise) that can be described on $C$ whose vertices are those $n$ points is:
:$S_n = \dfrac {\paren {n - 1}!} 2$
== Proof ==
An $n$-gon (either stellated or otherwise) is constructed by connecting all $n$ points in some order.
From Number of Permutations, there are ${}^n P_n = n!$ ways of ordering $n$ points.
However, for each $n$-gon formed in this way, we have:
:$n$ ways of choosing the first vertex
:$2$ different sides from that vertex to use as the first one (starting off either clockwise or anticlockwise).
and all of these end up describing the same $n$-gon.
Thus there are $\dfrac n 2 n! = \dfrac {\paren {n - 1}!} 2$ different $n$-gons.
== Examples ==
== Sources ==
* : $\text {3-3}$ Wilson's Theorem: Theorem $\text {3-5}$
Category:Stellated Polygons
Category:Polygons
Category:Combinatorics
Category:Number of Different n-gons that can be Inscribed in Circle
Number of Different n-gons that can be Inscribed in Circle/Examples/Pentagons

== Example of Number of Different n-gons that can be Inscribed in Circle ==
There are $12$ possible pentagons that can be inscribed within a circle $C$ whose $5$ vertices are a fixed set of equally-spaced points of $C$:
:
== Sources ==
* : $\text {3-3}$ Wilson's Theorem: Theorem $\text {3-5}$
Category:Number of Different n-gons that can be Inscribed in Circle
Number of Digits in Factorial

== Theorem ==
Let $n!$ denote the factorial of $n$.
The number of digits in $n!$ is approximately:
:$1 + \floor {\dfrac 1 2 \paren {\log_{10} 2 + \log_{10} \pi} + \dfrac 1 2 \log_{10} n + n \paren {\log_{10} n - \log_{10} e} }$
when $n!$ is shown in decimal notation.
This evaluates to:
:$1 + \floor {\paren {n + \dfrac 1 2} \log_{10} n - 0.43429 \ 4481 \, n + 0.39908 \ 9934}$
== Proof ==
From Stirling's Formula:
:$n! \sim \sqrt {2 \pi n} \paren {\dfrac n e}^n$
from which the result can be calculated.
To count the number of digits:
We have:
:Common Logarithm of $2$: $\log_{10} 2 \approx 0.30102 \ 9996$
:Common Logarithm of $\pi$: $\log_{10} \pi \approx 0.49714 \ 9873$
:Common Logarithm of $e$: $\log_{10} e \approx 0.43429 \ 4481$
Hence:
Hence the result from Number of Digits in Number.
Category:Factorials
Number of Digits in Number

== Theorem ==
Let $n \in \Z_{>0}$ be a strictly positive integer.
Let $b \in \Z_{>1}$ be an integer greater than $1$.
Let $n$ be expressed in base $b$.
Then the number of digits $d$ in this expression for $n$ is:
:$d = 1 + \floor {\log_b n}$
where:
:$\floor {\, \cdot \,}$ denotes the floor function
:$\log_b$ denotes the logarithm to base $b$.
== Proof ==
Let $n$ have $d$ digits when expressed in base $b$.
Then $n$ is expressed as:
:$n = \sqbrk {n_{d - 1} n_{d - 2} \dotsm d_1 d_0}$
where:
:$n = \ds \sum_{k \mathop = 0}^{d - 1} n_k b^k$
Thus:
:$b^{d - 1} \le n < b^d$
Thus we have:
By Integer equals Floor iff Number between Integer and One More:
:$d - 1 \le \log_b n < d \iff \floor {\log_b n} = d - 1$
and the result follows.
Category:Number Theory
Number of Digits in Power of 2

== Theorem ==
Let $n$ be a positive integer.
Expressed in conventional decimal notation, the number of digits in the $n$th power of $2$:
:$2^n$
is equal to:
:$\ceiling {n \log_{10} 2}$
where $\ceiling x$ denotes the ceiling of $x$.
== Proof ==
Let $2^n$ have $m$ digits when expressed in decimal notation.
By the Basis Representation Theorem and its implications, a positive integer $x$ has $m$ digits :
:$10^{m - 1} \le x < 10^m$
Thus:
Because a power of $2$ cannot equal a power of $10$, it will always be the case that:
:$m - 1 < n \log_{10} 2 < m$
and so:
:$m - 1 < n \log_{10} 2 \le m$
Hence from Integer equals Ceiling iff Number between Integer and One Less:
:$m = \ceiling {n \log_{10} 2}$
== Examples ==
== Sources ==
* : $0 \cdotp 301 \, 029 \, 995 \, 663 \, 981 \ldots$
* : $0 \cdotp 30102 \, 99956 \, 63981 \ldots$
Category:Logarithms
Category:Powers of 2
Category:Number of Digits in Power of 2
Number of Digits in Power of 2/Examples/Mersenne Number M127

== Example of Number of Digits in Power of 2 ==
When expressed in conventional decimal notation, the number of digits in the Mersenne number $M_{127}$ is $39$.
== Proof ==
Let $m$ be the number of digits in the Mersenne number $M_{127}$.
Recall the definition Mersenne number $M_{127}$:
:$M_{127} = 2^{127} - 1$
We have that $2^{127}$ is not a power of $10$.
Neither can $2^{127} - 1$ be a power of $10$.
So $M_{127}$ and $2^{127}$ have the same number of digits.
From Number of Digits in Power of 2:
:$m = \ceiling {127 \log_{10} 2}$
From Common Logarithm of 2:
:$\log_{10} 2 \approx 0 \cdotp 30102 \, 99956 \, 63981 \, 19521 \, 37389 \ldots$
and so:
:$m = \ceiling {38 \cdotp 23}$
Hence the result.
== Sources ==
* : $0 \cdotp 301 \, 029 \, 995 \, 663 \, 981 \ldots$
* : $0 \cdotp 30102 \, 99956 \, 63981 \ldots$
Category:Mersenne Numbers
Number of Digits to Represent Integer in Given Number Base

== Theorem ==
Let $n \in \Z_{>0}$ be a (strictly) positive integer.
Let $b \in \Z$ be an integer such that $b > 1$.
Let $d$ denote the number of digits of $n$ when represented in base $b$.
Then:
:$d = \ceiling {\map {\log_b} {n + 1} }$
where $\ceiling {\, \cdot \,}$ denotes the ceiling function.
== Proof ==
Let $n$ have $d$ digits.
Then:
Category:Number Theory
Number of Distinct Conjugate Subsets is Index of Normalizer

== Theorem ==
Let $G$ be a group.
Let $S$ be a subset of $G$.
Let $\map {N_G} S$ be the normalizer of $S$ in $G$.
Let $\index G {\map {N_G} S}$ be the index of $\map {N_G} S$ in $G$.
The number of distinct subsets of $G$ which are conjugates of $S \subseteq G$ is $\index G {\map {N_G} S}$.
== Proof 1 ==
== Proof 2 ==
== Sources ==
* : $\S 1.9$: Exercise $5.16 \ \text{(ii)}$
Category:Normalizers
Category:Conjugacy
Category:Number of Distinct Conjugate Subsets is Index of Normalizer
Number of Distinct Conjugate Subsets is Index of Normalizer/Proof 1

== Theorem ==
== Proof ==
We have that:
:$S^a = S^b \iff S^{a b^{-1}} = S$ (reference to be determined).
That is:
:$S^a = S^b \iff a b^{-1} \in \map {N_G} S$
which is equivalent to:
:$a^{-1} \equiv b^{-1} \pmod {\map {N_G} S}$
Thus we have a bijection between:
:the conjugacy class $\conjclass S$ of subsets of $G$ conjugate to $S$
and:
the left coset space $G / \map {N_G} S$
given by $S^a \to a^{-1} \map {N_G} S$.
Since $G / \map {N_G} S$ has $\index G {\map {N_G} S}$ elements, the result follows.
== Sources ==
* : Chapter $2$: Conjugacy, Normal Subgroups, and Quotient Groups: $\S 49$
Category:Number of Distinct Conjugate Subsets is Index of Normalizer
Number of Distinct Conjugate Subsets is Index of Normalizer/Proof 2

== Theorem ==
== Proof ==
Let $G$ act on its power set $\powerset G$ by the rule:
:$\forall g \in G, S \in \powerset G: g * S := S^{g^{-1} } = \set {x \in G: g^{-1} x g \in S}$
That is, the conjugacy action on subsets.
From Conjugacy Action on Subsets is Group Action, $*$ is a group action.
The orbit of $S \in \powerset G$ is the conjugacy class of $S$.
That is, $\Orb S$ is the set of distinct subsets of $G$ which are conjugate to $S$
The stabilizer of $S$ is its normalizer $\map {N_G} S$.
From the Orbit-Stabilizer Theorem:
:$\order {\Orb x} = \index G {\Stab x} = \dfrac {\order G} {\order {\Stab x} }$
from which the result follows directly.
== Sources ==
* : Chapter $2$: The Sylow Theorems: $\S 54$
Category:Number of Distinct Conjugate Subsets is Index of Normalizer
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 ==
== Historical Note ==
== Sources ==
* : Chapter $2$: The Symmetric Groups: $\S 85 \alpha$
Category:Function Theory
Number of Distinct Functions on n Variables obtained by Permutation/Historical Note

== Historical Note on Number of Distinct Functions on n Variables obtained by Permutation ==
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 , , , and .
== Sources ==
* : Chapter $2$: The Symmetric Groups: $\S 85 \alpha$
Category:Historical Notes
Number of Distinct Parenthesizations on Word

== Theorem ==
Let $w_n$ denote an arbitrary word of $n$ elements.
The number of distinct parenthesizations of $w_n$ is the Catalan number $C_{n - 1}$:
:$C_{n - 1} = \dfrac 1 n \dbinom {2 \paren {n - 1} } {n - 1}$
== Proof ==
Let $w_n$ denote an arbitrary word of $n$ elements.
Let $a_n$ denote the number of ways $W_n$ elements may be parenthesized.
First note that we have:
and from Parenthesization of Word of $4$ Elements:
:$a_4 = 5$
Consider a word $w_{n + 1}$ of $n + 1$ elements.
Then $w_{n + 1}$ can be formed as any one of:
:$w_1$ concatenated with $w_n$
:$w_2$ concatenated with $w_{n - 1}$
:$\dotsc$ and so on until:
:$w_n$ concatenated with $w_1$
Thus the $i$th row in the above sequence is the number of parenthesizations of $w_{n + 1}$ in which the two outermost parenthesizations contain $i$ and $n - i + 1$ terms respectively.
We have that:
:there are $a_i$ parenthesizations of $w_i$
:there are $a_{n - i + 1}$ parenthesizations of $w_{n - i + 1}$
Hence the total number of parenthesizations of $w_{n + 1}$ is the sum of all these parenthesizations for $1 \le i \le n$.
That is:
:$(1): \quad a_{n + 1} = a_1 a_n + a_2 a_{n - 1} + \dotsb + a_n a_1$
Let us start with the generating function:
:$\ds \map {G_A} z = \sum_{n \mathop = 1}^\infty a_n z^n$
Then:
Thus $\map {G_A} z$ satisfies the quadratic equation:
:$\paren {\map {G_A} z}^2 - \map {G_A} z + z = 0$
By the Quadratic Formula, this gives:
:$\map {G_A} z = \dfrac {1 \pm \sqrt {1 - 4 z} } 2$
Since $\map {G_A} 0 = 0$, we can eliminate the positive square root and arrive at:
:$(2): \quad \map {G_A} z = \dfrac 1 2 - \dfrac {\sqrt {1 - 4 z} } 2$
Expanding $\sqrt {1 - 4 z}$ using the Binomial Theorem:
:$\ds \map {G_A} z = \dfrac 1 2 - \dfrac 1 2 \sum_{n \mathop = 0}^\infty \paren {-1}^n \dbinom {\frac 1 2} n 4^n z^n$
where:
:$\dbinom {\frac 1 2} 0 = 1$
and:
:$\dbinom {\frac 1 2} n = \dfrac {\frac 1 2 \paren {\frac 1 2 - 1} \dotsm \paren {\frac 1 2 - n + 1} } {n!}$
As a result:
:$\ds (3): \quad \map {G_A} z = -\dfrac 1 2 \sum_{n \mathop = 1}^\infty \paren {-1}^n \dbinom {\frac 1 2} n 4^n z^n$
We can expand $(3)$ as a Taylor series about $0$.
As such a series, when it exists, is unique, the coefficients must be $a_n$.
Hence:
== Sources ==
* : $\text {3-4}$ Generating Functions: Theorem $\text {3-6}$
* : $42$
* : $42$
Category:Parenthesization
Category:Catalan Numbers
Number of Distinct Partial Derivatives of Order n

== Theorem ==
Let $u = \map f {x_1, x_2, \ldots, x_m}$ be a function of the $m$ independent variables $x_1, x_2, \ldots, x_m$.
The number of distinct partial derivatives of $u$ of order $n$ is:
:$\dfrac {\paren {n + m - 1}!} {n! \paren {m - 1}!}$
That is, the same as the number of terms in a homogeneous polynomial in $m$ variables of degree $n$.
== Proof ==
== Sources ==
* : $1$ Partial Differentiation: $\S 1$. Introduction: $1.3$ Higher Order Derivatives
Category:Partial Differentiation
Number of Edges in Forest

== Theorem ==
Let $F = \struct {V, E}$ be a forest with $n$ nodes and $m$ components.
Then $F$ contains $n - m$ edges.
== Proof ==
By definition, a forest is a disconnected graph whose components are all trees.
Let the number of nodes in each component of $F$ be $n_1, n_2, \ldots, n_m$ where of course $\ds \sum_{i \mathop = 1}^m n_i = n$.
From Finite Connected Simple Graph is Tree iff Size is One Less than Order, the number of edges in tree $i$ is $n_i - 1$.
So the total number of edges in $F$ is:
== Sources ==
* : $\S 4.1$: The Minimal Connector Problem: An Introduction to Trees: Problem $7$
Category:Forests
Number of Edges of Regular Graph

== Theorem ==
An $r$-regular graph of order $n$ is of size $\dfrac {n r} 2$.
=== Corollary ===
== Proof ==
The size of a $r$-regular graph is its number of edges.
The order of a $r$-regular graph is its number of vertices.
The degree of each vertex of an $r$-regular graph is $r$.
Hence the total of all the degrees of an $r$-regular graph of order $n$ is $nr$.
The result follows directly from the Handshake Lemma.
Category:Regular Graphs
Number of Edges of Regular Graph/Corollary

== Corollary to Number of Edges of Regular Graph ==
There are no $r$-regular graph of order $n$ where both $n$ and $r$ are odd.
== Proof ==
From Number of Edges of Regular Graph, an $r$-regular graph of order $n$ is of size $\dfrac {n r} 2$.
If $n$ and $r$ are both odd, then $n r$ is also odd, and hence $\dfrac {n r} 2$ is not integral.
Category:Regular Graphs
Number of Elements in Partition

== Theorem ==
Let $S$ be a set.
Let there be a partition on $S$ of $n$ subsets, each of which has $m$ elements.
Then:
:$\card S = n m$
== Proof ==
Let the partition of $S$ be $S_1, S_2, \ldots, S_n$.
Then:
:$\forall k \in \set {1, 2, \ldots, n}: \card {S_k} = m$
By definition of multiplication:
:$\ds \sum_{k \mathop = 1}^n \card {S_k} = n m$
and the result follows from the Fundamental Principle of Counting.
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 19$: Combinatorial Analysis: Theorem $19.1$
Category:Combinatorics
Number of Elements of Order p in Group of Order pq is Multiple of q

== Theorem ==
Let $p$ and $q$ be distinct prime numbers.
Let $G$ be a non-abelian group of order $p q$.
Then the number of elements of $G$ of order $p$ is a multiple of $q$.
== Proof ==
Let $x$ be an element of $G$ of order $p$.
From Center of Non-Abelian Group of Order pq is Trivial:
:$p \notin \map Z G$
where $\map Z G$ denotes the center of $G$.
As $x \notin \map Z G$:
:$\map C x \subsetneq G$
where $\map C x$ is the centralizer of $x$.
From Order of Element divides Order of Centralizer:
:$p \divides \order {\map C x}$
Then from Lagrange's Theorem, it follows directly that:
:$\order {\map C x} = p$
By Number of Conjugates is Number of Cosets of Centralizer:
:$\card {\conjclass x} = \index G {\map {C_G} x}$
where $\conjclass x$ denotes the conjugacy class of $x$.
It follows that:
:$\card {\conjclass x} = q$
and so the element of $G$ of order $p$ come in sets whose cardinality is a divisor of $q$.
== Sources ==
* : Chapter $8$: Homomorphisms, Normal Subgroups and Quotient Groups: Exercise $19 \ \text {(ii)}$
Category:Groups of Order p q
Number of Elements with given Cycle Type

== Theorem ==
Let $n \in \N$ be a natural number.
Let $S_n$ denote the symmetric group on $n$ letters.
Let $\lambda$ be an integer partition of $n$ such that $\lambda$ has $a_j$ parts of size $j$ for each $j$.
That is, such that there are $a_1$ instances of $1$s, $a_2$ instances of $2$s, $a_3$ instances of $3$s, and so on.
Let $C$ be the conjugacy class in $S_n$ comprising the elements whose cycle type is $\lambda$.
Then:
:$\size C = \dfrac {n!} {\ds \prod_j j^{a_j} a_j!}$
== Proof ==
== Sources ==
* : Chapter $2$: The Symmetric Groups: $\S 80 \beta$
Category:Symmetric Groups
Category:Permutations
Number of Fibonacci Numbers between n and 2n

== Theorem ==
Let $n \in \Z_{> 0}$ be a (strictly) positive integer.
Then there exists either one or two Fibonacci numbers between $n$ and $2 n$ inclusive.
== Proof ==
First existence is demonstrated.
Let $F_m \ge n$ such that $F_{m - 1} < n$.
This shows that the smallest Fibonacci number greater than $n$ is less than $2 n$.
Thus there exists at least one Fibonacci number between $n$ and $2 n$.
 there exist $3$ Fibonacci numbers between $n$ and $2 n$.
Let $F_m \ge n$ be the smallest of those Fibonacci numbers.
Then:
But $F_{m + 2} < 2 n$ by hypothesis.
Hence by Proof by Contradiction there can be no more than $2$ Fibonacci numbers between $n$ and $2 n$.
Let $n = 2$.
Then between $2$ and $4$ there exist $F_3 = 2$ and $F_4 = 3$.
Let $n = 10$.
Then between $10$ and $20$ there exists $F_7 = 13$ and no other Fibonacci numbers.
Thus it has been demonstrated:
:There always exists at least one Fibonacci number between $n$ and $2 n$
:There never exist more than $2$ Fibonacci number between $n$ and $2 n$
:There exist $n$ such that there exists exactly one Fibonacci number between $n$ and $2 n$
:There exist $n$ such that there exist exactly $2$ Fibonacci numbers between $n$ and $2 n$.
The result is complete.
== Historical Note ==
== Sources ==
* : $5$
* : $5$
Category:Fibonacci Numbers