Cyclic Compositions of a Positive Integer with Parts Avoiding an Arithmetic Sequence

Petros Hadjicostas School of Mathematics and Statistics Victoria University of Wellington Wellington 6140 New Zealand

                 peterhadji1@gmail.com

Abstract

A linear composition of a positive integer n is a finite sequence of positive integers (called parts) whose sum equals n. A cyclic composition of n is an equivalent class of all linear compositions of n that can be obtained from each other by a cyclic shift. In this paper, we enumerate the cyclic compositions of n that avoid an increasing arithmetic sequence of positive integers. In the case where all multiples of a positive integer r are avoided, we show that the number of cyclic compositions of n with this property equals to or is one less than the number of cyclic zero-one sequences of length n that do not contain r consecutive ones. In addition, we show that this number is related to the r-step Lucas numbers.

1 Introduction

Beck and Robbins [4] use generating functions to give an alternative proof of a result by Robbins [21, 22] regarding the number of r-regular (linear) compositions of a positive integer n. By a (linear) composition of a positive integer n of length k we mean a k-tuple (λ_{1}, λ_{2}, …, λ_{k}) ∈ ℤ_{>0}^{k} such that

n = λ_{1} + λ_{2} + ⋯ + λ_{k}.  (1)

Here the numbers λ_{1}, λ_{2}, …, λ_{k} are called the parts of the composition. By an r-regular (linear) composition of n with length k we mean a composition (λ_{1}, λ_{2}, …, λ_{k}) of n such that none of its parts are positive multiples of r. A result that appears in Beck and Robbins [4] and Robbins [21, 22], and which is stated as Theorem 5 in this paper, gives linear recursive formulas for the number of r-regular linear compositions of n.

In this paper, we state and prove a similar result for r-regular cyclic compositions (see Theorem 7). To achieve that, we first provide a formula for the number of cyclic compositions of a positive integer n with length k whose parts belong to a set A ⊆ ℤ_{>0}. See formula (4) in Theorem 1. This formula is a generalization of formulas found by Sommerville [23] more than a century ago (see below).

Cyclic compositions of length k of positive integer n can be defined as equivalent classes on the set of all linear compositions of n with length k such that two compositions belong to the same class if and only if one can be obtained from the other by a cyclic shift. If (λ_{1}, …, λ_{k}) is a representative of an equivalent class, we denote the class by [(λ_{1}, …, λ_{k})]_{R}. For example, if n = 4, then we have five equivalent classes (cyclic compositions):

(i) [(4)]_{R}, (ii) [(1, 3)]_{R} = [(3, 1)]_{R}, (iii) [(2, 2)]_{R},
(iv) [(1, 1, 2)]_{R} = [(2, 1, 1)]_{R} = [(1, 2, 1)]_{R}, (iv) [(1, 1, 1, 1)]_{R}.

Given a set A ⊆ ℤ_{>0}, we denote by c_{A}^{L}(n; k) and c_{A}^{R}(n; k) the number of linear and cyclic compositions, respectively, of length k of positive integer n with parts in A. We also let

c_{A}^{L}(n) = ∑_{k=1}^{n} c_{A}^{L}(n; k) and c_{A}^{R}(n) = ∑_{k=1}^{n} c_{A}^{R}(n; k).

When A = ℤ_{>0}, it was proven by MacMahon [16], and probably others before him, that (for 1 ≤ k ≤ n)

c_{ℤ_{>0}}^{L}(n; k) = \binom{n − 1}{k − 1} and c_{ℤ_{>0}}^{L}(n) = 2^{n−1}.  (2)

Similarly, it was proven by Sommerville [23] that, when n is prime and 1 ≤ k < n,

c_{ℤ_{>0}}^{R}(n; k) = \frac{1}{n}\binom{n}{k}.

When n = 2^{m} for some positive integer m and k is an odd positive integer less than n, he proved that

c_{ℤ_{>0}}^{R}(n; k) = \frac{1}{2^{m}} \binom{2^{m}}{k}.

Sommerville’s [23] results were generalized more than seven decades later by Razen et al. [20]; also see [2], [7, p. 48], [14], [24, pp. 70–71], and [25]. In these references, it is proven that (for 1 ≤ k ≤ n)

c_{ℤ_{>0}}^{R}(n; k) = \frac{1}{n} ∑_{j| gcd(n,k)} ϕ(j)\binom{n/j}{k/j} and c_{ℤ_{>0}}^{R}(n) = −1 + \frac{1}{n} ∑_{j|n} ϕ(j)2^{\frac{n}{j}} ,  (3)

where ϕ(n) is Euler’s totient function at n. (Here the summation ranges over all positive divisors j of gcd(n, k) in the first sum and all positive divisors j of n is the second sum.) The numbers (c_{ℤ_{>0}}^{R}(n) : n ∈ ℤ_{>0}) appear in \underline{A037306}. We generalize equations (3) to the case when A is any subset of ℤ_{>0}; see equations (4) and (5) in this paper.

We also prove that the number of cyclic r-regular compositions of n is closely related to the number of cyclic 0-1 sequences of length n that do not contain r consecutive ones; see Theorem 7. A 0-1 sequence of length n, say (δ_{1}, …, δ_{n}) with δ_{i} ∈ {0, 1} for i = 1, 2, …, n, gives rise to a cyclic sequence [(δ_{1}, …, δ_{n})]_{R} in the same way cyclic compositions were defined above. For example, there are 4 cyclic 0-1 sequences of length 3:

(i) [(0, 0, 0)]_{R}, (ii) [(1, 0, 0)]_{R} = [(0, 1, 0)]_{R} = [(0, 0, 1)]_{R},
(iii) [(0, 1, 1)]_{R} = [(1, 0, 1)]_{R} = [(1, 1, 0)]_{R}, (iv) [(1, 1, 1)]_{R}.

