Counting Non-Isomorphic Maximal Independent Sets of the n-Cycle Graph

Raymond Bisdorff Computer Science and Communications Research Unit University of Luxembourg 162A, avenue de la Faïencerie L-1511 Luxembourg Luxembourg

                raymond.bisdorff@uni.lu

Jean-Luc Marichal^{1} Mathematics Research Unit University of Luxembourg 162A, avenue de la Faïencerie L-1511 Luxembourg Luxembourg

               jean-luc.marichal@uni.lu

Abstract

The number of maximal independent sets of the n-cycle graph C_{n} is known to be the nth term of the Perrin sequence. The action of the automorphism group of C_{n} on the family of these maximal independent sets partitions this family into disjoint orbits, which represent the non-isomorphic (i.e., defined up to a rotation and a reflection) maximal independent sets. We provide exact formulas for the total number of orbits and the number of orbits having a given number of isomorphic representatives. We also provide exact formulas for the total number of unlabeled (i.e., defined up to a rotation) maximal independent sets and the number of unlabeled maximal independent sets having a given number of isomorphic representatives. It turns out that these formulas involve both the Perrin and Padovan sequences.

1Corresponding author.

1 Introduction

Let G = (V, E) be a simple undirected graph, with vertex set V and edge set E. Recall that an independent set of G is a subset X of V such that no two vertices in X are adjacent. An independent set is maximal if it is not a proper subset of any other independent set.

In this paper we are concerned with maximal independent sets (MISs) of the n-cycle C_{n}, i.e., the graph consisting of a cycle with n vertices. Füredi [4] observed that the total number of MISs of C_{n} is given by the nth term p(n) of the Perrin sequence (Sequence \underline{A001608} from Sloane [8]), which is defined recursively as p(1) = 0, p(2) = 2, p(3) = 3, and

p(n) = p(n − 2) + p(n − 3) (n ⩾ 4).

The action of the automorphism group Aut(C_{n}) of C_{n} on the family of MISs of C_{n} gives rise to a partition of this family into orbits, each containing isomorphic (i.e., identical up to a rotation and a reflection) MISs. For instance, it is easy to verify that C_{6} has p(6) = 5 MISs, which can be grouped into two orbits: an orbit with two isomorphic MISs of size 3 and an orbit with three isomorphic MISs of size 2. Thus, C_{6} has essentially two non-isomorphic MISs.

Here we give a closed form formula for the number of orbits, that is, the number of non-isomorphic MISs of C_{n} (see Theorem 13). We also provide a formula for the number of orbits having a given number of isomorphic representatives. Finally, by modifying the concept of isomorphic MISs, requiring that they be identical up to a rotation only (which means that their unlabeled versions are identical), we provide a formula for the number of these unlabeled MISs (see Theorem 14) and the number of unlabeled MISs having a given number of isomorphic representatives. Incidentally, these formulas involve both Perrin and Padovan sequences, which are constructed from the same recurrence equation.

Although many results were obtained on the maximum number of MISs in a general graph (see for instance Chang and Jou [2] and Ying et al. [10] for recent results) it seems that the searching for the exact number of distinct MISs, or non-isomorphic MISs, in special subclasses of graphs has received little attention (see however Euler [3] and Kitaev [7]). We hope that by solving the case of cycle graphs we might bring more interest to this kind of challenging enumerative combinatorics problems.

2 Some properties of Aut(C_{n})

In this section we recall and give some properties of the automorphism group Aut(C_{n}) that we will use in the rest of the paper. More information on automorphism groups of graphs can be found for instance in Godsil and Royle [5].

Denote by V_{n} = {v_{0}, v_{1}, …, v_{n−1}} the set of vertices of C_{n} labeled either clockwise or counterclockwise. The index set of the vertices is assumed to be the cyclic group ℤ_{n} = {0, 1, …, n − 1} with addition modulo n.

It is well known that the group Aut(C_{n}) is isomorphic to the dihedral group of order 2n,

D_{2n} = {1, σ, …, σ^{n−1}, τ, στ, …, σ^{n−1}τ},

where σ : 2^{V_{n}} → 2^{V_{n}} is the rotation which carries every v_{i} into v_{i+1} and τ : 2^{V_{n}} → 2^{V_{n}} is the reflection which carries every v_{i} into v_{n−i}, with the properties σ^{n} = 1, τ^{2} = 1, and τσ = σ^{−1}τ. The subset {1, σ, …, σ^{n−1}} of rotations, also denoted ⟨σ⟩, is a cyclic subgroup of order n of D_{2n}.

Consider a family X_{n} ⊆ 2^{V_{n}} of subsets of V_{n} with the property that if X ∈ X_{n} then g(X) ∈ X_{n} for all g ∈ D_{2n}. For instance, the family of MISs of C_{n} fulfills this property. Indeed, independence and maximality properties, which characterize the MISs, remain stable under the action of D_{2n}.

Recall that, for any X ∈ X_{n}, the orbit and the stabilizer of X under the action of D_{2n} are respectively defined as

