Aperiodic Compositions and Classical Integer Sequences

Margherita Maria Ferrari and Norma Zagaglia Salvi^{∗} Department of Mathematics Politecnico di Milano Milano, 20133 Italy

               margheritamaria.ferrari@polimi.it
                   norma.zagaglia@polimi.it

Abstract In this paper we define the notion of singular composition of a positive integer. We provide a characterization of these compositions, together with methods for decomposing and also extending a singular composition in terms of other singular compositions. Consecutive extensions of particular compositions determine sequences of integers which coincide with classical integer sequences involving Fibonacci and Lucas numbers.

1 Introduction

Let k, n be integers where 1 ≤ k ≤ n, and let α = (a_{1}, a_{2}, …, a_{k}) denote a composition of n into k parts [3]. We call α (h, i)-singular if

(a_{1}, a_{2}, …, a_{i} + a_{i+1}, …, a_{k}) = (a_{1+h}, a_{2+h}, …, a_{i+h} + a_{i+1+h}, …, a_{k+h}),  (1)

where 1 ≤ h ≤ k − 1, 1 ≤ i ≤ k and the indices are modulo k. Note that shifting a (h, i)- singular composition of one position to the right, we obtain a (h, i+1)-singular composition. Consequently, the choice of a single index i is sufficient for identifying such compositions.

∗ Work partially supported by MIUR (Ministero dell’Istruzione, dell’Università e della Ricerca).

Thus we fix i = 1 and we call the composition α = (a_{1}, a_{2}, …, a_{k}) h-singular if

(a_{1} + a_{2}, a_{3}, …, a_{k}) = (a_{1+h} + a_{2+h}, a_{3+h}, …, a_{k+h}).  (2)

A k-composition of n is singular when it is h-singular for a suitable value of 1 ≤ h ≤ k−1.

Example 1. The 5-composition (1, 2, 2, 1, 2) of n = 8 is 2-singular.

Kramer [2] used singular compositions in order to define the middle levels partition graph of n.

The concatenation of the compositions α = (a_{1}, a_{2}, …, a_{k}) and β = (b_{1}, b_{2}, …, b_{h}) of the positive integers n and m respectively is the composition αβ = (a_{1}, a_{2}, …, a_{k}, b_{1}, b_{2}, …, b_{h}) of n + m. We let α^{i} denote the concatenation of α with itself i times. A composition α is periodic if α = π^{j}, where 1 < j ≤ k and π is a suitable composition.

Fibonacci and Lucas numbers will appear in some of our results. Recall that the Fibonacci sequence (F_{n})_{n≥0} is defined by setting F_{0} = 0, F_{1} = 1 and F_{n} = F_{n−1} + F_{n−2}, for n ≥ 2. The Lucas sequence (L_{n})_{n≥0} is defined by setting L_{0} = 2, L_{1} = 1 and L_{n} = L_{n−1} + L_{n−2}, for n ≥ 2.

The paper is outlined as follows. In Section 2 we determine a characterization of aperiodic singular compositions which allows us to obtain a method for constructing such compositions (Theorem 11). In Section 3 we study decompositions (Theorem 14) and also extensions (Theorem 18) of a singular composition in terms of other singular compositions. In Section 4 we prove that consecutive extensions of particular compositions determine sequences of integers which coincide with classical sequences involving Fibonacci and Lucas numbers. We conclude the paper by posing a more general definition of singular composition together with an open problem.

2 A characterization of singular compositions

Let α be an h-singular k-composition of n; from (2) it follows that (a_{3}, …, a_{k}) = (a_{3+h}, …, a_{k+h}).

This equality determines the function f_{h} : {3, 4, …, k} → {3 + h, 4 + h, …, k + h} on the indices of the elements of previous sequences such that

f_{h}(i) = i + h,

where 3 ≤ i ≤ k and the integers are modulo k. We may represent f_{h} in two-line notation

(\begin{matrix}3 4 ⋯ k \\ 3 + h 4 + h ⋯ k + h \end{matrix}) .  (3)

Note that the second line is obtained by shifting of h positions to the left the elements of the sequence (1, 2, 3, 4, …, k) and ignoring the first two elements 1+h and 2+h. A consequence is that the elements 1 and 2, which do not belong to the first line, belong to the second one, except for h = 1 and h = k − 1. Indeed for h = 1 the second line contains 1, but not 2; for h = k − 1 the second line contains 2, but not 1. In a similar way, the elements 1 + h and 2 + h do not belong to the second line while they belong to the first one, except for h = 1 and h = k − 1.