The total number of 0-1 cyclic sequences of length n is c_{ℤ_{>0}}^{R}(n) + 1. This was proven by MacMahon [15]. See also Bender [5] and Zhang and Hadjicostas [26].

If in a cyclic 0-1 sequence [(δ_{1}, …, δ_{n})]_{R} we identify 1 with a black bead and 0 with a white bead, then we get a (fixed) necklace with n beads; e.g., see Graham et al. [9, Section 4.9]. In Knopfmacher and Robbins [14], a bijection is given between necklaces of n beads with k black and n − k white beads, and cyclic compositions of n with k parts. This bijection, however, does not seem to help in establishing a connection between the number of cyclic r-regular compositions of n with the number of 0-1 cyclic sequences of length n that do not contain r consecutive ones, which is one the main topics of this paper. The bijection in Knopfmacher and Robbins [14] does, however, prove that the number of necklaces with n beads of which k are black and the rest white is given by the number c_{ℤ_{>0}}^{R}(n; k). In addition, it also establishes MacMahon’s [15] result that the total number of necklaces with n beads which are either black or white is c_{ℤ_{>0}}^{R}(n) + 1 (where the extra 1 corresponds to the necklace consisting of n white beads).

The organisation of the paper is as follows. In Section 2, we first provide a formula that connects c_{A}^{R}(n; k) to c_{A}^{L}(n/s; k/s), where s ranges over the common divisors of n and k. We also provide a formula that connects c_{A}^{R}(n) to c_{A}^{L}(n/s), where s|n, through a sequence of integers (g_{A}(n) : n ∈ ℤ_{>0}), which is interesting on its own right. We provide a generating function and recursive formulas for this sequence of integers (see Lemma 2). Using these results, we provide a generating function for the numbers c_{A}^{R}(n) (see Corollary 4), and we mention that this generating function is reminiscent of the theory in Flajolet and Soria [8]. For the case when A is the set of positive integers that avoid all multiples of a fixed integer, we remind the reader of a theorem in Beck and Robbins [4] and Robbins [22] that provides recursive formulas for the numbers c_{A}^{L}(n), and then (in Corollary 6) we proceed to state a similar theorem for the numbers g_{A}(n). This result involves the generalized Lucas numbers. In Theorem 8, we correct a result that appeared in Beck and Robbins [4] for the case when A avoids an increasing arithmetic sequence, and we state a similar result for the numbers g_{A}(n) in Corollary 9.

The proofs of most results in Section 2 appear in Section 3 of the paper. Section 4 contains examples that illustrate the theory and results of this paper, while Section 5 contains some concluding remarks.

Note that some of the sequences in this paper maybe shifted versions of the corresponding cited sequences in OEIS [1]. Not all authors agree on what is the first term of each sequence.

2 The main results

The following theorem connects the numbers of linear and cyclic compositions of n with parts in A, and it allows us to prove our claims in this paper. This result is important because the theory of enumeration of all linear compositions with parts in A is more wellestablished [11, 12] than the corresponding theory for the enumeration of cyclic compositions with parts in A. (Proofs of the results in this section, which have not been proven elsewhere, appear in the next section of the paper.)

Theorem 1. The number of cyclic compositions of n of length k with parts in A is given by

c_{A}^{R}(n; k) = \frac{1}{k} ∑_{s| gcd(n,k)} ϕ(s) c_{A}^{L} (\frac{n}{s}; \frac{k}{s} ) .  (4)

Also, the total number of cyclic compositions (of any length) of n with parts in A is

c_{A}^{R}(n) = \frac{1}{n} ∑_{d|n} ϕ(d)g_{A} (\frac{n}{d}) ,  (5)

where

g_{A}(s) = s ∑_{k=1}^{s} \frac{c_{A}^{L}(s; k)}{k} for s ∈ ℤ_{>0}.  (6)

The numbers (g_{A}(n) : n ∈ ℤ_{>0}) are used throughout this paper, and they satisfy some useful recurrences; see equations (8) and (9) in the lemma below.

Lemma 2. The generating function of the numbers g_{A}(n) is given by

∑_{n≥1} g_{A}(n)x^{n} = \frac{∑_{s∈A} sx^{s}}{1 − ∑_{s∈A} x^{s}} .  (7)

For each positive integer n,

g_{A}(n) = ∑_{s=1}^{n−1} g_{A}(s)I(n − s ∈ A) + n I(n ∈ A)  (8)

and

g_{A}(n) = ∑_{s=1}^{n−1} s I(s ∈ A) c_{A}^{L}(n − s) + n I(n ∈ A),  (9)

where I(x ∈ A) = 1 if x ∈ A, and zero otherwise.

Since an empty sum is by definition zero, equations (8) and (9) in Lemma 2 give g_{A}(1) = I(1 ∈ A). This of course agrees with the equation g_{A}(1) = c_{A}^{L}(1; 1) = I(1 ∈ A).

Remark 3. Using the generating function of the numbers c_{A}^{L}(n) (see Beck and Robbins [4] and Moser and Whitney [18], or see equation (22) in this paper), one can easily show that, for n ∈ ℤ_{>0},

c_{A}^{L}(n) = ∑_{s=1}^{n−1} c_{A}^{L}(s) I(n − s ∈ A) + I(n ∈ A).  (10)

The following result is reminiscent of the theory in Flajolet and Sedgewick [7, pp. 27 and 729–730] and Flajolet and Soria [8] about the generating function of cycles of unlabelled combinatorial structures, but we derive it independently using Theorem 1 and Lemma 2 above.

Corollary 4. The generating function of the total number of cyclic compositions (of any length) of n with parts in A, i.e., c_{A}^{R}(n), is