Orb(X) = {g(X) : g ∈ D_{2n}},
Stab(X) = {g ∈ D_{2n} : g(X) = X}.

Recall also that Stab(X) is either a cyclic or a dihedral subgroup of D_{2n} and that, by the orbit-stabilizer theorem, we have

|Orb(X)| × |Stab(X)| = |D_{2n}| = 2n,  (1)

which implies that both |Orb(X)| and |Stab(X)| divide 2n.

Let O_{n} = X_{n}/D_{2n} denote the set of orbits of X_{n} under the action of D_{2n}. We say that X, X′ ∈ X_{n} are isomorphic if Orb(X) = Orb(X′), that is, if X′ can be obtained from X by a rotation and/or a reflection.

For any divisor d ⩾ 1 of 2n (we write d|2n), denote by O_{n}^{d} the set of orbits of X_{n} of cardinality \frac{2n}{d}. By (1), O_{n}^{d} is also the set of orbits whose elements have a stabilizer of cardinality d. Define also the sequences

orb(n) = |O_{n}|,
orb_{d}(n) = |O_{n}^{d}| (d|2n),

which obviously lead to the identity

orb(n) = ∑_{d|2n} orb_{d}(n).  (2)

Moreover, since the orbits partition the set X_{n} we immediately have

|X_{n}| = ∑_{d|2n} \frac{2n}{d} orb_{d}(n).  (3)

We now introduce a concept that will be very useful as we continue, namely the membership function of any set X ∈ X_{n}.

Definition 1. The membership (or characteristic) function of a set X ∈ X_{n} is the mapping 1_{X} : V → {0, 1} defined as 1_{X}(v_{i}) = 1 if and only if v_{i} ∈ X.

The following immediate result expresses, for any set X ∈ X_{n}, the properties of Stab(X) in terms of the membership function 1_{X}.

Proposition 2. For any j ∈ ℤ and any X ∈ X_{n}, we have

(i) σ^{j} ∈ Stab(X) if and only if 1_{X}(v_{ℓ+j}) = 1_{X}(v_{ℓ}) for all ℓ ∈ ℤ,

(ii) σ^{2j}τ ∈ Stab(X) if and only if 1_{X}(v_{j+ℓ}) = 1_{X}(v_{j−ℓ}) for all ℓ ∈ ℤ,

(iii) σ^{2j+1}τ ∈ Stab(X) if and only if 1_{X}(v_{j+ℓ}) = 1_{X}(v_{j+1−ℓ}) for all ℓ ∈ ℤ.

The conditions stated in Proposition 2 have a clear geometric interpretation. If we think of C_{n} as a regular n-gon centered at the origin, then condition (i) means that X is invariant under the rotation, about the origin, which carries v_{0} into v_{j}. Then, condition (ii) means that X has a symmetry axis passing through v_{j}. Finally, condition (iii) means that X has a symmetry axis passing through the midpoint of v_{j} and v_{j+1}.

From Proposition 2 it follows that, if n is odd, all reflections fix exactly one vertex while, in the case of n even, all reflections of the form σ^{i}τ fix exactly two vertices or no vertex according to whether i is even or odd, respectively.

Definition 3. Given X ∈ X_{n} and an integer d ⩾ 1, the d-concatenation of X is the set X^{(d)} ∈ X_{dn} whose membership function is given by

1_{X^{(d)}}(v_{ℓ}) = 1_{X}(v_{ℓ}) (ℓ ∈ ℤ).

Definition 3 can be reformulated as follows: For any X ∈ X_{n}, the set X^{(d)} ∈ X_{dn} is characterized by the fact that the vector 1_{X^{(d)}}(V_{dn}) is obtained by concatenating d times the vector 1_{X}(V_{n}).

Proposition 4. For any X ∈ X_{n} and any j ∈ ℤ, we have σ^{j} ∈ Stab(X) if and only if σ^{j} ∈ Stab(X^{(d)}). Similarly, we have σ^{j}τ ∈ Stab(X) if and only if σ^{j}τ ∈ Stab(X^{(d)}).

Proof. Let us prove the second part. The first part can be proved similarly. Let X ∈ X_{n} and j ∈ ℤ. Then

σ^{j}τ ∈ Stab(X) ⇔ 1_{X}(v_{j−ℓ}) = 1_{X}(v_{ℓ}) (ℓ ∈ ℤ)
⇔ 1_{X^{(d)}}(v_{j−ℓ}) = 1_{X^{(d)}}(v_{ℓ}) (ℓ ∈ ℤ)
⇔ σ^{j}τ ∈ Stab(X^{(d)}).

Proposition 5. The number of orbits of X_{n} whose elements have a stabilizer included in ⟨σ⟩ is given by ∑_{d|n} orb_{1}(d).

Proof. Let d|n and let X ∈ X_{n} be such that Stab(X) = ⟨σ^{d}⟩. Then

1_{X}(v_{ℓ+id}) = 1_{X}(v_{ℓ}) (i, ℓ ∈ ℤ)