Proposition 2. An h-singular k-composition of n, where h and k are not coprime, is periodic.

Proof. Let gcd(k, h) = t > 1, where h = th′, k = tk′ and gcd(k′, h′) = 1. Note that the sets H_{i} = {i, i+h, …, i+(k′−1)h}, 1 ≤ i ≤ t, determine a partition of the set [k]. Then, for an hsingular k-composition α = (a_{1}, a_{2}, …, a_{k}), the elements of the sets {a_{i}, a_{i+h}, …, a_{i+(k′−1)h}}, 1 ≤ i ≤ t, coincide and α turns out to be the concatenation (a_{1}, a_{2}, …, a_{t})^{k′}.

Throughout the paper we consider only aperiodic compositions.

Beggas et al. [1] proved that a particular bijection, called widened permutation, between two n-sets having n − 1 elements in common has a decomposition into a linear order and a possible permutation. In this case we have a similar function in which the two sets have n − 2 elements in common, but for h = 1 and h = k − 1.

Lemma 3. Let h, k be coprime integers, where 1 ≤ h ≤ k − 1. The function f_{h} does not contain cycles.

Proof. By way of contradiction we assume there is a cycle

C = (d, d + h, …, d + (r − 1)h),

where 1 ≤ d ≤ k and d + rh ≡ d (mod k). This means that rh ≡ 0 (mod k) and therefore k divides rh. Then, because gcd(k, h) = 1, k divides r. The unique possibility is r = k; so the cycle contains all the elements. But this implies the impossible condition that also every line of (3) contains all the elements.

Theorem 4. Let h, k be coprime integers, where 1 ≤ h ≤ k − 1. The function f_{h} is decomposed into the linear orders:

1.

E_{h} = (1 + h, 1 + 2h, …, 1 + rh)  (4)

and

F_{h} = (2 + h, 2 + 2h, …, 2 + sh),  (5)

where r = h^{−1}, s = (k − 1)h^{−1} in ℤ_{k}, for h ≠ 1, k − 1;

2. E_{1} = (2) and F_{1} = (3, 4, …, k, 1), for h = 1;

3. E_{k−1} = (k, k − 1, …, 2) and F_{k−1} = (1), for h = k − 1.

Proof. Let h ≠ 1, k−1. Starting from 1+h we obtain the sequence (1+h, 1+2h, …, 1+rh = a), where a is one of the two elements which are in the second but not in the first line. So we have either a = 1 or a = 2. If a = 1, we obtain the impossible relation rh ≡ 0 (mod k). If a = 2, we obtain rh ≡ 1 (mod k), which is satisfied for r = h^{−1} in ℤ_{k}. Now starting from 2 + h we obtain the sequence (2 + h, 2 + 2h, …, 2 + sh = b), where either b = 1 or b = 2. The unique possibility is b = 1, which holds for s = (k − 1)h^{−1} in ℤ_{k}. By Lemma 3 the function does not contain cycles; therefore it is decomposed into the previous linear orders.

Now let h = 1. The function f_{1} is decomposed into F_{1} = (3, 4, …, k, 1) and E_{1} = (2). In the case h = k − 1, f_{k−1} is decomposed into E_{k−1} = (k, k − 1, …, 2) and F_{k−1} = (1). This completes the proof of the theorem.

In the following we let E_{h} and F_{h} also denote the sets of the elements of the assigned linear orders.

Corollary 5. For every 1 ≤ h ≤ k −1 such that gcd(k, h) = 1, E_{h} ∪F_{h} = [k] and, for k > 2, | E_{h} |≠| F_{h} |.

Proof. If k − h^{−1} = h^{−1}, then k = 2h^{−1} and kh = 2 in ℤ_{k}. This implies that 2 ≡ 0 (mod k), a contradiction for k > 2.

Lemma 6. Let h_{1}, h_{2} be two integers such that 1 ≤ h_{1} < h_{2} ≤ k − 1 and gcd(k, h_{1}) = gcd(k, h_{2}) = 1. Then E_{h_{1}} ≠ E_{h_{2}} and F_{h_{1}} ≠ F_{h_{2}}.

