Circular and Necklace Permutations

Hiroshi KAJIMOTO and Mai OSABE

Department of Mathematical Science, Faculty of Education

Nagasaki University, Nagasaki 852-8521, Japan
e-mail: kajimoto@nagasaki-u.ac.jp
(Received October 31, 2006)

Abstract
We enumerate circular and necklace permutations which have beads
of several colors, and count the related combinatorial numbers.

0 Introduction
Circular and necklace permutations are standard subjects of high school com-
binatorics. On the other hand they serve a good introduction to more ad-
vanced subject of combinatorics, that is the Pólya theory of counting under
group action. In fact these enumerations were historically a precursor of the
theory [2, 4, p.558]. In this article we give the enumeration of circular and
necklace permuations according to the given number of beads for each colors,
and of the related combinatorial numbers.
A circular permutation is defined to be an equivalence class of sequences
under the cyclic group Cn , i.e., two sequences a1 a2 . . . an and b1 b2 . . . bn are
equivalent if one is a cyclic shift of the other. A necklace (or necklace permu-
tation) is defined to be an equivalence class of sequences under the dihedral
group Dn , i.e., two sequences a1 a2 . . . an and b1 b2 . . . bn are equivalent if one
is a cyclic shift of the other or if circular permutaions of them are mutually
reflective with respect to some diameter.
We make full use of the counting theory and look back the classical ex-
amples, and show how to use Pólya’s cycle index efficiently. We use combi-
natorial notation, especially relative to partitions, as in [4].