and hence, there is Y ∈ X_{d} such that X = Y^{(n/d)}. By Proposition 4, we necessarily have Stab(Y) = {1} and hence Orb(Y) ∈ O_{d}^{1}. It is then very easy to see that the set of orbits of X_{n} whose elements have the stabilizer ⟨σ^{d}⟩ is

{ ⋃_{Y ∈O} Y^{(n/d)} : O ∈ O_{d}^{1}},

which shows that the number of orbits of X_{n} whose elements have the stabilizer ⟨σ^{d}⟩ is given by orb_{1}(d). Hence the result.

The next proposition shows that determining the sequences orb_{d}(n) reduces to determining only the two sequences orb_{1}(n) and orb_{2}(n).

Proposition 6. For any d|2n, we have

orb_{d}(n) = \begin{cases}orb_{1}(n/d), & if d is odd; \\ orb_{2}(2n/d), & if d is even. \end{cases}

Proof. Let d ⩾ 1 be an odd integer. Consider O ∈ O_{dn}^{d} and Y ∈ O. Then

Stab(Y) = ⟨σ^{n}⟩ = {1, σ^{n}, σ^{2n}, …, σ^{(d−1)n}}.

By proceeding as in the proof of Proposition 5, we can easily see that

O_{dn}^{d} = { ⋃_{X∈O} X^{(d)} : O ∈ O_{n}^{1}},

which obviously entails orb_{d}(dn) = orb_{1}(n).

Now, let d ⩾ 1 be an even integer. Consider O ∈ O_{dn/2}^{d} and Y ∈ O. Then either

Stab(Y) = ⟨σ^{\frac{n}{2}} ⟩ = \{1, σ^{\frac{n}{2}} , …, σ^{(d−1) \frac{n}{2}} \}

(assuming n even) or there is j ∈ {0, 1, …, dn/2 − 1} such that

Stab(Y) = ⟨σ^{n}, σ^{j}τ⟩
= \{1, σ^{n}, …, σ^{( \frac{d}{2} −1)n}, σ^{j}τ, σ^{n+j}τ, …, σ^{( \frac{d}{2} −1)n+j}τ\}.

In both cases, there is X ∈ X_{n} such that Y = X^{(d/2)} and, by Proposition 4, we have

Stab(X) = \{1, σ^{\frac{n}{2}} \},

in the first case, and

Stab(X) = {1, σ^{j (mod n)}τ},

in the second case. It is then very easy to see that

O_{dn/2}^{d} = { ⋃_{X∈O} X^{(d/2)} : O ∈ O_{n}^{2}},

which obviously entails orb_{d}(dn/2) = orb_{2}(n).

3 Counting non-isomorphic MISs of C_{n}

In the present section we derive formulas for the enumeration of non-isomorphic MISs of C_{n}. Thus, we now assume that X_{n} is the set of MISs of C_{n}.

We can readily see that the membership function 1_{X} of any MIS X of C_{n} is characterized by the following two conditions:

min{1_{X}(v_{i}), 1_{X}(v_{i+1})} = 0 (i ∈ ℤ),  (4)
max{1_{X}(v_{i}), 1_{X}(v_{i+1}), 1_{X}(v_{i+2})} = 1 (i ∈ ℤ).  (5)

In fact, condition (4) expresses independence whereas condition (5) expresses maximality. Thus, for any MIS X of C_{n}, the n-tuple 1_{X}(V_{n}) is a cyclic n-list made up of 0s and 1s, with one or two 0s between two neighboring 1s.

As mentioned in the introduction, we have |X_{n}| = p(n), the nth term of the Perrin sequence. Then, from (3), we immediately have

p(n) = ∑_{d|2n} \frac{2n}{d} orb_{d}(n).  (6)

Example 7. The fact that the Perrin sequence counts the distinct MISs of C_{n} was observed without proof by Füredi [4]. A very simple bijective proof, suggested by Vatter [9], can be written as follows. Let X ∈ X_{n} and suppose that the vertex in X of maximal label is k, and the vertex of second-greatest label is j. Then k must be j + 2 or j + 3. If k = j + 2, then X \ {v_{k}} can be viewed as a MIS of C_{n−2}, while if k = j + 3 then X \ {v_{k}} can be viewed as a MIS of C_{n−3}. The inverse to this map can easily be described, thus proving that the number of MISs of C_{n} satisfies the Perrin recurrence.

We can readily see that any orbit of X_{n} can be uniquely represented by a cyclic list made up of 2s and/or 3s summing up to n, where a clockwise writing is not distinguished from its counterclockwise counterpart. The bijection between this representation and the n-list representation is straightforward: put a 2 whenever only one 0 separates two neighboring 1s and put a 3 whenever two 0s separate two neighboring 1s.

This representation of orbits immediately leads to the following result:

Proposition 8. orb(n) is the number of cyclic compositions of n in which each term is either 2 or 3, where a clockwise writing is not distinguished from its counterclockwise counterpart.