Proof. The cardinalities of E_{h_{1}} and E_{h_{2}} coincide with h_{1}^{−1} and h_{2}^{−1} in ℤ_{k} respectively. Because h_{1} < h_{2}, their inverses are distinct; then also the sets E_{h_{1}} and E_{h_{2}} are distinct. The same argument applies for F_{h_{1}} and F_{h_{2}}.

The following result is straightforward.

Corollary 7. If k is a prime integer, then all the sets E_{h} (respectively F_{h}), 1 ≤ h ≤ k − 1, are distinct.

Note that when k and h are coprime, then also k and k − h are coprime. In the following result we establish a relation between E_{k−h} (respectively F_{k−h}) and F_{h} (respectively E_{h}).

Proposition 8. For every 1 ≤ h ≤ ⌊\frac{k}{2}⌋ such that gcd(k, h) = 1, E_{k−h} = (F_{h} \ \{1\}) ∪ \{2\} and F_{k−h} = (E_{h} \ {2}) ∪ {1}.

Proof. The result is easy to prove for h = 1. Let h′ = k − h. Since gcd(k, h) = 1, then gcd(k, h′) = 1, E_{h′} = {1 + h′, 1 + 2h′, …, 1 + (r′ − 1)h′, 2} and F_{h′} = {2 + h′, 2 + 2h′, …, 2 + (s′ − 1)h′, 1}, where r′ = (h′)^{−1} and s′ = k − (h′)^{−1} in ℤ_{k}. Let s denote k − h^{−1} in ℤ_{k}; it follows that

1 + k − h ≡ 2 + (s − 1)h (mod k).

Then 1+2(k−h) ≡ 2+(s−2)h and so on until 1+(s−1)(k−h) ≡ 2+h and 1+s(k−h) ≡ 2 (mod k). Thus E_{k−h} = {2 + (s − 1)h, 2 + (s − 2)h, …, 2 + h, 2} = (F_{h} \ {1}) ∪ {2}.

Moreover, 2 + k − h ≡ 1 + (r − 1)h (mod k), where r = h^{−1} in ℤ_{k}; thus F_{k−h} = {1 + (r − 1)h, 1 + (r − 2)h, …, 1 + h, 1} = (E_{h} \ {2}) ∪ {1}.

Corollary 9. If α = (a_{1}, a_{2}, …, a_{k}) is an aperiodic h-singular k-composition of n, then every a_{i} is equal to a_{1} or a_{2}, 1 ≤ i ≤ k, as long as i ∈ F_{h} or i ∈ E_{h} respectively. Then a_{1} and a_{2} are distinct, and they satisfy the relation

(k − h^{−1})a_{1} + h^{−1}a_{2} = n.  (6)

Corollary 10. If an aperiodic composition contains more than two distinct elements, then it is not singular.

Previous results allow us to give a characterization of singular compositions, which turns out to be a method for their construction.

Theorem 11. Let h, k, n be positive integers such that 1 ≤ h < k ≤ n and gcd(k, h) = 1. An aperiodic k-composition α = (a_{1}, a_{2}, …, a_{k}) is h-singular if and only if a_{1} ≠ a_{2} and the pair of elements (a_{1}, a_{2}) is a solution of the equation

(k − h^{−1})x_{1} + h^{−1}x_{2} = n,  (7)

where h^{−1}, k−h^{−1} ∈ ℤ_{k}, and each a_{i} coincides with a_{1} or a_{2} for i ∈ F_{h} or i ∈ E_{h} respectively.

Proof. If α is h-singular, then by Corollary 9 the property holds. Now let us assume that the pair of distinct integers (a_{1}, a_{2}) is solution of the equation (7) and each a_{i} coincides with a_{1} or a_{2} for i ∈ F_{h} or i ∈ E_{h} respectively. Hence, for h ≠ 1, k − 1, the composition α = (a_{1}, a_{2}, …, a_{k}) which has the elements a_{1} and a_{2} in the positions given by (5) and (4) respectively, is h-singular. Lastly, if h = 1, α = (a_{1}, a_{2}, a_{1}, …, a_{1}) is 1-singular, while if h = k − 1, α = (a_{1}, a_{2}, …, a_{2}) is (k − 1)-singular.