∑_{n≥1} c_{A}^{R}(n)x^{n} = ∑_{n≥1} \frac{ϕ(n)}{n} log \frac{1}{1 − ∑_{s∈A} x^{sn}} .

Robbins [22] and Beck and Robbins [4] have shown the following result for the special case when we count all r-regular linear compositions of n.

Theorem 5. If r is a fixed positive integer and A is the set all of positive integers that are not multiples of r, then the number of linear compositions of n with parts in A, i.e., c_{A}^{L}(n), is given by the sequence (f_{n} : n ∈ ℤ_{>0}) defined recursively through

f_{j} = 2^{j−1} for 1 ≤ j ≤ r − 1,
f_{r} = 2^{r−1} − 1,
f_{j} = f_{j−1} + f_{j−2} + ⋯ + f_{j−r} for j > r.

Clearly, for r = 1 the sequence (f_{n} : n ∈ ℤ_{>0}) is a sequence of 0’s. As noted in Beck and Robbins [4], the case r = 2 gives rise to the Fibonacci numbers, while the cases r = 3 and r = 4 give rise to one version of Tribonacci and Tetranacci numbers, that is, \underline{A001590} and \underline{A001631}, respectively. These sequences should not be confused, however, with the Tribonacci and Tetranacci sequences \underline{A000073} and \underline{A000078}, respectively, which are special cases of the r-step (or r-generalized) Fibonacci sequences, which are mentioned, for example, in Miles [17] and Zhang and Hadjicostas [26]. These r-step Fibonacci sequences are first cousins of the r-step Lucas numbers defined below, which are needed in this paper.

For positive integer r, following Noe and Vos Post [19] and Zhang and Hadjicostas [26], we may define the r-generalized Lucas numbers (L_{n}^{(r)} : n ∈ ℤ) by

L_{n}^{(r)} = −1 for n < 0, L_{0}^{(r)} = r,  (11)

and by the recursion

L_{n}^{(r)} = ∑_{i=1}^{r} L_{n−i}^{(r)} for all n ≥ 1.  (12)

For r = 1, starting from n = 0, we get a sequence of 1’s, while the case r = 2 corresponds to \underline{A000032}, and it is the usual Lucas sequence. Starting at n = 0, the cases r = 3 and r = 4 correspond to \underline{A001644} and \underline{A073817}, respectively.

Corollary 6. Let r be a fixed positive integer and A be the set all of positive integers that are not multiples of r. Then the sequence

(g_{A}(n) + rI(r|n) : n ∈ ℤ_{>0})

satisfies the same r-order recurrence that the sequence (c_{A}^{L}(n) : n ∈ ℤ_{>0}) satisfies in Theorem 5, but (in general) with different initial conditions. More specifically,

g_{A}(n) = L_{n}^{(r)} − rI(r|n) for all n ∈ ℤ_{>0}.

Let ρ_{n}^{(r)} be the number of cyclic sequences of length n consisting of 0’s and 1’s that do not contain r consecutive 1’s. For example, ρ_{4}^{(3)} = 4 because we have the following cyclic sequences of length n = 4 that avoid r = 3 consecutive 1’s:

(i) [(0, 0, 0, 0)]_{R}, (ii) [(0, 0, 0, 1)]_{R}, (iii) [(0, 0, 1, 1)]_{R}, (iv) [(0, 1, 0, 1)]_{R}.

(To be able to define ρ_{n}^{(r)} for any n, r ∈ ℤ_{>0}, we make the convention that a sequence of length n with all 1’s contains r consecutive 1’s even if n < r.) For r = 2 and r = 3 the sequences of numbers ρ_{n}^{(r)} appear in \underline{A000358} and \underline{A093305}, respectively.

Using Theorem 1, Corollary 6, and a result from Zhang and Hadjicostas [26], we prove in the next section the following theorem.

Theorem 7. If r is a fixed positive integer and A is the set all of positive integers that are not multiples of r, then the number of cyclic compositions of n with parts in A, i.e., c_{A}^{R}(n), is given by

c_{A}^{R}(n) = −I(r|n) + \frac{1}{n} ∑_{d|n} ϕ (\frac{n}{d}) L_{d}^{(r)} = −I(r|n) + ρ_{n}^{(r)},  (13)

where I(r|n) = 1 if r|n, and zero otherwise.

In other words, the previous theorem says that when r does not divide n, the number of r-regular cyclic compositions of n equals the number of cyclic sequences of length n consisting of 0’s and 1’s that not contain r consecutive 1’s. Otherwise, if r divides n, then c_{A}^{(R)}(n) = ρ_{n}^{(r)} − 1.

When A is the set of all positive integers that do not include any member of an increasing arithmetic sequence, say of the form m + jr for j ∈ ℤ_{≥0}, where r and m are positive integers with m < r, we may derive a result like Corollary 6 above, but not as elegant. This is done in Corollary 9 below.

Before we do that, we remind the reader of a result in Beck and Robbins [4] about the number of linear compositions of n with parts that are not members of an increasing arithmetic sequence of positive integers. Unfortunately, some of the initial conditions in the recurrence in Theorem 4 in Beck and Robbins [4] are not correct, so we correct them here. The proof of the corrected Theorem 4, stated as Theorem 8 below, is similar to the proofs in Beck and Robbins [4], and hence it is omitted; one can also prove it using equation (10) in this paper. (The notation B − C denotes set difference between the sets B and C.)

Theorem 8. Let r and m be fixed integers with 1 ≤ m < r, and let

A = ℤ_{>0} − {m + jr : j ∈ ℤ_{≥0}}.  (14)

Then the number of linear compositions of n with parts in A, i.e., c_{A}^{L}(n), is given by the sequence (f_{n} : n ∈ ℤ_{>0}) defined recursively through