Consider the Padovan sequence q = (q(n))_{n∈ℕ} (a shifted version of Sloane’s \underline{A000931}), which is defined as q(1) = 0, q(2) = 1, q(3) = 1, and

q(n) = q(n − 2) + q(n − 3) (n ⩾ 4),  (7)

and let r = (r(n))_{n∈ℕ} be the sequence defined by

r(n) = \begin{cases}q(k), & if n = 2k − 1; \\ q(k + 2), & if n = 2k. \end{cases}

Note that, from (7) it follows that r(n) fulfills the recurrence equation

r(n) = r(n − 4) + r(n − 6) (n ⩾ 7).

The following immediate proposition shows that q(n) is the number of ways of writing n as an ordered sum in which each term is either 2 or 3. For example, q(8) = 4, and there are 4 ways of writing 8 as an ordered sum of 2s and 3s: 2 + 2 + 2 + 2, 2 + 3 + 3, 3 + 2 + 3, 3 + 3 + 2.

Proposition 9. q(n) is the number of compositions of n in which each term is either 2 or 3.

Proof. The values of q(n) for n ⩽ 3 can be easily calculated. Now, fix n ⩾ 4. From among all the possible compositions of n, q(n − 2) of them begin with a 2 and q(n − 3) of them begin with a 3, which establishes (7).

As the following proposition shows, r(n) shares the same property as q(n) but with the additional condition that the terms form a cyclic and palindromic composition. For example, r(8) = 2, and there are only 2 ways of writing 8 as an ordered sum of 2s and 3s in a cyclic and palindromic way: 2 + 2 + 2 + 2, 3 + 2 + 3.

Proposition 10. r(n) is the number of cyclic and palindromic compositions of n in which each term is either 2 or 3.

Proof. Let T ∈ {2, 3}^{m} be a cyclic and palindromic composition of n, with m terms placed counterclockwise and uniformly on the unit circle. Let X be a representative of the corresponding orbit of X_{n}. Clearly, each symmetry axis of X induces a symmetry axis of the cyclic list T. The number of symmetry axes, say d ⩾ 1, necessarily divides n since Stab(X) is a dihedral subgroup of D_{2n}.

Each of the d axes intersects the unit circle at two points. Label these 2d intersection points as a_{0}, a_{1}, …, a_{2d−1} counterclockwise. These points constitute the vertices of a regular 2d-gon. Let S be the sublist of T consisting of the terms located on the arc [a_{0}, a_{1}] inclusive, with the property that the terms located at a_{0} or a_{1}, if any, are divided by two, and let \overline{S} be the reversed version of S. According to the kaleidoscope principle (see for instance [6] for an expository note on dihedral kaleidoscopes and Coxeter groups), the sublist S is located on each of the d arcs of the form [a_{2i}, a_{2i+1}] (i ∈ ℤ_{d}) whereas the sublist \overline{S} is located on each of the d arcs of the form [a_{2i+1}, a_{2i+2}] (i ∈ ℤ_{d}). In particular, the elements of S ∪ \overline{S} sum up to n/d.

Suppose first that n = 2k − 1 is odd, which necessarily implies that d is odd (since d|n). By symmetry, there is a point a_{i} (i ∈ ℤ_{2d}) at which we have a 3 and, by rotating the composition, we can assume that i = 0. At the opposite point a_{d} we have either a 2 or no term. As this feature holds for every symmetry axis, we immediately observe that the only possible palindromic writing of T whose two extreme terms are \frac{3}{2}s is obtained by the alternating concatenation of 2d sublists S and \overline{S}, that is,

W = S\overline{S}S\overline{S} ⋯ S\overline{S}.

Let L be the first half of W and, except for its first element (which is \frac{3}{2}) and its last element (which can be 1, 2, or 3), replace in L each sublist (\frac{3}{2}, \frac{3}{2}) with 3 and each sublist (1, 1) with 2.

Let T_{n} be the set of cyclic and palindromic compositions of n in which each term is either 2 or 3. Clearly, we can assume that each of these compositions is written so that its two extreme terms are \frac{3}{2}s. For any T ∈ T_{n}, denote by L^{T} the sublist as defined above. Then, it is easy to see that the disjoint union

⋃_{T ∈T_{n}} L^{T} ,

which has cardinality |T_{n}|, is also the set of compositions of \frac{3}{2} + \frac{n−3}{2} = \frac{3}{2} + (k − 2) in which each term is either 2 or 3, except for the first term, which is \frac{3}{2}, and the last term which can be 1, or 2, or 3. By calculating the cardinality of this latter set, we obtain

|T_{n}| = q(k − 2) + q(k − 3).

Indeed, by Proposition 9, there are q(k−2) compositions whose last term is either 2 or 3, plus q(k − 3) compositions whose last term is 1. Finally, using (7) we obtain |T_{n}| = q(k) = r(n), which proves the result for n = 2k − 1.

Let us now assume that n = 2k is even. Then the two possible palindromic writings of T are obtained by the alternating concatenation of 2d sublists S and \overline{S}, that is,