Example 12. The list of h-singular 9-compositions with a_{1} = 1 and a_{2} = 2 is

1. for h = 1, α_{1} = (1, 2, 1, 1, 1, 1, 1, 1, 1);

2. for h = 2, α_{2} = (1, 2, 2, 1, 2, 1, 2, 1, 2);

3. for h = 4, α_{4} = (1, 2, 2, 2, 2, 1, 2, 2, 2);

4. for h = 5, α_{5} = (1, 2, 1, 1, 1, 2, 1, 1, 1);

5. for h = 7, α_{7} = (1, 2, 1, 2, 1, 2, 1, 2, 1);

6. for h = 8, α_{8} = (1, 2, 2, 2, 2, 2, 2, 2, 2)

where the corresponding integers are n_{1} = 10, n_{2} = 14, n_{4} = 16, n_{5} = 11, n_{7} = 13 and n_{8} = 17. Note that the compositions α_{5}, α_{7} and α_{8} are obtained from α_{4}, α_{2} and α_{1} respectively, by exchanging 1 with 2 after the first two positions.

Let α = (a_{1}, a_{2}, …, a_{k}) be an h-singular composition. By Proposition 8, it follows that by exchanging a_{1} and a_{2} after the first two positions, we obtain a (k − h)-singular composition. We now prove that by exchanging only the first two elements we obtain again a (k − h)- singular composition.

Proposition 13. Let α = (a_{1}, a_{2}, …, a_{k}) be an aperiodic h-singular composition of n, where 1 ≤ h ≤ k − 1. Then α^{∗} = (a_{2}, a_{1}, a_{3}, …, a_{k}) is a (k − h)-singular composition of n, obtained from α by rotation.

Proof. Consider the composition α^{∗} = (a_{1}^{∗}, a_{2}^{∗}, …, a_{k}^{∗}) = (a_{2}, a_{1}, a_{3}, …, a_{k}) of n. The set E^{∗} of indices of the elements equal to a_{2}^{∗} in α^{∗} satisfies E^{∗} = (F_{h}\{1})∪{2} = E_{k−h} (Proposition 8). The same relation holds for F^{∗} = F_{k−h}, where F^{∗} is the set of indices of the elements equal to a_{1}^{∗} in α^{∗}. Then α^{∗} is a (k − h)-singular composition of n. Note that the composition α′ = (a_{1+h}, a_{2+h}, …, a_{k}, a_{1}, …, a_{h}) is (k − h)-singular and is obtained from α by rotation. Moreover a_{2} = a_{1+h} and a_{1} = a_{2+h}. Since the first two elements of α^{∗} coincide with the first two of α′ and both the compositions are (k − h)-singular, E^{∗} = E′ and F^{∗} = F′. Thus α^{∗} = α′, and the result follows.

3 Decompositions and extensions

In this section we investigate two decompositions and some extensions of an aperiodic singular composition.

Theorem 14. Let α = (a_{1}, a_{2}, …, a_{k}) be an aperiodic h-singular k-composition of n, where k = hq + r and 1 ≤ r < h. Then α = λμλ ⋯ λ, where λ = (a_{1}, a_{2}, …, a_{h}), μ is the sequence of the last r elements of λ and q is the multiplicity of λ. Moreover λ is a (h − r)-singular h-composition of a_{1} + ⋯ + a_{h}.

Proof. Since α is h-singular, the sequences β = (a_{1} + a_{2}, a_{3}, …, a_{k}) and γ = (a_{1+h} + a_{2+h}, a_{3+h}, …, a_{k+h}) coincide. In particular this holds for the subsequences β′ and γ′ obtained by deleting the first h − 1 elements of β and γ respectively. If 1 ≤ h ≤ ⌊\frac{k}{2}⌋, by comparing β′ = (a_{1+h}, a_{2+h}, …, a_{k}) and γ′ = (a_{1+2h}, a_{2+2h}, …, a_{k}, a_{1}, …, a_{h}) = (a_{1+2h}, …, a_{k})λ, where λ = (a_{1}, a_{2}, …, a_{h}), we obtain that the sequence (a_{k−(h−1)}, …, a_{k}) formed by the last h elements of β′ coincides with λ. Then the sequence of length h in γ′ which precedes the last subsequence λ coincides again with λ. We continue until we find a subsequence μ of length less than h in β′, which is formed by the last r elements of λ. Thus μ = (a_{h−(r−1)}, a_{h−(r−2)}, …, a_{h}). If ⌊\frac{k}{2}⌋ < h ≤ k − 1, by comparing β′ and γ′ = μ we obtain α = λμ. In both cases α = λμλ ⋯ λ, where λ occurs q times.