f_{n} = 2^{n−1} for 1 ≤ n ≤ m − 1,
f_{m} = 2^{m−1} − 1,
f_{n} = ∑_{{i=1 \atop i≠m}}^{n−1} f_{n−i} + 1 for m + 1 ≤ n ≤ r,

f_{n} = ∑_{{i=1 \atop i≠m}}^{r−1} f_{n−i} + 2f_{n−r} for n > r.

Using Lemma 2, we can prove the result below. Here, I[n ≢ m (mod r)] = 1 when r does not divide n − m, and zero otherwise.

Corollary 9. Let r and m be fixed integers with 1 ≤ m < r, and assume A is given by equation (14). Then the sequence (g_{A}(n) : n ∈ ℤ_{>0}) satisfies

g_{A}(n) = 2^{n} − 1 for 1 ≤ n ≤ m − 1,
g_{A}(m) = 2^{m} − m − 1,
g_{A}(n) = ∑_{{i=1 \atop i≠m}}^{n−1} g_{A}(n − i) + n for m + 1 ≤ n ≤ r,

g_{A}(n) = ∑_{{i=1 \atop i≠m}}^{r−1} g_{A}(n − i) + 2g_{A}(n − r) + r I[n ≢ m (mod r)] for n > r.

There is some similarity between the four equalities in Theorem 8 and those in Corollary 9, but the two results yield different sequences (for fixed values of m and r). For example, when m = 1 < r, the sequence (f_{n} : n ∈ ℤ_{>0}) in Theorem 8 is defined through

f_{1} = 0, f_{n} = ∑_{i=2}^{n−1} f_{n−i} + 1 for 2 ≤ n ≤ r,

and

f_{n} = ∑_{i=2}^{r−1} f_{n−i} + 2f_{n−r} for n ≥ r + 1.

On the other hand, the sequence (g_{A}(n) : n ∈ ℤ_{>0}) in Corollary 9 is defined through

g_{A}(1) = 0, g_{A}(n) = ∑_{i=2}^{n−1} g_{A}(n − i) + n for 2 ≤ n ≤ r,

and

g_{A}(n) = ∑_{i=2}^{r−1} g_{A}(n − i) + 2g_{A}(n − r) + r I(r ∤ n − 1) for n > r.

3 Proofs

In this section we prove Theorems 1 and 7, Corollaries 4, 6 and 9, and Lemma 2 from the previous section. Before we do that, we illustrate that Theorem 1 works even when A = ℤ_{>0}. Equation (4) in Theorem 1 becomes

c_{A}^{R}(n, k) = \frac{1}{k} ∑_{s| gcd(n,k)} ϕ(s) \binom{(n/s) − 1}{(k/s) − 1}

= \frac{1}{n} ∑_{s| gcd(n,k)} ϕ(s) \frac{n/s}{k/s}\binom{(n/s) − 1}{(k/s) − 1} = \frac{1}{n} ∑_{s| gcd(n,k)} ϕ(s) \binom{n/s}{k/s},

which is the first equation in (3). Also, when A = ℤ_{>0}, we can use the first equation in (2) and equation (6) to obtain

g_{A}(n) = n ∑_{k=1}^{n} \frac{\binom{n−1}{k−1}}{k} = 2^{n} − 1.  (15)

We leave it to the reader to prove the second equation in (15); e.g. use the binomial theorem and integration. It follows from Theorem 1 that

c_{A}^{R}(n) = \frac{1}{n} ∑_{d|n} ϕ(d) (2^{n/d} − 1) = \frac{1}{n} ∑_{d|n} ϕ(d)2^{n/d} − \frac{1}{n} ∑_{d|n} ϕ(d),

which gives the second equation in (3) because ∑_{d|n} ϕ(d) = n; see Apostol [3, Section 2.3].

Proof of Theorem 1. Consider an arbitrary circular composition [(λ_{1}, …, λ_{k})]_{R} of n with length k and with parts in A. Place the λ_{i}’s of this composition on a circle (i.e., λ_{1} follows λ_{n}). We define the period h of this circular composition to be the length of the shortest subsequence of λ_{i}’s with consecutive indices that is able to re-produce [(λ_{1}, …, λ_{k})]_{R} by repeating itself k/h times. Because of equation (1), we must have that the positive integer k/h divides n.

The set of all linear compositions of n with length k and parts in A can be partitioned into equivalent classes representing all circular compositions of n with length k and parts in A. These equivalent classes can be classified according to their period h, and each equivalent class with period h produces exactly h linear compositions of n with length k and with parts in A. If we denote by c_{A}^{R}(n; k; h) the number of all circular compositions of n with length k, period h, and parts in A, then

c_{A}^{L}(n; k) = ∑_{h|k & \frac{k}{h} |n} h c_{A}^{R}(n; k; h).

Let s = \frac{k}{h}, in which case

c_{A}^{L}(n; k) = ∑_{s| gcd(n,k)} \frac{k}{s} c_{A}^{R} (n; k; \frac{k}{s} ) = ∑_{s| gcd(n,k)} \frac{k}{s} c_{A}^{R} (\frac{n}{s}; \frac{k}{s}; \frac{k}{s} ) .  (16)

The last step follows from the fact that a circular composition of n with length k and period k/s can be partitioned into s identical circular compositions of n/s with length k/s and period k/s. Similarly,

c_{A}^{R}(n; k) = ∑_{h|k & \frac{k}{h} |n} c_{A}^{R}(n; k; h)

= ∑_{s| gcd(n,k)} c_{A}^{R} (n; k; \frac{k}{s} ) = ∑_{s| gcd(n,k)} c_{A}^{R} (\frac{n}{s}; \frac{k}{s}; \frac{k}{s} ) .

Letting a = gcd(n, k), n^{∗} = n/a, k^{∗} = k/a, and v = a/s, we get