W_{1} = S\overline{S}S\overline{S} ⋯ S\overline{S},
W_{2} = \overline{S}S\overline{S}S ⋯ \overline{S}S.

(Note that if S contains at least two elements then it cannot be palindromic for otherwise we would have more than d symmetry axes.)

Let L_{1} (resp. L_{2}) be the first half of W_{1} (resp. W_{2}) and, without modifying its two extreme elements, replace in L_{1} (resp. L_{2}) each sublist (\frac{3}{2}, \frac{3}{2}) with 3 and each sublist (1, 1) with 2. If S contains at least two elements then L_{1} and L_{2} are two distinct sublists. If S contains only one element then we simply set L_{1} = (1, 2, …, 2, 1) and L_{2} = (2, …, 2) in case S = (1) and L_{1} = (\frac{3}{2}, 3, …, 3, \frac{3}{2}) and L_{2} = (3, …, 3) in case S = (\frac{3}{2}).

Let T_{n} be the set of cyclic and palindromic compositions of n in which each term is either 2 or 3 and, for any T ∈ T_{n}, denote by L_{1}^{T} and L_{2}^{T} the two sublists as defined above. Then, it is easy to see that the disjoint union

⋃_{T ∈T_{n}} L_{1}^{T} ∪ ⋃_{T ∈T_{n}} L_{2}^{T} ,

which has cardinality 2|T_{n}|, is also the set of compositions of \frac{n}{2} = k in which each term is either 2 or 3, except for the two extreme terms which can be 1, or \frac{3}{2}, or 2, or 3. By calculating the cardinality of this latter set, we obtain

2 |T_{n}| = q(k) + 2q(k − 1) + q(k − 2) + q(k − 3)
= 2q(k) + 2q(k − 1)
= 2q(k + 2).

Indeed, by Proposition 9, there are q(k) compositions whose two extreme terms are 2s or 3s, plus 2q(k − 1) compositions whose only one extreme term is 1, plus q(k − 2) compositions whose two extreme terms are 1s, plus q(k − 3) compositions whose two extreme terms are \frac{3}{2}s. Finally, we have |T_{n}| = q(k + 2) = r(n), which completes the proof.

The following example illustrates the proof of Proposition 10 in the case n = 16.

Example 11. There are 7 cyclic and palindromic compositions of 16 in which each term is either 2 or 3. Table 1 gives these compositions together with the number d of symmetry axes and the sublists L_{1} and L_{2}, as defined in the proof of Proposition 10.

\begin{matrix}T & d & L_{1} & L_{2} \\ (2, 2, 2, 2, 2, 2, 2, 2) & 8 & (2, 2, 2, 2) & (1, 2, 2, 2, 1) \\ (3, 2, 3, 3, 2, 3) & 2 & (3, 2, 3) & (1, 3, 3, 1) \\ (2, 2, 3, 2, 3, 2, 2) & 1 & (2, 2, 3, 1) & (1, 3, 2, 2) \\ (2, 3, 2, 2, 2, 3, 2) & 1 & (2, 3, 2, 1) & (1, 2, 3, 2) \\ (2, 3, 3, 3, 3, 2) & 1 & (2, 3, 3) & (3, 3, 2) \\ (3, 2, 2, 2, 2, 2, 3) & 1 & (3, 2, 2, 1) & (1, 2, 2, 3) \\ (\frac{3}{2}, 2, 3, 3, 3, 2, \frac{3}{2}) & 1 & (\frac{3}{2}, 2, 3, \frac{3}{2}) & (\frac{3}{2}, 3, 2, \frac{3}{2}) \end{matrix}

Table 1: Cyclic and palindromic compositions of 16

Through the identification of the orbits of X_{n} whose elements have at least one symmetry axis with the cyclic and palindromic compositions of n made up of 2s and/or 3s, Proposition 10 can be immediately rewritten as follows:

Proposition 12. The number of orbits of X_{n} whose elements have a stabilizer not included in ⟨σ⟩ is given by r(n).

We are now able to state our main result, which gives explicit expressions for the sequences orb, orb_{1}, and orb_{2}. To this end, recall that the Dirichlet convolution product of two sequences f = (f(n))_{n∈ℕ} and g = (g(n))_{n∈ℕ} is the sequence f ∗ g = ((f ∗ g)(n))_{n∈ℕ} defined as

(f ∗ g)(n) = ∑_{d|n} f(d) g(\frac{n}{d}).

Moreover, in addition to the sequences p(n), q(n), and r(n) introduced above, consider the following integer sequences:

μ(n) = \underline{A008683}(n) (Möbius function),
\underline{A113788}(n) = \frac{1}{n} (p ∗ μ)(n),
1(n) = 1,
e_{k}(n) = \begin{cases}1, & if n = k; \\ 0, & else, \end{cases}  (k ∈ ℕ).

Theorem 13. The following equalities hold:

orb = r + orb_{1} ∗ 1,  (8)
2orb_{1} = \underline{A113788} − r ∗ μ,  (9)
orb_{2} = r ∗ μ + orb_{1} ∗ e_{2}.  (10)

Proof. Combining Propositions 5 and 12 immediately leads to (8). Next, combining (2) and (8), we can write

r(n) = ∑_{d|2n} orb_{d}(n) − ∑_{d|n} orb_{1}(d),

that is, using Proposition 6,

r(n) = ∑_{{d|2n \atop d even}} orb_{d}(n) + ∑_{{d|2n \atop d odd}} orb_{d}(n) − ∑_{d|n} orb_{1}(d)

= ∑_{\begin{matrix}d|2n \\ \frac{2n}{d} & even \end{matrix}} orb_{2}(d) + ∑_{\begin{aligned}& d|n \\ \frac{n}{d} & odd \end{aligned}} orb_{1}(d) − ∑_{d|n} orb_{1}(d)

= ∑_{d|n} orb_{2}(d) − ∑_{\begin{aligned}& d|n \\ \frac{n}{d} & even \end{aligned}} orb_{1}(d).

Hence, introducing g_{2}(n) = \frac{1+(−1)^{n}}{2} , we obtain

r = orb_{2} ∗ 1 − orb_{1} ∗ g_{2},

that is, using Möbius inversion formula and the immediate identity g_{2} = e_{2} ∗ 1,

r ∗ μ = orb_{2} − orb_{1} ∗ e_{2}.  (11)

On the other hand, combining (6) with Proposition 6, we obtain

p(n) = ∑_{{d|2n \atop d odd}} \frac{2n}{d} orb_{1}(\frac{n}{d}) + ∑_{{d|2n \atop d even}} \frac{2n}{d} orb_{2}(\frac{2n}{d})

= ∑_{{d|n \atop d odd}} \frac{2n}{d} orb_{1}(\frac{n}{d}) + ∑_{\begin{matrix}d|2n \\ \frac{2n}{d} & even \end{matrix}} d orb_{2}(d)

= ∑_{\begin{aligned}& d|n \\ \frac{n}{d} & odd \end{aligned}} 2d orb_{1}(d) + ∑_{d|n} d orb_{2}(d).

Hence, introducing f_{1}(n) = n orb_{1}(n), f_{2}(n) = n orb_{2}(n), and g_{1}(n) = \frac{1−(−1)^{n}}{2} , we obtain

p = 2f_{1} ∗ g_{1} + f_{2} ∗ 1,

that is, using Möbius inversion formula and the fact that g_{1} = 1 − g_{2} = 1 − e_{2} ∗ 1,

p ∗ μ = 2f_{1} − 2f_{1} ∗ e_{2} + f_{2},

which implies

\underline{A113788} = 2orb_{1} − orb_{1} ∗ e_{2} + orb_{2}.  (12)

Combining (11) and (12) immediately leads to formulas (9) and (10).

It is noteworthy that the sequence orb(n) can be rewritten as

2orb(n) = r(n) + \frac{1}{n}(p ∗ ϕ)(n),

where ϕ = \underline{A000010} is the Euler totient function. In fact, combining (8) and (9), we obtain

2orb(n) = 2r(n) + 2(orb_{1} ∗ 1)(n)
= r(n) + (\underline{A113788} ∗ 1)(n)

and the latter term also writes

(\underline{A113788} ∗ 1)(n) = ∑_{d|n} \frac{d}{n}(p ∗ μ)(\frac{n}{d}) = \frac{1}{n}(p ∗ μ ∗ Id)(n) = \frac{1}{n}(p ∗ ϕ)(n),  (13)

where Id(n) = n is the identity sequence.

4 Counting unlabeled MISs of C_{n}

We now investigate the simpler problem of enumerating the unlabeled MISs of C_{n}, that is, the MISs defined up to a rotation. In fact, these unlabeled MISs are nothing less than the orbits of X_{n} under the action of ⟨σ⟩.

Let orb^{σ}(n) denote the number of unlabeled MISs of C_{n} and, for any d|n, let orb_{d}^{σ}(n) denote the number of unlabeled MISs of C_{n} that have \frac{n}{d} isomorphic representatives or, equivalently, those that have a stabilizer of cardinality d.

Then, we clearly have

orb^{σ}(n) = ∑_{d|n} orb_{d}^{σ}(n),  (14)
p(n) = ∑_{d|n} \frac{n}{d} orb_{d}^{σ}(n),  (15)

and, by proceeding as in the proof of Proposition 6, we can easily show that

orb_{d}^{σ}(n) = orb_{1}^{σ}(n/d) (d|n).  (16)

We then obtain the following formulas:

Theorem 14. The following equalities hold:

orb^{σ} = orb_{1}^{σ} ∗ 1,  (17)
orb_{1}^{σ} = \underline{A113788}.  (18)

Proof. Define the sequence f_{1}^{σ}(n) = n orb_{1}^{σ}(n). Combining (14) and (16) immediately leads to (17). On the other hand, combining (15) and (16), we obtain