Let us assume that r > 1. Since α is h-singular, the sequence

(a_{1} + a_{2}, a_{3}, …, a_{h}, a_{h−(r−1)}, a_{h−(r−2)}, …, a_{h})λ^{q−1}

coincides with

(a_{h−(r−1)} + a_{h−(r−2)}, a_{h−(r−3)}, …, a_{h})λ^{q}.

Therefore the sequences of the first h − 1 elements coincide

(a_{1} + a_{2}, a_{3}, …, a_{h}) = (a_{h−(r−1)} + a_{h−(r−2)}, a_{h−(r−3)}, …, a_{h}, a_{1}, …, a_{h−r}).

Thus the composition λ is (h−r)-singular. A similar argument applies in the case r = 1.

Proposition 15. Let α = (a_{1}, a_{2}, …, a_{k}) be an aperiodic h-singular k-composition of n, where k = hq + r and 1 < r < h. Then α = σλ ⋯ λ, where λ = (a_{1}, a_{2}, …, a_{h}), σ = (a_{1}, a_{2}, …, a_{r}) and the multiplicity of λ is q. Moreover λ is a (h − r)-singular h-composition of a_{1} + ⋯ + a_{h}.

Proof. Let λ = (a_{1}, a_{2}, …, a_{h}) and σ = (a_{1}, a_{2}, …, a_{r}). By applying the same argument used in the proof of Theorem 14 to the subsequences obtained by deleting the first r − 1 elements of β and γ, the result follows.

Corollary 16. In the case of r = 1, there is not a decomposition α = σλλ ⋯ λ.

Proof. In the case of r = 1, σ is reduced to the element a_{1}. This implies the relation a_{1} + a_{2} = 2a_{1}; then a_{2} = a_{1}, a contradiction to the assumption that α is aperiodic.

Corollary 17. If k = hq + r and 1 < r < h, then σλ = λμ.

Now we investigate an operation which can be considered the inverse of the decomposition; namely we want to determine an extension of a singular composition which turns out to be again a singular composition.

Theorem 18. Let α be an aperiodic h-singular k-composition of n, and let ν denote the sequence formed by the last k − h elements of α. The k′-composition β = ανα ⋯ α, where k′ = kq′ + k − h and q′ is the multiplicity of α, is k-singular.

Proof. Let α = (a_{1}, a_{2}, …, a_{k}) be an aperiodic h-singular k-composition of n, where k > 2 and 1 ≤ h < k − 1. The composition β = ανα ⋯ α, where ν denotes the sequence formed by the last k − h elements of α, is k-singular if

(a_{1} + a_{2}, …, a_{k}, a_{1+h}, …, a_{k})α^{q′−1} = (a_{1+h} + a_{2+h}, …, a_{k})α^{q′}.

In order to prove the equality, it is sufficient to show that

(a_{1} + a_{2}, a_{3}, …, a_{k}, a_{1+h}, …, a_{k}) = (a_{1+h} + a_{2+h}, …, a_{k}, a_{1}, …, a_{k}).  (8)

Since α is h-singular, (a_{1} + a_{2}, a_{3}, …, a_{k}) = (a_{1+h} + a_{2+h}, …, a_{k}, a_{1}, …, a_{h}). Thus the left side of (8) coincides with (a_{1+h} + a_{2+h}, …, a_{k}, a_{1}, …, a_{h}, a_{1+h}, …, a_{k}) and the result follows. A similar argument applies in the cases k = 2 and h = k − 1.

4 Classical integer sequences

Let α be an h-singular k-composition of n. The composition β = ανα ⋯ α, where ν is the sequence formed by the last k − h elements of α and α is repeated q times, is called a qextension of α. By consecutive extensions, we determine a sequence of singular compositions and therefore a sequence of integers corresponding to the numbers of their parts.

4.1 Fibonacci sequences