c_{A}^{R}(n^{∗}a, k^{∗}a) = ∑_{s|a} c_{A}^{R} (\frac{n^{∗}a}{s}; \frac{k^{∗}a}{s}; \frac{k^{∗}a}{s}) = ∑_{v|a} c_{A}^{R}(n^{∗}v; k^{∗}v; k^{∗}v)  (17)

and

c_{A}^{L}(n^{∗}a; k^{∗}a) = ∑_{v|a} k^{∗}v c_{A}^{R}(n^{∗}v; k^{∗}v; k^{∗}v).  (18)

Fixing n^{∗} and k^{∗} while varying a (and this can be done because n and k are arbitrary positive integers with 1 ≤ k ≤ n), we apply the Möbius ‘inversion principle’ on equation (18); see Graham et al. [9, Section 4.9]. We then get, for v ∈ ℤ_{>0},

k^{∗}v c_{A}^{R}(n^{∗}v; k^{∗}v; k^{∗}v) = ∑_{w|v} μ(w) c_{A}^{L} (\frac{n^{∗}v}{w}; \frac{k^{∗}v}{w} ) .  (19)

Here μ(d) is the Möbius function at integer d, which equals 1 if d is square-free with an even number of prime factors, −1 if d is square-free with an odd number of prime factors, and 0 otherwise; e.g., see Apostol [3, Chapter 2].

It follows from equations (17) and (19) that

c_{A}^{R}(n^{∗}a, k^{∗}a) = ∑_{v|a} \frac{1}{k^{∗}v} ∑_{w|v} μ(w) c_{A}^{L} (\frac{n^{∗}v}{w}; \frac{k^{∗}v}{w} )

= \frac{1}{k^{∗}a} ∑_{v|a} \frac{a}{v} (∑_{w|v} μ(w) c_{A}^{L} (\frac{n^{∗}v}{w}; \frac{k^{∗}v}{w} ))

= \frac{1}{k^{∗}a} ∑_{v|a} (∑_{w|v} \frac{v}{w}μ(w)) c_{A}^{L} (\frac{n^{∗}a}{v}; \frac{k^{∗}a}{v}) .

The last step follows from the associativity of Dirichlet convolutions; see again Apostol [3, Chapter 2]. Using the formula

v ∑_{w|v} \frac{μ(w)}{w} = ϕ(v),

which is a standard result from Number Theory (e.g. see Apostol [3, Theorem 2.3]), we get

c_{A}^{R}(n^{∗}a, k^{∗}a) = \frac{1}{k^{∗}a} ∑_{v|a} ϕ(v) c_{A}^{L} (\frac{n^{∗}a}{v}; \frac{k^{∗}a}{v}) .

Using the equalities n = n^{∗}a, k = k^{∗}a, and a = gcd(n, k) in the above equation, we obtain equation (4). The methodology we used above is due to Bender [5].

To prove equation (5) we sum both sides of (4) from k = 1 to k = n:

c_{A}^{R}(n) = ∑_{k=1}^{n} c_{A}^{R}(n; k) = ∑_{k=1}^{n} ∑_{d| gcd(n,k)} \frac{1}{k}ϕ(d) c_{A}^{L} (\frac{n}{d}; \frac{k}{d}) .

Letting t = n/d and ℓ = k/d, and switching the order of summation in the last double sum above, we get

c_{A}^{R}(n) = ∑_{t|n} ∑_{ℓ=1}^{t} \frac{ϕ(n/t)}{ℓn/t} c_{A}^{L}(t; ℓ) = \frac{1}{n} ∑_{t|n} ϕ (\frac{n}{t}) t ∑_{ℓ=1}^{t} \frac{c_{A}^{L}(t; ℓ)}{ℓ}.

Using equation (6), we can easily get equation (5).

Proof of Lemma 2. According to Beck and Robbins [4] and Hoggatt and Lind [13], the bivariate generating function of the numbers c_{A}^{L}(n; k) is given by

C_{A}^{L}(x, y) = 1 + ∑_{n,k≥1} c_{A}^{L}(n; k)x^{n}y^{k} = \frac{1}{1 − y ∑_{s∈A} x^{s}} ,  (20)

which implies

∑_{n,k≥1} c_{A}^{L}(n; k)x^{n}y^{k−1} = \frac{∑_{s∈A} x^{s}}{1 − y ∑_{s∈A} x^{s}} .

Integrating both sides of the above equation with respect to y, from 0 to z, we obtain

∑_{n≥1} (∑_{k≥1} \frac{c_{A}^{L}(n; k)}{k}z^{k}) x^{n} = ∫_{0}^{z} \frac{∑_{s∈A} x^{s}}{1 − y ∑_{s∈A} x^{s}} dy = − log (1 − z ∑_{s∈A} x^{s}) .

Setting z = 1 in the above equations and differentiating with respect to x, we get

∑_{n≥1} g_{A}(n)x^{n−1} = \frac{d}{dx} [− log (1 − ∑_{s∈A} x^{s})] = \frac{∑_{s∈A} sx^{s−1}}{1 − ∑_{s∈A} x^{s}} .  (21)

(Note that we have used the fact that c_{A}^{L}(n; k) = 0 for k > n.) This proves equation (7). Also,

(∑_{n≥1} g_{A}(n)x^{n}) (1 − ∑_{s≥1} I(s ∈ A)x^{s}) = ∑_{s≥1} sI(s ∈ A)x^{s}.

Multiplying the two power series on the left-hand side of the above equation, and equating coefficients of x^{s} from the resulting equality, we get

g_{A}(s) − ∑_{t=1}^{s−1} g_{A}(t)I(s − t ∈ A) = sI(s ∈ A),

and this proves equation (8).

Finally, we know from Beck and Robbins [4] and Moser and Whitney [18] that the generating function of the numbers c_{A}^{L}(n) is