p(n) = ∑_{d|n} \frac{n}{d} orb_{1}^{σ}(n/d) = (f_{1}^{σ} ∗ 1)(n)

and by using Möbius inversion formula we are immediately led to (18).

It is noteworthy that, combining (13), (17), and (18), we also obtain

orb^{σ}(n) = \frac{1}{n}(p ∗ ϕ)(n).

Finally, we also have the immediate result:

Proposition 15. orb^{σ}(n) is the number of cyclic compositions of n in which each term is either 2 or 3.

Example 16. Just as for the results obtained in Section 2, the results stated in the present section do not essentially lie on the intrinsic properties of MISs. Up to the left-hand side of (15), formulas (14)–(16) remain valid for any other definition of X_{n}.

5 Summary

Starting from the Perrin (\underline{A001608}) and Padovan (shifted \underline{A000931}) sequences, respectively denoted p(n) and q(n) in the present paper, we have introduced the following new integer sequences, with an explicit expression for each of them:

• r(n) = \underline{A127682}(n) is the number of non-isomorphic MISs of C_{n} having at least one symmetry axis (see Proposition 12), where two MISs are isomorphic if they are identical up to a rotation and a reflection. It is also the number of cyclic and palindromic compositions of n in which each term is either 2 or 3 (see Proposition 10). Recall that this sequence is defined as

r(n) = \begin{cases}q(k), & if n = 2k − 1; \\ q(k + 2), & if n = 2k. \end{cases}

• For any d|2n, orb_{d}(n) gives the number of non-isomorphic MISs of C_{n} having \frac{2n}{d} isomorphic representatives. This sequence can always be expressed from one of the sequences orb_{1}(n) = \underline{A127683}(n) and orb_{2}(n) = \underline{A127684}(n) (see Proposition 6), which in turn can be directly calculated from the formulas

orb_{1}(n) = \frac{1}{2}(\underline{A113788}(n) − (r ∗ μ)(n))
orb_{2}(n) = (r ∗ μ)(n) + (orb_{1} ∗ e_{2})(n).

• orb(n) = \underline{A127685}(n) gives the number of non-isomorphic MISs of C_{n}. It is also the number of cyclic compositions of n in which each term is either 2 or 3, where a clockwise writing is not distinguished from its counterclockwise counterpart (see Proposition 8). This sequence is given explicitly by

orb(n) = r(n) + (orb_{1} ∗ 1)(n) = \frac{1}{2}(r(n) + \frac{1}{n}(p ∗ ϕ)(n)).

• (orb_{1} ∗ 1)(n) = \underline{A127686}(n) is the number of non-isomorphic MISs of C_{n} having no symmetry axis (see Proposition 5). It is also the number of cyclic and non-palindromic compositions of n in which each term is either 2 or 3, where a clockwise writing is not distinguished from its counterclockwise counterpart. This sequence is given explicitly by

(orb_{1} ∗ 1)(n) = orb(n) − r(n).

• orb^{σ}(n) = \underline{A127687}(n) is the number of unlabeled MISs of C_{n}. It is also the number of cyclic compositions of n in which each term is either 2 or 3 (see Proposition 15). This sequence is given explicitly by

orb^{σ}(n) = (\underline{A113788} ∗ 1)(n) = \frac{1}{n}(p ∗ ϕ)(n) = 2orb(n) − r(n).

• For any d|n, orb_{d}^{σ}(n) gives the number of unlabeled MISs of C_{n} having \frac{n}{d} isomorphic representatives. This sequence can always be expressed from the sequence orb_{1}^{σ}(n) (see (16)), which in turn can be directly calculated from the formulas

orb_{1}^{σ}(n) = \underline{A113788}(n) = (orb^{σ} ∗ μ)(n).

The first 40 values of the main sequences considered in this paper are listed in Table 2. We observe that, when n is prime, we have orb(n) = orb_{1}(n) + orb_{2}(n), orb_{2}(n) = r(n), and orb^{σ}(n) = orb_{1}^{σ}(n) = orb(n) + orb_{1}(n) = \frac{1}{n}p(n), which can be easily verified.

6 A musical application

In classical tonal music (see for instance Benward and Saker [1]), MISs on C_{7k} for k = 1, 2, … may be seen as musical chords built on thirds and fourths, where k denotes the number of octaves on some major or minor scale. For instance, in C major the Cmaj chord, namely C-E-G, is a MIS on C_{7} and the thirteenth chord C13maj, namely C-E-G-B-d-f-a, is a MIS on C_{14}.

On C_{7} there exists only orb(7) = orb^{σ}(7) = 1 non-isomorphic MIS, with p(7) = 7 elements giving all possible chords built on generic thirds and fourths. However, on C_{14}, that is a two octave scale, we observe orb(14) = orb^{σ}(14) = 5 non-isomorphic MIS, with p(14) = 51 elements giving all possible chords on generic (unlabeled) thirds and fourths.