1
1 Cycle indices of cyclic and dihedral groups
We begin with a brief accout of the counting theory under group action.
A good introduction to the theory is [3, chapter 6], that is a lecture note
without detailed proof. To those who want the proof see [1, chapter 5] or
[4, section 7.24].
Let G be a subgroup of the full permutation group SX of a finite set
X. Let n = |X| be the number of elements of X. Each element g ∈ G is a
permutation of X, so g is a product of several disjoint cycles of elements of X:
g = (a1 a2 . . . ak ) . . . (c1 c2 . . . cm ). The cycle type of g determines a monomial
b (g) b (g)
p11 p22 . . . pnbn (g) , that is, g has b1 (g) cycles of length 1, b2 (g) cycles of
length 2, . . . in the cycle decomposition, so (1b1 (g) 2b2 (g) . . .) ⊢ n. Cycle index
PG is a polynomial defined by
1 ∑ b1 (g) b2 (g)
PG = p p2 . . . pbnn (g) .
|G| g∈G 1
Let R = {r, b, . . . , w} be a set of colors. Then Pólya’s main theorem is
that all the inequivalent colorings f : X → R under G are expressible by a
generating function PG substituted by pi = ri + bi + · · · + wi .
For circular and necklace permutations let X = {1, 2, . . . n} and let the
cyclic group Cn = ⟨a|an = e⟩ act on X in an obvious way: a = (1, 2, . . . , n).
The coloring f : X → R is a sequence of length n and then Cn act on
the set RX of sequences as a cyclic shift by a(r1 r2 . . . rn ) = r2 r3 . . . rn r1 . An
equivalence class of the sequences under Cn is exactly a circular permutation.
The dihedral group Dn = ⟨a, ε|an = ε2 = e, εaε = a−1 ⟩ acts on X by putting
ε being a reflection with respect to some symmetry axis. For instance put
{
(n)(1, n − 1)(2, n − 2) . . . (⌊ n2 ⌋, ⌈ n2 ⌉) when n odd
ε=
(1, n)(2, n − 1) . . . ( n2 , n2 + 1) when n even.
An equivalence class of sequences under Dn is a necklace permutation.
Lemma 1 Cycle indices of circular and necklace permutations are given by
1∑ n/d
PCn = φ(d)pd ,
n d|n
 (∑ )
 1 n/d ⌊n/2⌋
d|n φ(d)pd + np1 p2 when n odd
PDn = 2n (∑ )
 1 n/d n n/2 (n/2)−1
p21 p2
2n d|n φ(d)pd + 2
(p2 + ) when n even,
where φ(n) := #{d ∈ Z|gcd(n, d) = 1, 1 ≤ d ≤ n} is the Euler function.

2
 ⊔
For proof, notice that Cn = d|n Cn (d) where Cn (d) is a subset of all the
elements of order d and that all elements in Cn (d) have the cycle type (dn/d ) ⊢
⊔
n and |Cn (d)| = φ(d). Notice also a coset decomposition: Dn = Cn εCn and
that all the elements of εCn are reflections. When n is odd all the reflections
of εCn have the cycle type (1)(2⌊n/2⌋ ) ⊢ n. When n is even we have two kinds
of symmetry axes, half the reflections of εCn have the cycle type (2n/2 ) and
another half the reflections have (12 )(2n/2−1 ).
The total number of circular and necklace permutations of length n with
beads of k kinds of colors are given by substituting all pi = k in cycle indices.

Corollary 2 The total number C(n, k) of circular permutations of length n

with k colors of beads and N (n, k) of necklace permutations are
( )
1∑ 1∑ n d
C(n, k) = φ(d)k n/d = φ k ,
n d|n n d|n d
 { 
1 ∑ nk ⌈n/2⌉ when n odd .
N (n, k) = φ(d)k n/d + n
2n d|n 2
(k n/2 + k (n/2)+1 ) when n even

We here take the simplest:

Example (n = 3). Cycle indices:
1 1
PC3 = (p31 + 2p3 ), PD3 = (p31 + 2p3 + 3p1 p2 ).
3 6
Total numbers: C(3, k) = (k 3 + 2k)/3, N (3, k) = (k 3 + 2k + 3k 2 )/6,

k 1 2 3 4 5
C(3, k) 1 4 11 24 45 .
N (3, k) 1 4 10 20 35
k = 3: We have beads of three colors, red r, blue b and white w. Substituting
the figure inventory pi = ri + bi + wi in the cycle index, we get
1{ }
PC3 = (r + b + w)3 + 2(r3 + b3 + w3 )
3
= r3 + b3 + w3 + r2 b + r2 w + b2 r + b2 w + w2 r + w2 b + 2rbw
by the multinomial expansion.

3
 r b w

r 3 + b3 + w 3
r r b b w w

b w r

r r r r b b
r2 b + r2 w + b2 r + b2 w + w2 r + w2 b
w r b

b b w w w w

r r

2rbw
w b b w

The first 9 circles are self-reflective, the last 2 circles are pair-reflective each
other, with respect to indicated symmetry axes. We can collect terms as
∑ ∑ ∑
r3 = r3 +b3 +w3 , r2 b = r2 b+r2 w+b2 r+b2 w+w2 r+w2 b, rbw = rbw.
∑
In these sums, for instance r2 b indicates that terms with two beads of one
color and one bead of the second color are summed up, r2 b is the typical
∑
term of the possible
( ) color choices. The sum rbw has just one term when
k = 3, but has 3 terms when k ≥ 3 and has no terms hence = 0 when
k

k < 3. Then we have

∑
k ∑
k ∑
k
PC3 = r3 + r2 b + 2 rbw.

This expression is independent of the indicated number k of colors. In this

example we easily have for necklaces,

∑
k ∑
k ∑
k
P D3 = r3 + r2 b + rbw

4
 ∑
by computation or by inspection. We will seek their coefficient [ rλ ]PG ,
which is the number of essentially inequivalent color patterns under group
action.

2 Circular permutations
To get all the circular permutations of length n with beads of k kinds of
color, we have to expand PCn by substituting pd = r1d + r2d + · · · + rkd , the
power sum symmetric polyomials. In this case the expansion is fairly easy.
Remember the multinomial expansion and write that in the following way:
( ) ( )
∑ n α ∑ n ∑
k
(x1 + x2 + · · · + xk ) =n
x = xµ .
|α|=n,α∈Nk
α µ⊢n,l(µ)≤k
µ
∑
Here l(µ) is the length of a partition µ and k xµ is a monomial symmetric
polynomial mµ of k variables [4, section7.3] defined by

∑
k ∑
xµ = mµ = xα
α

where the last sum runs over all distinct permutations α = (α1 , α2 , . . .) of the
entries of the partition µ = (µ1 , µ2 , . . .). A monomial symmetric polynomial
∑k µ
x collects all the colorings whose choices of the numbers of different
k colors of beads are according to the partition µ ⊢ n. We have by the
substitution
 ( ) 
1∑ 1∑ ∑ n/d ∑k
φ(d)  rdµ 
n/d
PCn = φ(d)pd =
n d|n n d|n µ⊢n/d
µ

where dµ = (dµ1 , dµ2 , . . .) ⊢ d|µ|. Putting λ = dµ ⊢ n, we get the generating

function of circular permutations of length n with k colors of beads:

Theorem 3
 ( ) 
∑ 1 ∑ n/d ∑k
PCn = φ(d) rλ .
n λ/d 
λ⊢n d|gcd{λ1 ,λ2 ,...}

where λ/d = (λ1 /d, λ2 /d, . . .) ⊢ n/d.

5
 ∑ ∑ ( )
The coefficient [ k rλ ]PCn = d|gcd{λ1 ,λ2 ,...} n/d
λ/d
φ(d)/n is the number of es-
sentially different circular permutations according to the number of each color
indicated by the partition λ ⊢ n. For instance the number of circular permu-
tations of length n = 6 with two( )red beads,( )two blue beads and two white
∑
beads is [ r2 b2 w2 ]PC6 = {φ(1) 263 + φ(2) 133 }/6 = 16. A direct counting of
this coefficient is possible by the Burnside lemma. The cycle index involves
the Burnside lemma beforehand in its polynomial form.
∑
The number of terms in k rλ is the number of color choices among k
colors, according to the partition λ = (λ1 , λ2 , . . .) ⊢ n which indicates the
numbers of each color. The length l(λ) is now not greater than k.

Lemma 4 Let the partition λ ⊢ n be λ = (1b1 2b2 . . .) and let l(λ) = b1 + b2 +

· · · ≤ k. Then the number of terms in a monomial symmetric polynomial
∑k λ
r is ( )
k
(possibly = 0).
b1 , b2 , . . . , k − l(λ)

3 Necklaces
⌊n/2⌋ n/2−1
As to necklaces we have to expand the correction terms p1 p2 and p21 p2
in the cycle index PDn .
When n is odd we have
( n−1 )
∑ (∑ )(n−1)/2 ∑ ∑ ∑
⌊n/2⌋
p1 p2 = r1 r12 = r1 2 r2µ .
µ⊢(n−1)/2
µ
∑ ∑ ∑ ∑
For a product of monomial symmetric polynomials, r1 r2µ = i r2µ+ei
where ei is i-th unit vector. So
( n−1 )
⌊n/2⌋ ∑
k ∑ ∑
p1 p2 = 2 r2µ+ei .
i=1 µ⊢(n−1)/2 µ
( ) ( )
Put λ = 2µ+ei ⊢ n. Then (n−1)/2
µ
= (n−1)/2
⌊λ/2⌋
where ⌊λ/2⌋ = (⌊λ1 /2⌋, ⌊λ2 /2⌋, . . .) ⊢
(n − 1)/2 = ⌊n/2⌋ and λ runs over all the partitions of n those have exactly
one odd entry one by one, in the above summation. Hence
( ) k
⌊n/2⌋ ∑ ⌊n/2⌋ ∑
p1 p2 = rλ
λ ⌊λ/2⌋

6
where the sum runs over all the partitions λ of n those have exactly one odd
entry. When n is odd, the generating function of necklaces is
 
1  ∑ ⌊n/2⌋
φ(d)pd + np1 p2 
n/d
P Dn =
2n d|n
  ( )  ( ) 
1 ∑  1 ∑ n/d ∑
k ∑ ⌊n/2⌋ ∑
k 
= φ(d) rλ + rλ
2 λ⊢n n d|gcd{λ1 ,λ2 ,...} λ/d λ ⌊λ/2⌋ 
 ( ) ( )  ( ) 
(1)
∑ 1 1 ∑ n/d ⌊n/2⌋  ∑
k ∑(2)
1  ∑ n/d ∑
k
= φ(d) + λ
r + φ(d) rλ
λ 2 n d|gcd λ
λ/d ⌊λ/2⌋  λ 2n d|gcd λ
λ/d
∑
where the first sum (1) runs over partitions λ ⊢ n, l(λ) ≤ k which have the
∑
exactly one odd entries, the second sum (2) runs over the other partitions
λ ⊢ n, l(λ) ≤ k and gcd λ = gcd{λ1 , λ2 , . . .} is the great common divisor of
nonzero entries of λ.
n/2−1
When n is even direct expansion of p21 p2 is possible but clumsy. We
quote the following proposition which is convenient for power sum expansions
in the cycle index. Define the power sum symmetric polynomials as
∑
pn = mn = xni , n ≥ 1 with p0 = 1
i

pµ = pµ1 pµ2 · · · if µ = (µ1 , µ2 , . . .).

Proposition 5 ([4], 7.7.1) Let λ = (λ1 , . . . , λl ) ⊢ n, where l = l(λ), and

set ∑
pλ = Rλµ mµ .
µ⊢n

Let k = l(µ). Then Rλµ is the number of ordered partitions π = (B1 , . . . , Bk )

of the set [l] such that
∑
µj = λi , 1 ≤ j ≤ k.
i∈Bj

We then have
n/2−1 ∑
p21 p2 = p(12 2n/2−1 ) = R(12 2n/2−1 ),λ mλ .
λ

7
If Rµλ ̸= 0 then µ is a refinement of λ. So if R(12 2n/2−1 ),λ ̸= 0 then either all
entries of λ are even or exactly two entries of λ are odd. We get R(12 2n/2−1 ),λ =
( ) ( )
n/2 n/2−1
λ/2
when all entries of λ are even and R 2
(1 2 n/2−1 ),λ = 2 ⌊λ/2⌋
when λ has
exactly two odd entries, as an exercise of prop 5 (though the whole article is
an exercise of the counting theory). We have
(3) ( ) (4) ( )
n/2 (n/2)−1 ∑ n/2 ∑ ∑ n/2 − 1 ∑
p2 + p21 p2 =2 rλ + 2 rλ
λ λ/2 λ ⌊λ/2⌋
∑
where (3) runs over partitions λ ⊢ n, l(λ) ≤ k which have all even entries
∑
and (4) runs over partitions λ ⊢ n, l(λ) ≤ k which have exactly two odd
entries. Substituting the power sums and gathering terms together in
 
1 ∑ n/d n n/2 (n/2)−1 
P Dn = φ(d)pd + (p2 + p21 p2 ) ,
2n d|n 2

we get the generating function of necklaces of length n with beads of k kinds

of color.

Theorem 6 When n is odd,

 ( ) ( )  ( ) 
(1)
∑ 1 1 ∑ n/d ⌊n/2⌋  ∑
k (2)
∑ 1 ∑ n/d ∑
k
P Dn = φ(d) + r + 
λ
φ(d)  rλ .
λ 2 n d|gcd λ
λ/d ⌊λ/2⌋  λ 2n d|gcd λ
λ/d

When n is even,
 ( ) ( ) k
(3)
∑ 1 1 ∑ n/d n/2  ∑
PDn = φ(d) + rλ +
λ2 n d|gcd λ
λ/d λ/2 
 ( ) (n)  ( ) 
(4)
∑ 1 1 ∑ n/d − 1 ∑k
λ
∑(5)

1 ∑ n/d  ∑
k
φ(d) + 2 r + φ(d) rλ .
λ 2 n d|gcd λ
λ/d ⌊λ/2⌋  λ 2n d|gcd λ
λ/d
Here all the summations are for partitions λ ⊢ n, l(λ) ≤ k with the additional
∑ ∑
conditions: (1) runs over λ those have exactly one odd entry, (3) runs over
∑(4)
λ those have all even entries, runs over λ those have exactly two odd
∑(2) ∑(5)
entries, and run over the remaining partitions.

8
 ∑
The coefficient [ rλ ]PDn is the number of essentially different necklaces ac-
cording to λ ⊢ n which shows the number of beads of each colors. For instance
the number of necklaces with 2 red beads, 2 (blue
) beads and 2 white beads is
∑(3) ∑ 2 2 2
in case and so [ r b w ]PD3 = {16 + 13 }/2 = 11 (16 is the number
3

of circular permutations already counted). We count this coefficient by the

Burnside lemma in the last section. We find that the correction term of each
generating function corresponds to the number of self-reflective circular per-
mutations relative to the symmetry axes of each case. Try examples when
n = 6 or 12, and enjoy the correspondence with necklaces and mathematical
expressions, in the Pólya theory!

4 Burnside Lemma and Examples

We will give a direct counting by the Burnside lemma of the number of
circular permutations and necklaces varying the number of beads for each
colors. The Burnside(-Cauchy-Frobenius) lemma is the following, which en-
ables us to replace counting equivalence classes by counting fixed points of
the permutation group.

Lemma 7 ([4], 7.24.5 or [1], Theorem 5.2) Let X be a finite set and G
a subgroup of the full permutation group SX . For each g ∈ G let

Fix(g) = {x ∈ X|gx = x}

be the fixed point set of the permutation g. Let X/G be the set of orbits of
G. Then
1 ∑
|X/G| = |Fix(g)|.
|G| g∈G
In other words, the average number of elements of X fixed by an elements of
G is equal to the number of equivalence classes.

Let R = {r1 , r2 , . . .} be a set of colors and let λ = (λ1 , λ2 , . . .) ⊢ n be a

partition which shows the number of beads for each color. Let Rλ = {s =
s1 s2 . . . sn ∈ R[n] |s contains λ1 r1 ’s, λ2 r2 ’s,. . .} be the set of all the sequences
of length n in which color r1 appears λ1 -times, color r2 appears λ2 -times and
so on. Then G = Cn (or Dn respectively) acts on X = Rλ , and X/G = Rλ /G
is the set of all the circular permutations of length n which have λ1 -beads
of color r1 , λ2 -beads of color r2 and so on when G = Cn (or the set of all

9
the necklaces which have the same numbers of beads for each color when
G = Dn respectively). The number of elements of these sets are obtained as
coefficients [rλ ]PG = |Rλ /G| of generating functions in section 2 and 3. We
apply here the Burnside lemma 7.
Corollary 8 The number of circular permutations of length n which have
λ1 -beads of color r1 , λ2 -beads of color r2 and so on, is given by
( )
1 ∑ n/d
λ
[r ]PCn = φ(d).
n d|gcd{λ1 ,λ2 ,...} λ/d

Proof. We know
1 ∑ 1∑ ∑
[rλ ]PCn = |Rλ /Cn | = |Fix(g)| = |Fix(g)|
n g∈Cn n d|n g∈Cn (d)

by the Burnside lemma and

⊔
Cn = Cn (d)
d|n

where Cn (d) is a subset of all the elements of order d and all elements in
Cn (d) have the cycle type (dn/d ) ⊢ n. Let g ∈ Cn (d) and s = s1 s2 . . . sn ∈
Fix(g, Rλ ). Then for cycles (i1 , i2 , . . . , id ) of the permutation g, the corre-
sponding elements in the sequence s must have the same color: si1 = s(i2 =)
· · · = sid since g fixes s. Hence we see d|λi (∀i), and get |Fix(g, Rλ )| = n/d λ/d
by considering selections of colors to the (n/d)-cycles in g. Since |Cn (d)| =
φ(d) result follows.
Corollary 9 The number [rλ ]PDn of necklaces which have λ1 -beads of color
r1 , λ2 -beads of color r2 and so on, is given as follows.
When n is odd, we have
 ( ) ( 
)
1  ∑ n/d (n − 1)/2 
[rλ ]PDn = 
φ(d) +n
2n d|gcd λ λ/d ⌊λ/2⌋ 

if λ has exactly one odd entry, and

( )
λ 1 ∑ n/d
[r ]PDn = φ(d)
2n d|gcd λ λ/d

10
for other λ.
When n is even, we have
 ( ) ( ) 
1  ∑ n/d n/2 
[rλ ]PDn = φ(d) +n
2n d|gcd λ λ/d λ/2 

if λ has all even entries,

 ( ) ( ) 
1  ∑ n/d (n − 2)/2 
[rλ ]PDn = φ(d) +n
2n d|gcd λ λ/d ⌊λ/2⌋ 

if λ has exactly two odd entries, and

( )
λ 1 ∑ n/d
[r ]PDn = φ(d)
2n d|gcd λ λ/d

for other λ.
Proof. We have to take reflections into consideration. We know
 
1 ∑ 1 ∑ ∑
[rλ ]PDn = |Rλ /Dn | = |Fix(g)| = |Fix(g)| + |Fix(g)|
2n g∈Dn 2n g∈Cn g∈εCn

by the Burnside lemma and a coset decomposition

⊔
Dn = Cn εCn

where Dn = ⟨a, ε|an = ε2 = e, εaε = a−1 ⟩, Cn = ⟨a⟩ is a subgroup of all

the rotations of Dn , and all the elements of εCn are reflections with respect
to some axes. When n is odd all the reflections of εCn have the cycle type
(1)(2(n−1)/2 ) ⊢ n. When n is even we have two kinds of symmetry axes,
half the reflections of εCn have the cycle type (2n/2 ) and another half the
reflections have (12 )(2(n−2)/2 ).
Take a case when n is even for instance. Then half the reflections εCn2 =
{ε, εa2 , . . . , εan−2 } of εCn have the cycle type (2n/2 ). The typical element is
( )
n n
ε = (1, n)(2, n − 1) . . . , +1 .
2 2
Let s = s1 s2 . . . sn ∈ Fix(ε, Rλ ). Then s1 = sn , s2 = sn−1(, . . .), sn/2 = s(n/2)+1 .
Hence 2|λi (∀i). If g ∈ εCn2 , then we have |Fix(g, Rλ )| = n/2 λ/2
for λ which has

11
all even entries and Fix(g, Rλ ) = ∅ for λ which has an odd entry. Another
half εaCn2 = {εa, εa3 , . . . , εan−1 } of εCn have the cycle type (12 )(2(n−2)/2 ).
The typical element is
( )( )
n n n
εa = (n)(1, n − 1)(2, n − 2) . . . − 1, + 1 .
2 2 2
( )
The same reasoning shows that if g ∈ εCn2 , then |Fix(g, Rλ )| = n/2
for λ
( ) λ/2
which has all even entries, |Fix(g, Rλ )| = 2 (n−2)/2
⌊λ/2⌋
for λ which has exactly
two odd entries, and Fix(g, R ) = ∅ for other λ. Results for even n now
λ

follow. The simillar argument goes through the case when n is odd.

Examples. When n = 5 and( λ =) (2, 2, 1), the corresponding circular permu-

5
tations are, [r2 b2 w]PC5 = 15 2,2,1 = 30
5
= 6 as

r r r r

w r r w b b b b

b b b b w r r w

pair-wise reflective

w w

r r b b
self-reflective

b b r r

2 2
On{ the
( other
) (hand
)} the corresponding necklaces are of the number [r b (w]P
) D5 =
1 1 5 2 1 2
2 5 2,2,1
+ 1 = 2 (6 + 2) = 4. We see that the correction term 1 = 2
is the number of self-reflective circular permutations.
When n = 6, first let λ = ((4, 1,) 1). Then the corresponding circular
6
permutations are, [r4 bw]PC6 = 61 4,1,1 = 30
6
= 5 as

12
 b b b b b
w r r w r r r r r r

r r r r w r r w r r
r r r r w
pair-wise reflective self-reflective
{ ( ) ( )}
6
The corresponding necklaces are of the number [r4 bw]PD6 = 1 1
2 {(6 4,1,1
+ 2 =
) ( 2 )}
1
2
(5+1) = 3. Next let λ = (2, 2, 2) ⊢ 6. Then [r2 b2 w2 ]PC6 = 1
6
6
2,2,2
3
+ 1,1,1 =
1
6
(90 + 6) = 16 as

r r r r r r
b w w b b b b b w w w w

w b b w w r r w b r r b
r r w w b b
r r r r
b r r b b r r b
pair-wise reflective
b w w b w w w w
w w b b

r b w
b b r r r r

w w w w b b
r b w
r r r r b b self-reflective

b w wr r
b
w w b b w w

13
 [ {( ) ( )} ( )]
1 1 6 3 3
And [r2 b2 w2 ]PD6 = + + = 21 (16 + 6) = 11. We
2 6 2,2,2 ( )
1,1,1 1,1,1( )
23
see again that the correction terms = 1 and 1,1,1
2
= 6 are the numbers
of self-reflective permutations respectively. Incidentally here we can ask, is
there efficient way of writing out all the color patterns one by one in [rλ ]PG ?

The observation of examples and the proof of corollary 9 show that the
correction term counts the number of self-reflective, that is fixed by some
reflexion, circular permutations.

Theorem 10 The number of self-reflective permutations among circular per-

mutations of length n which have λ1 -beads of color r1 , λ2 -beads of color r2
and so on, is given by
2[rλ ]PDn − [rλ ]PCn
 (⌊n/2⌋)

 when n is odd and λ has only one odd entry

 ⌊λ/2⌋



 ( )



 n/2
when n is even and λ has all even entries
 λ/2
=

 ( )

 (n−2)/2

 when n is even and λ has exactly two odd entries

 ⌊λ/2⌋





0 otherwise.

References
[1] C. L. Liu, Introduction to Combinatorial Mathematics,
McGraw-Hill (1969),
組合せ数学入門 （伊理正夫−伊理由美 共訳），共立全書 541 (1972).

[2] P. A. MacMahon, Proc. London Math. Soc. 23 (1892), pp.305-313.

[3] G. Pólya, R. E. Tarjan and D. R. Woods, Notes on Introductory Combi-

natorics, Birkhäuser (1983),
組合せ論入門 (今宮淳美訳），近代科学社 (1986).

[4] R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Univ. Press

(1999).

14