C_{A}^{L}(x) = 1 + ∑_{n≥1} c_{A}^{L}(n) x^{n} = \frac{1}{1 − ∑_{s∈A} x^{m}} .  (22)

This of course follows from equation (20) by setting y = 1, i.e.,

C_{A}^{L}(x) = C_{A}^{L}(x, y = 1).

Using then equation (7), we obtain

(∑_{s≥1} s I(s ∈ A) x^{s}) (1 + ∑_{n≥1} c_{A}^{L}(n) x^{n}) = ∑_{n≥1} g_{A}(n) x^{n},

from which we can easily prove equation (9).

Proof of Corollary 4. Using Theorem 1, we have

∑_{n≥1} c_{A}^{R}(n)x^{n} = ∑_{n≥1} \frac{1}{n} ∑_{d|n} ϕ(d)g_{A} (\frac{n}{d}) x^{n}.

We want to change the order of summation in the right-hand side of the above equation. We let n = td, and then we have

∑_{n≥1} c_{A}^{R}(n)x^{n} = ∑_{d≥1} ∑_{t≥1} \frac{ϕ(d)}{td}g_{A}(t)x^{td} = ∑_{d≥1} \frac{ϕ(d)}{d} ∑_{t≥1} \frac{g_{A}(t)}{t}(x^{d})^{t}.  (23)

Integrating both sides of the first equation in (21) from x = 0 to x = z, we obtain

∑_{n≥1} \frac{g_{A}(n)}{n}z^{n} = − log (1 − ∑_{s∈A} z^{s}) = log \frac{1}{1 − ∑_{s∈A} z^{s}} .  (24)

Letting z = x^{d}, it then follows from equations (23) and (24) that

∑_{n≥1} c_{A}^{R}(n)x^{n} = ∑_{d≥1} \frac{ϕ(d)}{d} log \frac{1}{1 − ∑_{s∈A} x^{sd}} ,

and this completes the proof of the corollary.

Proof of Corollary 6. We note that equation (8) in Lemma 2 implies

g_{A}(n) = ∑_{s=1}^{n−1} g_{A}(s)I(r ∤ n − s) + nI(r ∤ n).

Note that r ∤ n − s if and only if r ∤ n − r − s, and r ∤ n if and only if r ∤ n − r. Thus, for n > r,

g_{A}(n) = ∑_{s=n−r+1}^{n−1} g_{A}(s) + ∑_{s=1}^{n−r−1} g_{A}(s)I(r ∤ n − r − s)
+(n − r)I(r ∤ n − r) + rI(r ∤ n)
= ∑_{s=n−r+1}^{n−1} g_{A}(s) + g_{A}(n − r) + rI(r ∤ n)

= ∑_{s=n−r}^{n−1} g_{A}(s) + rI(r ∤ n).

It is then easy to prove that, for n > r,

g_{A}(n) + rI(r|n) = ∑_{s=n−r}^{n−1}[g_{A}(s) + rI(r|s)],

i.e., the sequence of numbers (g_{A}(n)+rI(r|n) : n ∈ ℤ_{>0}) satisfies the same recurrence as the r-step Lucas numbers described by equations (11) and (12). In addition, if 1 ≤ k ≤ n ≤ r, then

c_{A}^{L}(n; k) = c_{ℤ_{>0}}^{L}(n; k) = \binom{n − 1}{k − 1}

except when n = r and k = 1, in which case, c_{A}^{L}(r; 1) = 0. It follows from equation (15) that

g_{A}(n) = 2^{n} − 1 − rI(r|n) = L_{n}^{(r)} − rI(r|n) for n = 1, 2, …, r.

Therefore, g_{A}(n) = L_{n}^{(r)} − rI(r|n) for all n ∈ ℤ_{>0}.

Proof of Theorem 7. The equality

ρ_{n}^{(r)} = \frac{1}{n} ∑_{d|n} ϕ (\frac{n}{d}) L_{d}^{(r)},

where ρ_{n}^{(r)} is the number of cyclic 0-1 sequences of length n that do not contain r consecutive 1’s, has been proven in Zhang and Hadjicostas [26].

The first equality in (13) follows from Theorem 1, Corollary 6, and the fact that

\frac{r}{n} ∑_{d|n} ϕ (\frac{n}{d}) I(r|d) = I(r|n).  (25)

We leave it to the reader to prove equation (25).

Proof of Corollary 9. When 1 ≤ n ≤ m − 1, we have c_{A}^{L}(n) = c_{ℤ_{>0}}^{L}(n) = 2^{n−1}, which is the total number of linear compositions of n (of any length) with parts in the set of positive integers. It then follows from equation (9) that

g_{A}(n) = ∑_{s=1}^{n−1} s 2^{n−s−1} + n = 2^{n} − 1.

When n = m, we have

g_{A}(m) = ∑_{i=1}^{m−1} s 2^{m−s−1} + 0 = 2^{m} − m − 1.

For m + 1 ≤ n ≤ r, the equation

g_{A}(n) = ∑_{{i=1 \atop i≠m}}^{n−1} g_{A}(n − i) + n

follows immediately from equation (8).

When n > r, equation (8) implies

g_{A}(n) = ∑_{s=n−r}^{n−1} g_{A}(s)I(n − s ∈ A) + ∑_{s=1}^{n−r−1} g_{A}(s)I(n − r − s ∈ A)
+(n − r)I(n − r ∈ A) + rI(n ∈ A)

because x ∈ A if and only x − r ∈ A for x > r. Thus, for n > r, by applying equation (8) again for n − r rather than n, we get

g_{A}(n) = ∑_{{s=n−r+1 \atop s≠n−m}}^{n−1} g_{A}(s) + 2g_{A}(n − r) + rI(n ∈ A)