Figure 1 shows the 5 possible chord sets in C major built from generic thirds and fourths on two octaves. MIS (a) represents the above-mentioned thirteenth chord C13maj, in which

Figure 1: Chord sets in C major built from generic thirds and fourths on two octaves

we observe 7 symmetry axes passing through every note of the chord. In this case, the orbit contains only 2 representatives. MIS (b) represents a repetition of the Cmaj chord in each octave, in which we have 2 symmetry axes, and the orbit contains 7 representatives. In the three remaining MISs (c), (d), and (e), we have only one symmetry axis passing respectively through 2, 1, and 0 notes and each of the corresponding orbits contains 14 representatives.

Our results provide useful tools for analyzing the symmetries of third and fourth chords on more than two octaves.

n p(n) q(n) r(n) orb(n) orb_{1}(n) orb_{2}(n) orb^{σ}(n) orb_{1}^{σ}(n)
1  0  0  0  0  0  0  0  0
2  2  1  1  1  0  1  1  1
3  3  1  1  1  0  1  1  1
4  2  1  1  1  0  0  1  0
5  5  2  1  1  0  1  1  1
6  5  2  2  2  0  0  2  0
7  7  3  1  1  0  1  1  1
8  10  4  2  2  0  1  2  1
9  12  5  2  2  0  1  2  1
10  17  7  3  3  0  1  3  1
11  22  9  2  2  0  2  2  2
12  29  12  4  4  0  2  4  2
13  39  16  3  3  0  3  3  3
14  51  21  5  5  0  3  5  3
15  68  28  4  5  1  2  6  4
16  90  37  7  7  0  5  7  5
17 119  49  5  6  1  5  7  7
18 158  65  9  10  1  6  11  8
19 209  86  7  9  2  7  11  11
20 277 114 12  14  2  9  16  13
21 367 151  9  14  5  7  19  17
22 486 200 16  20  4  13  24  21
23 644 265 12  20  8  12  28  28
24 853 351 21  30  9  16  39  34
25 1130 465 16  31  15  15  46  45
26 1497 616 28  44  16  24  60  56
27 1983 816 21  48  27  19  75  73
28 2627 1081 37  67  30  32  97  92
29 3480 1432 28  74  46  28  120  120
30 4610 1897 49  104  54  44  159  151
31 6107 2513 37  117  80  37  197  197
32 8090 3329 65  161  96  58  257  250
33 10717 4410 49  188  139  46  327  324
34 14197 5842 86  254  167  81  422  414
35 18807 7739 65  302  237  63  539  537
36 24914 10252 114  407  292  104  700  687
37 33004 13581 86  489  403  86  892  892
38 43721 17991 151  654  501  145  1157  1145
39 57918 23833 114  801  687  110  1488  1484
40 76725 31572 200 1064  862  189  1928  1911

Table 2: First 40 values of the main sequences

References

[1] B. Benward and M. Saker. Music in Theory and Practice, Vol 1. McGraw-Hill Humanities, 8th edition, 2008.

[2] G. J. Chang and M.-J. Jou. The number of maximal independent sets in connected triangle-free graphs. Discrete Math. 197/198 (1999), 169–178.

[3] R. Euler. The Fibonacci number of a grid graph and a new class of integer sequences. J. Integer Seq. 8 (2005), Article 05.2.6.

[4] Z. Füredi. The number of maximal independent sets in connected graphs. J. Graph Theory 11 (1987), 463–470.

[5] C. Godsil and G. Royle. Algebraic Graph Theory, Vol. 207 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2001.

[6] R. Goodman. Alice through looking glass after looking glass: the mathematics of mirrors and kaleidoscopes. Amer. Math. Monthly, 111 (2004), 281–298.

[7] S. Kitaev. Independent sets on path-schemes. J. Integer Seq. 9 (2006), Article 06.2.2.

[8] N. J. A. Sloane (editor). The On-Line Encyclopedia of Integer Sequences.

   http://www.research.att.com/~njas/sequences/

[9] V. R. Vatter. Private communication, 2006. School of Mathematics and Statistics, University of St Andrews, Scotland.

[10] G. C. Ying, K. K. Meng, B. E. Sagan, and V. R. Vatter. Maximal independent sets in graphs with at most r cycles. J. Graph Theory 53 (2006), 270–282.

2000 Mathematics Subject Classification: Primary 05C69; Secondary 05C38, 05A15, 05A17, 05C25, 1155. Keywords: maximal independent set, cycle graph, combinatorial enumeration, dihedral group, group action, cyclic and palindromic composition of integers, Perrin sequence, Padovan sequence.

(Concerned with sequences \underline{A000010}, \underline{A000931}, \underline{A001608}, \underline{A008683}, \underline{A113788}, \underline{A127682}, \underline{A127683}, \underline{A127684}, \underline{A127685}, \underline{A127686}, and \underline{A127687}.)

Received May 26 2008; revised version received November 25 2008. Published in Journal of Integer Sequences, December 14 2008.

Return to Journal of Integer Sequences home page.