バーンサイドの補題
証明の第一歩は群 G の元 g に関する和を集合 X の元 x に関する和に書き直すことである(二重数え上げ)。
∑ g ∈ G | X g | = | { ( g , x ) ∈ G × X ∣ g x = x } | = ∑ x ∈ X | G x | {\displaystyle \sum _{g\in G}\vert X^{g}\vert =\vert \{\,(g,x)\in G\times X\mid gx=x\,\}\vert =\sum _{x\in X}\vert G_{x}\vert }
(ここで X = { x ∈ X | gx = x } は群 G の元 g で固定される X のすべての元からなる集合で Gx = { g ∈ G | gx = x } は集合 X の元 x を固定する G のすべての元からなる固定群である。)
軌道・固定群定理により集合 X の各元 x の軌道 Gx = { gx ∈ X | g ∈ G } と固定群 Gx による左剰余類 G/Gx の間には自然な全単射がある。ラグランジュの定理と合わせると次を得る。
| G x | = [ G : G x ] = | G | / | G x | {\displaystyle \vert Gx\vert =[G:G_{x}]=\vert G\vert /\vert G_{x}\vert }
したがって最初の等式の右辺にある集合 X の元に関する和を次のように書き換えることができる。