= ∑_{{s=1 \atop s≠m}}^{r−1} g_{A}(n − s) + 2g_{A}(n − r) + rI[n ≢ m (mod r)],

and this completes the proof of the corollary.

4 Examples

In this section, we illustrate the results of the paper for the cases m = 0 < r = 2 and m = 1 < r = 2, i.e., when A consists of the positive odd integers and the positive even integers, respectively. Instead of using the subscript A for the quantities c_{A}^{L}(n), g_{A}(n) and c_{A}^{R}(n), we use the subscript ‘2, 0’ for the first case and the subscript ‘2, 1’ for the second case. Values of these three quantities for each of the two cases are given in Table 1 from n = 1 to n = 20.

The generating functions of the three quantities when A is the set of all odd positive integers are

1 + ∑_{n≥1} c_{2,0}^{L}(n)x^{n} = \frac{1 − x^{2}}{1 − x − x^{2}} ,

∑_{n≥1} g_{2,0}(n)x^{n} = \frac{x(x^{2} + 1)}{(1 − x − x^{2})(1 − x^{2})},

∑_{n≥1} c_{2,0}^{R}(n)x^{n} = ∑_{n≥1} \frac{ϕ(n)}{n} log \frac{1 − x^{2n}}{1 − x^{n} − x^{2n}} .

The generating functions of the three quantities when A is the set of all even positive

\begin{matrix}n & c_{2,0}^{L}(n) & c_{2,1}^{L}(n) & g_{2,0}(n) & g_{2,1}(n) & c_{2,0}^{R}(n) & c_{2,1}^{R}(n) \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ 2 & 1 & 1 & 1 & 2 & 1 & 1 \\ 3 & 2 & 0 & 4 & 0 & 2 & 0 \\ 4 & 3 & 2 & 5 & 6 & 2 & 2 \\ 5 & 5 & 0 & 11 & 0 & 3 & 0 \\ 6 & 8 & 4 & 16 & 14 & 4 & 3 \\ 7 & 13 & 0 & 29 & 0 & 5 & 0 \\ 8 & 21 & 8 & 45 & 30 & 7 & 5 \\ 9 & 34 & 0 & 76 & 0 & 10 & 0 \\ 10 & 55 & 16 & 121 & 62 & 14 & 7 \\ 11 & 89 & 0 & 199 & 0 & 19 & 0 \\ 12 & 144 & 32 & 320 & 126 & 30 & 13 \\ 13 & 233 & 0 & 521 & 0 & 41 & 0 \\ 14 & 377 & 64 & 841 & 254 & 63 & 19 \\ 15 & 610 & 0 & 1364 & 0 & 94 & 0 \\ 16 & 987 & 128 & 2205 & 510 & 142 & 35 \\ 17 & 1597 & 0 & 3571 & 0 & 211 & 0 \\ 18 & 2584 & 256 & 5776 & 1022 & 328 & 59 \\ 19 & 4181 & 0 & 9349 & 0 & 493 & 0 \\ 20 & 6765 & 512 & 15125 & 2046 & 765 & 107 \end{matrix}

Table 1: Evaluations of various sequences for the cases m = 0 < r = 2 and m = 1 < r = 2.

integers are

1 + ∑_{n≥1} c_{2,1}^{L}(n)x^{n} = \frac{1 − x^{2}}{1 − 2x^{2}} ,

∑_{n≥1} g_{2,1}(n)x^{n} = \frac{2x^{2}}{(1 − 2x^{2})(1 − x^{2})},

∑_{n≥1} c_{2,1}^{R}(n)x^{n} = ∑_{n≥1} \frac{ϕ(n)}{n} log \frac{1 − x^{2n}}{1 − 2x^{2n}} .

By using a symbolic computation package that has calculus and number theory capabilities, one can expand the above six generating functions around x = 0 far enough in order to obtain the results in Table 1.

Alternatively, we can find recurrences for the first two quantities in each case. For the first case:

c_{2,0}^{L}(1) = c_{2,0}^{L}(2) = 1,
c_{2,0}^{L}(n) = c_{2,0}^{L}(n − 1) + c_{2,0}^{L}(n − 2) for n > 2;
g_{2,0}(1) = 1, g_{2,0}(2) = 1,
g_{2,0}(n) = g_{2,0}(n − 1) + g_{2,1}(n − 2) + 2I(2 ∤ n) for n > 2.

Of course the sequence (c_{2,0}^{L}(n) : n ∈ ℤ_{>0}) is the classical Fibonacci sequence, while the sequence (g_{2,0}(n) : n ∈ ℤ_{>0}) satisfies

g_{2,0}(n) = L_{n}^{(2)} − 2I(2|n) = L_{n}^{(2)} − [1 + (−1)^{n}] for all n ∈ ℤ_{>0},

and it is given by \underline{A001350}. These numbers are called “associate Mersenne numbers” by Haselgrove [10] in an article that he published in 1949 in the Cambridge University Mathematics Society magazine Eureka. (It is actually one of three sequences that he calls like that.) The sequence (c_{2,0}^{R}(n) : n ∈ ℤ_{n>0}) can be calculated through equations (13) and it appears in \underline{A032189}.

For the second case, using Theorem 8 and Corollary 9, we find

c_{2,1}^{L}(1) = 0, c_{2,1}^{L}(2) = 1,
c_{2,1}^{L}(n) = 2c_{2,1}^{L}(n − 2) for n > 2;
g_{2,1}(1) = 0, g_{2,1}(2) = 2,
g_{2,1}(n) = 2g_{2,1}(n − 2) + 2I(2 | n) for n > 2.

In this case, it is easy to prove that for all n ≥ 1:

c_{2,1}^{L}(n) = 2^{\frac{n}{2} −1} I(2|n) and g_{2,1}(n) = (2^{\frac{n}{2} +1} − 2) I(2|n).