Let us consider the h_{0}-singular k_{0}-composition α_{0} = (a, b), with a ≠ b, k_{0} = 2 and h_{0} = 1. The 2-extension of α_{0} is the h_{1}-singular k_{1}-composition α_{1} = α_{0}ν_{0}α_{0} = (a, b, b, a, b), where k_{1} = k_{0} · 2 + 1, h_{1} = k_{0} = 2 and ν_{0} is the composition formed by last (k_{0} − h_{0}) = 1 element of α_{0}. The consecutive 2-extension is the h_{2}-singular k_{2}-composition α_{2} = α_{1}ν_{1}α_{1} = (a, b, b, a, b, b, a, b, a, b, b, a, b), where k_{2} = k_{1} · 2 + 3, h_{2} = k_{1} and ν_{1} is the composition formed by last (k_{1} − h_{1}) = 3 elements of α_{1} and so on.

The first values of the sequence of the numbers (k_{n})_{n≥0} of parts of the 2-extensions of α_{0} are

2, 5, 13, 34, 89, 233, …

These numbers appear as the first integers, but the first two, in the sequence \underline{A001519} [4], which is obtained from the recursive relation

a_{n} = 3a_{n−1} − a_{n−2},  (9)

with the initial conditions a_{0} = 1, a_{1} = 1. We prove that the integers k_{n} satisfy the same recursive relation.

Lemma 19. The integers k_{n} of the parts of the 2-extensions of the 1-singular 2-composition (a, b), with a ≠ b, satisfy the recursive relation:

k_{n} = 3k_{n−1} − k_{n−2}

with the initial conditions k_{0} = 2, k_{1} = 5.

Proof. Recall that, by Theorem 18,

k_{n} = 2k_{n−1} + k_{n−1} − h_{n−1}.

Because h_{n−1} = k_{n−2}, the result follows.

The following corollary is straightforward.

Corollary 20. The integers h_{n} associated to the 2-extensions of the 1-singular 2-composition (a, b), with a ≠ b, satisfy the recursive relation:

h_{n} = 3h_{n−1} − h_{n−2}

with the initial conditions h_{0} = 1, h_{1} = 2.

It is easy to prove that the generating function of the sequence of the integers k_{n} is

\frac{2 − x}{1 − 3x + x^{2}} ,

and

k_{n} = \frac{2 + \sqrt{5}}{\sqrt{5}}(\frac{3 + \sqrt{5}}{2})^{n} + \frac{−2 + \sqrt{5}}{\sqrt{5}}(\frac{3 − \sqrt{5}}{2})^{n}.

Proposition 21. The sequence

k_{0}, k_{1} − h_{1}, k_{1}, k_{2} − h_{2}, k_{2}, k_{3} − h_{3}, …  (10)

coincides with the sequence of Fibonacci numbers F_{n}, with initial conditions F_{2} = 2, F_{3} = 3.

Proof. We have to prove that every element of (10) is the sum of the preceding two elements and the initial conditions coincide. For i ≥ 1, k_{i} = k_{i} − h_{i} + k_{i−1}, because h_{i} = k_{i−1}. Moreover, for i ≥ 2, k_{i} − h_{i} = k_{i−1} + k_{i−1} − h_{i−1} by Lemma 19. Because k_{0} = 2, k_{1} = 5 and h_{1} = 2, the initial conditions are 2 and 3, which coincide with F_{2} and F_{3} of the Fibonacci sequence \underline{A000045}.

Another consequence of Proposition 21 is that the elements k_{i}, i ≥ 0, form a bisection of the Fibonacci sequence; this result turns out to be one of the comments to \underline{A001519}.

By repeating the previous procedure for q > 2, we easily obtain a sequence satisfying the recursive relation

a_{n} = (q + 1)a_{n−1} − a_{n−2},

with the initial conditions a_{0} = 2, a_{1} = 2q + 1.

In the particular case of q = 3, we obtain the sequence whose first elements are

2, 7, 26, 97, …

which coincides with \underline{A001075}, but the first element.

Again, for q = 4 we obtain a sequence whose first elements are

2, 9, 43, 206, …

which coincides with \underline{A002310}, but the first element.

4.2 Lucas sequences

The first values of the sequence of the numbers (p_{n})_{n≥0} of parts of the 2-extensions of the 2-singular 3-composition (a, b, b), with a ≠ b, are

3, 7, 18, 47, 123, …

These integers coincide with the first integers, but the first one, of \underline{A005248}, which is obtained from the recursive relation (9), with the initial conditions a_{0} = 2, a_{1} = 3.

Using the same procedure of Lemma 19, the numbers p_{n} satisfy the same recursive relation with initial conditions p_{0} = 3 and p_{1} = 7. Moreover the generating function of the sequence of the integers p_{n} is

\frac{3 − 2x}{1 − 3x + x^{2}} ,

and

p_{n} = (\frac{3 + \sqrt{5}}{2})^{n+1} + (\frac{3 − \sqrt{5}}{2})^{n+1}.

Proposition 22. The sequence

h_{0}, p_{0} − h_{0}, p_{0}, p_{1} − h_{1}, p_{1}, p_{2} − h_{2}, p_{2}, p_{3} − h_{3}, …  (11)

coincides with the sequence of Lucas numbers L_{n}, with initial conditions L_{0} = 2, L_{1} = 1.

Another consequence of the previous result is that the elements p_{i}, i ≥ 0, form a bisection of the Lucas sequence \underline{A000032}, as noted in a comment to \underline{A005248}.

4.3 Other integer sequences

We now consider the sequence of the numbers (t_{n})_{n≥0} of parts of 2-extensions of the 3-singular 4-compositions (a, b, b, b), with a ≠ b, that is

4, 9, 23, 60, 157, …

This sequence, which is not contained in [4], satisfies the recursive relation (9), with initial conditions t_{0} = 4 and t_{1} = 9. The corresponding generating function is

\frac{4 − 3x}{1 − 3x + x^{2}} ,

and

t_{n} = \frac{3 + 2\sqrt{5}}{\sqrt{5}}(\frac{3 + \sqrt{5}}{2})^{n} + \frac{−3 + 2\sqrt{5}}{\sqrt{5}}(\frac{3 − \sqrt{5}}{2})^{n}.

By continuing, we may obtain other integer sequences by q-extension, with q ≥ 2, of the singular composition (a, b, …, b), where b occurs more than three times.

5 Conclusion

The notion of singular composition can be generalized as follows. We call the composition α = (a_{1}, a_{2}, …, a_{k}) (h, i, j)-singular, if

(a_{1}, a_{2}, …, a_{i−1}, a_{i} + a_{j}, a_{i+1}, …, a_{j−1}, a_{j+1}, …, a_{k}) =
= (a_{1+h}, a_{2+h}, …, a_{i−1+h}, a_{i+h} + a_{j+h}, a_{i+1+h}, …, a_{j−1+h}, a_{j+1+h}, …, a_{k+h}), (12)

where 1 ≤ h ≤ k − 1, 1 ≤ i < j ≤ k and the indices are modulo k.

This definition leads to compositions which can not be obtained from equation (1). In fact, (1, 1, 2, 2, 2) satisfies (a_{1} + a_{3}, a_{2}, a_{4}, a_{5}) = (a_{1+h} + a_{3+h}, a_{2+h}, a_{4+h}, a_{5+h}) for h = 4, but it does not satisfy any equation (1).

Thus this definition poses the problem to find necessary and sufficient conditions based on which a given aperiodic sequence with two distinct elements satisfies (12).

6 Acknowledgments

The authors thank the anonymous referee for his valuable suggestions which led to an improvement of the manuscript.

References

[1] F. Beggas, M. M. Ferrari, and N. Zagaglia Salvi, Combinatorial interpretations and enumeration of particular bijections, Riv. Mat. Univ. Parma 8 (2017). To appear.

[2] A.-V. Kramer, A particular Hamiltonian cycle on middle levels in the De Bruijn digraph, Discrete Math. 312 (2012), 608–613.

[3] J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958.

[4] N. J. A. Sloane, The on-line encyclopedia of integer sequences, 2017. Available at

    https://oeis.org.

2010 Mathematics Subject Classification: Primary 05A17; Secondary 11B39. Keywords: ordered partition, composition, singular composition, Fibonacci number, Lucas number.

(Concerned with sequences \underline{A000032}, \underline{A000045}, \underline{A001075}, \underline{A001519}, \underline{A002310}, and \underline{A005248}.)

Received April 20 2017; revised versions received May 11 2017; August 2 2017. Published in Journal of Integer Sequences, September 5 2017.

Return to Journal of Integer Sequences home page.