The sequence (c_{2,1}^{R}(n) : n ∈ ℤ_{n>0}) can be calculated through equation (5). Obviously, c_{2,1}^{R}(2n − 1) = 0 for n ∈ ℤ_{>0}, while the sequence (c_{2,1}^{R}(2n) : n ∈ ℤ_{n>0}) appears in \underline{A008965}.

5 Concluding remarks

The various r-step Lucas numbers L_{n}^{(r)}, defined by equations (11) and (12), have been studied extensively and satisfy various combinatorial identities involving binomial coefficients; e.g., see Charalambides [6]. When A is the set of all positive integers that are not multiples of a positive integer r, we managed to express c_{A}^{R}(n) in terms of L_{n}^{(r)} through equation (13) in Theorem 7. It would be nice to find a similar elegant equality for the numbers c_{A}^{R}(n) in terms of well-studied sequences of integers for the case

A = ℤ_{>0} − {m + jr : j ∈ ℤ_{>0}}

when r, m ∈ ℤ_{>0} with 1 ≤ m < r.

Finally, it would be nice to find a simple and elegant combinatorial argument to prove

c_{A}^{R}(n) = −I(r|n) + ρ_{n}^{(r)}

when A = ℤ_{>0} − {rj : j ∈ ℤ_{>0}}. Is there a ‘quasi-bijection’ between the number of cyclic compositions of n that are not multiples of r with the number of cyclic 0-1 sequences of length n that do not contain r consecutive 1s?

6 Acknowledgement

The author wishes to thank statistician Lingyun Zhang whose ideas and work have inspired this paper.

References

[1] The On-Line Encyclopedia of Integer Sequences, 2016, available at http://oeis.org.

[2] E. Akin and M. Davis, Bulgarian solitaire, Amer. Math. Monthly 92 (1985), 237–250.

[3] T. M. Apostol, Introduction to Analytic Number Theory, Springer, 2010.

[4] M. Beck and N. Robbins, Variations on a generating-function theme: enumerating compositions with parts avoiding an arithmetic sequence, Amer. Math. Monthly 122 (2015), 256–263.

[5] E. A. Bender, Möbius inversion counting, in K. H. Rosen, J. G. Michaels, J. L. Gross, J. W. Grossman, and D. R. Shier, eds., Handbook of Discrete and Combinatorial Mathematics, CRC Press, 2000, pp. 127–129.

[6] Ch. A. Charalambides, Lucas numbers and polynomials of order k and the length of the longest circular success run, Fibonacci Quart. 29 (1991), 290–297.

[7] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009.

[8] P. Flajolet and M. Soria, The cycle construction, SIAM J. Discrete Math. 4 (1991), 58–60.

[9] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1989.

[10] C. B. Haselgrove, A note on Fermat’s last theorem and the Mersenne numbers, Eureka 11 (1949), 19–22.

[11] S. Heubach and T. Mansour, Compositions of n with parts in a set, Congr. Numer. 168 (2004), 127–143.

[12] S. Heubach and T. Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.

[13] V. E. Hoggatt, Jr., and D. A. Lind, Fibonacci and binomial properties of weighted compositions, J. Combin. Theory 4 (1968), 121–124.

[14] A. Knopfmacher and N. Robbins, Some properties of cyclic compositions, Fibonacci Quart. 48 (2010), 249–255.

[15] P. A. MacMahon, Application of a theory of permutations in circular procession to the theory of numbers, Proc. London Math. Soc. 23 (1892), 305–313.

[16] P. A. MacMahon, Memoir on the theory of the compositions of numbers, Philos. Trans. Roy. Soc. London A 184 (1893), 835–901.

[17] E. P. Miles, Jr., Generalized Fibonacci numbers and associated matrices, Amer. Math. Monthly 67 (1960), 745–752.

[18] L. Moser and E. L. Whitney, Weighted compositions, Canad. Math. Bull. 4 (1961), 39–43.

[19] T. D. Noe, and J. Vos Post, Primes in Fibonacci n-step and Lucas n-step sequences, J. Integer Sequences 8 (2005), Article 05.4.4.

[20] R. Razen, J. Seberry, and K. Wehrhahn, Ordered partitions and codes generated by circulant matrices, J. Combin. Theory Ser. A 27 (1979), 333–341.

[21] N. Robbins, On Tribonacci numbers and 3-regular compositions, Fibonacci Quart. 52 (2014), 16–19.

[22] N. Robbins, On r-regular compositions, J. Comb. Math. Combin. Comput. 96 (2016), 195-199.

[23] D. Y. M. Sommerville, On certain periodic properties of cyclic compositions of integers, Proc. London Math. Soc. Ser. 2 7 (1908), 263–313.

[24] K. H. Wehrhahn, Combinatorics: An Introduction, 2nd ed., Carslaw Publications, 1992.

[25] N. Zagaglia Salvi, Ordered partitions and colourings of cycles and necklaces, Bull. Inst. Combin. Appl. 27 (1999), 37–40.

[26] L. Zhang and P. Hadjicostas, On sequences of independent Bernoulli trials avoiding the pattern “11...1”, Math. Scientist 40 (2015), 89–96.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 11B39. Keywords: cyclic composition, Euler’s totient function, generalized Lucas number, generating function.

(Concerned with sequences \underline{A000032}, \underline{A000073}, \underline{A000078}, \underline{A000358}, \underline{A001350}, \underline{A001590}, \underline{A001631}, \underline{A001644}, \underline{A008965}, \underline{A032189}, \underline{A037306}, \underline{A073817}, and \underline{A093305}.)

Received June 18 2016; revised version received October 8 2016. Published in Journal of Integer Sequences, October 10 2016.

Return to Journal of Integer Sequences home page.