On Schreier-Type Sets, Partitions, and Compositions

Kevin Beanland Department of Mathematics Washington and Lee University Lexington, VA 24450 USA

                   beanlandk@wlu.edu

Hùng Vi{ê \atop .}t Chu Department of Mathematics Texas A&M University College Station, TX 77843 USA

                   hungchu1@tamu.edu

Abstract

For a fixed ℓ ∈ ℕ, a nonempty set A ⊂ ℕ is ℓ-strong Schreier if min A ≥ ℓ|A|−ℓ+1. We define a set of positive integers to be sparse if either the set has at most two numbers or the differences between consecutive numbers in increasing order are non-decreasing. We establish a connection between sparse Schreier-type sets and (restricted) partition numbers. One of our results states that if G_{n,ℓ} consists of partitions of n that contain no parts in {2, …, ℓ}, and we set

A_{n,ℓ} := {A ⊂ {1, …, n} : n ∈ A, A is sparse and ℓ-strong Schreier},

then

|A_{n,ℓ}| = |G_{n−1,ℓ}|, for all n, ℓ ∈ ℕ.

The special case G_{n−1,1} consists of all partitions of n − 1. Besides partitions, we also investigate integer compositions.

1 Introduction

Let ℕ denote the set of positive integers {1, 2, 3, …}. A set A ⊂ ℕ is said to be Schreier if either A is empty or min A ≥ |A|. Schreier sets are an important concept with many applications in Banach space theory [1, 10, 11]. These sets have also been studied as purely combinatorial objects in Ramsey theory [8]. In 2012, Bird [4] had a surprising observation that for every n ∈ ℕ, we have that

#{A ⊂ {1, …, n} : A is Schreier and n ∈ A} = F_{n},  (1)

where (F_{n})_{n≥1} is the Fibonacci sequence with F_{1} = F_{2} = 1 and F_{n} = F_{n−1} + F_{n−2} for n ≥ 3. Subsequent work has modified the Schreier condition or added extra conditions on the set A to discover many unexpected results. For example, counting Schreier sets that are an arithmetic progression gives the number of edges of the (modified) Turán graphs [2, 5]. Meanwhile, the general linear relation q min A ≥ p|A| gives a higher-order linear recurrence of depth p + q, where positive and negative terms alternate [2, 7]. Then several authors [6] generalized (1) to Schreier multisets and the s-step Fibonacci sequences and moreover, considered the nonlinear Schreier condition \sqrt[k]{min A} ≥ |A| for k ≥ 2. Recently, the first named author et al. [3] counted unions of Schreier sets and was able to describe linear recurrences using coefficients from a family of characteristic polynomials.

In this note, we introduce (strongly) sparse Schreier-type sets and connect them to integer partitions.

Definition 1. We call a set A = {a_{1}, …, a_{n}} ⊂ ℕ (a_{1} < ⋯ < a_{n}) sparse if either |A| ≤ 2 or

|A| ≥ 3 and a_{i} − a_{i−1} ≥ a_{i−1} − a_{i−2}, for 3 ≤ i ≤ n.

Furthermore, the set A is strongly sparse if either |A| ≤ 2 or

|A| ≥ 3 and a_{i} − a_{i−1} > a_{i−1} − a_{i−2}, for 3 ≤ i ≤ n.

With an abuse of notation, we may write a_{1} < a_{2} < ⋯ < a_{k} to mean the set {a_{1}, a_{2}, …, a_{k}} with the additional information about the ordering of elements in the set. For

F = a_{1} < ⋯ < a_{n} ⊂ ℕ with n ≥ 2,

we let

D(F) = {a_{2} − a_{1}, …, a_{n} − a_{n−1}},

which is a multiset. Our main results are motivated by the following proposition.

Proposition 2. Let m, n ∈ ℕ. Define

F_{n,m} = {F ⊂ {1, …, n} : F is Schreier and sparse, n ∈ F, min F = m}.

Then for m ≤ n − 1,

|F_{n,m+1}| = p(n − 1, m),

where p(u, k) is the number of partitions of u into exactly k parts.

Proof. Let P (n − 1, m) consist of all partitions of n − 1 into exactly m parts. If m = n − 1, then |F_{n,m+1}| = p(n − 1, m) = 1. Assume n > m + 1. Define a function R on F ∈ F_{n,m+1} as

R(F) = \{\underbrace{m + 1, …, m + 1}_{m+1−|F |}\} ∪ F.

Note that R gives multisets. Since n > m + 1, each set F in F_{n,m+1} contains at least two numbers. Therefore, the map D can take R(F) as an input. Define S : F_{n,m+1} → P (n−1, m) as S(F) = D(R(F))+1. Here elements of the set D(R(F))+1 represent parts of a partition. We show that S is well-defined and bijective.

Let F ∈ F_{n,m+1}. Since min F = m+1 and max F = n, the sum of m numbers in D(R(F)) is n − m − 1. Therefore, the sum of m parts given by S(F) is (n − m − 1) + m = n − 1, thus S(F) ∈ P (n − 1, m), which shows that S is well-defined. Injectivity is obvious.

To see surjectivity, choose an arbitrary partition {n_{1} ≤ ⋯ ≤ n_{m}} of n − 1 with

n_{1} ≤ ⋯ ≤ n_{m}.

Let t be the smallest (if any) such that n_{t} ≥ 2. It is not hard to see that S(F) = {n_{1}, …, n_{m}}, where

F = {m + 1, m + 1 + (n_{t} − 1), …, m + 1 + ∑_{i=t}^{m}(n_{i} − 1)} ∈ F_{n,m+1}.

This completes the proof.

Corollary 3. For n ≥ 1, let

F_{n} = {F ⊂ {1, …, n} : F is Schreier and sparse, n ∈ F }.  (2)

It holds that |F_{n}| = p(n − 1), where p(u) is the partition number of u. Here p(0) = 1 by convention.

Corollary 3 shows a nice relation between Schreier-type sets and partition numbers, inspiring us to look at restricted partitions, where certain rules are applied to the parts in each partition. In particular, we are concerned with the following sequences \underline{A000009}, \underline{A000041}, \underline{A000070}, \underline{A002865}, \underline{A008483}, \underline{A008484}, \underline{A025147}, \underline{A025148}, \underline{A025149}, \underline{A025150}, \underline{A025151}, \underline{A027336}, \underline{A036469}, \underline{A038348}, \underline{A185325} in the On-Line Encyclopedia of Integer Sequences (OEIS) [12].

Definition 4. For ℓ ∈ ℕ_{≥0}, a finite set A ⊂ ℕ is said to be ℓ-strong Schreier if either A = ∅ or

min A ≥ ℓ|A| − ℓ + 1.

Remark 5. This definition is natural in the sense that all finite subsets of ℕ are 0-strong Schreier. If ℓ ≥ k, an ℓ-strong Schreier set is k-strong Schreier, and when ℓ = 1, the 1-strong Schreier property is the same as the Schreier property. All sets of size 1 (singleton) are ℓ-strong Schreier for all ℓ.

For n ≥ 1 and ℓ ≥ 0, we define the objects to be studied

• A_{n,ℓ} := {A ⊂ {1, …, n} : n ∈ A, A is sparse and ℓ-strong Schreier},

• A_{n,ℓ}^{s} := {A ⊂ {1, …, n} : n ∈ A, A is strongly sparse and ℓ-strong Schreier},

• E_{n,ℓ}: the set of partitions of n into parts which are at least ℓ, and

• E_{n,ℓ}^{d}: the set of partitions of n into distinct parts, each of which is at least ℓ. By convention, we have |E_{0,ℓ}| = |E_{0,ℓ}^{d}| = 1. For reference, we include tables for initial values of |A_{n,ℓ}|, |A_{n,ℓ}^{s}|, |E_{n,ℓ}|, and |E_{n,ℓ}^{d}| in Section 4. Theorem 6. The following identities hold

|A_{n,ℓ}| = ∑_{i=0}^{n−1} |E_{i,ℓ+1}|, for all n ≥ 1 and ℓ ≥ 0, and  (3)
|A_{n,ℓ}^{s}| = ∑_{i=0}^{n−1} |E_{i,ℓ+1}^{d}|, for all n ≥ 1 and ℓ ≥ 0.  (4)

Thanks to Theorem 6, we obtain the next theorem, whose short proof utilizes generating functions. For ℓ ≥ 0, define

• G_{n,ℓ} to consist of partitions of n, which have no parts in {2, …, ℓ}, and

• H_{n,ℓ} to consist of partitions of n, which has no parts in {2, …, ℓ} and no even parts

greater than 2ℓ. Here when ℓ ≤ 1, we let {2, …, ℓ} = ∅. By convention, |G_{0,ℓ}| = |H_{0,ℓ}| = 1. Section 4 contains instances of |G_{n,ℓ}| and |H_{n,ℓ}|. Theorem 7. For all n, ℓ ∈ ℕ, we have

|A_{n,ℓ}| = |G_{n−1,ℓ}| and  (5)
|A_{n,ℓ}^{s}| = |H_{n−1,ℓ}|.  (6)

Remark 8. Note that (|G_{n,1})_{n=0}^{∞} is the sequence of partition numbers. In this case, (5) is the same as Corollary 3. The sequence (|H_{n,1}|)_{n=0}^{∞} counts partitions of n that contain no even parts except 2. Using generating functions, it is not hard to verify that (|H_{n,1}|)_{n=0}^{∞} is also equal to the number of partitions of n that contain at most one even part. This is the sequence \underline{A038348}. The two sequences (|H_{n,2}|)_{n=0}^{∞} and (|H_{n,3}|)_{n=0}^{∞} are new and not available in the OEIS at the time of this writing.

A surprising feature of the identities in Theorems 6 and 7 is that while the left side involves the ℓ-strong Schreier property, the right side cleanly counts partitions excluding certain parts. A natural approach to prove Theorems 6 and 7 is to “divide and conquer”. Specifically for (3), we may divide A_{n,ℓ} into n collections of sets based on their minimum and hope that the cardinality of each collection is equal to a corresponding summand on the right side. This approach works in the simplest case when ℓ = 0, but the naive division fails in general.

Similarly, we may attempt to prove (5) by grouping A_{n,ℓ} into sets having the same minimum, while dividing G_{n−1,ℓ} into groups of partitions having the same number of parts. This idea works when ℓ = 1 as we have seen in the proof of Proposition 2. However, the idea again fails for ℓ ≥ 2.

The above discussion suggests that to establish Theorems 6 and 7, we need a more clever way to divide and conquer, which we shall show in the next section.

We end this note with a result about compositions of positive integers. A composition of n is a way to write n as a sum of positive integers, and two sums whose terms are ordered differently constitute two different compositions. The definition of compositions is thus different from that of partitions, whose order of terms does not matter. We shall connect ℓ-strong Schreier sets to compositions by removing the sparse condition on sets in the definition of A_{n,ℓ}. For m, n ∈ ℕ and ℓ ≥ 0, define

B_{n,ℓ} = {B ⊂ {1, …, n} : n ∈ B, B is ℓ-strong Schreier} and
B_{n,ℓ,m} = {B ⊂ {1, …, n} : n ∈ B, |B| = m, B is ℓ-strong Schreier}.

Theorem 9. For m, n ∈ ℕ and ℓ ≥ 0,

|B_{n,ℓ,m}| = c(n + ℓ, ℓ + 1, m),

where c(u, v, s) is the number of compositions of u into exactly s parts, each of which is at least v. As a result,

|B_{n,ℓ}| = c(n + ℓ, ℓ + 1),

where c(u, v) counts compositions of u into parts that are at least v.

2 The ℓ-strong Schreier sets and partitions

We set up some notation to state a key lemma for the proof of Theorem 6. Choose n ≥ 1 and ℓ ≥ 0. Let E_{n,ℓ,k} consist of partitions in E_{n,ℓ} with exactly k parts. For k ≥ 2 and q ≥ 0, let E_{n,ℓ,k,q} be the collection of all partitions in E_{n,ℓ,k}, where the difference between the largest and the second largest parts is q.

Define the collection F_{n,ℓ} to consist of sets of positive integers A = {a_{1}, …, a_{p}, n + 1} such that

i) p ≥ 2, a_{1} < ⋯ < a_{p} < n + 1, ii) A is sparse and ℓ-strong Schreier, and

iii) n + 1 + a_{p−1} = 2a_{p}.

Note that F_{n,ℓ} = ∅ for all n ≤ 2ℓ + 1. The first n for which F_{n,ℓ} is nonempty is 2ℓ + 2; in fact, F_{2ℓ+2,ℓ} = {{2ℓ + 1, 2ℓ + 2, 2ℓ + 3}}.

Let F_{n,ℓ,k} be the collection of sets in F_{n,ℓ} with exactly k elements. Finally, for k, q ≥ 1, let F_{n,ℓ,k,q} consist of sets in F_{n,ℓ,k} with the smallest element equal to q.

Remark 10. By the definition of E_{n,ℓ+1}, for ℓ + 1 ≤ n ≤ 2ℓ + 1, we have |E_{n,ℓ+1}| = 1, as the only permissible partition of n is itself. When n = 2ℓ+2, we have two partitions in E_{2ℓ+2,ℓ+1}, which are 2ℓ + 2 and (ℓ + 1) + (ℓ + 1). This, along with the discussion after the definition of F_{n,ℓ}, makes us suspect that |F_{n,ℓ}| + 1 = |E_{n,ℓ+1}| for n ≥ ℓ + 1. Our first goal in this section is to establish this identity (see Corollary 13).

Lemma 11. For n ≥ ℓ + 1, k ≥ 2, and q ≥ 1, we have

|F_{n,ℓ,k+1,ℓk+q}| = |E_{n,ℓ+1,k,q−1}|.  (7)

Proof. Given a nonempty set A of natural numbers, we let

R(A) = (A\{max A}) ∪ {max A + q − 1}.

We define a bijective map S : F_{n,ℓ,k+1,ℓk+q} → E_{n,ℓ+1,k,q−1} as

S(F) = R(D(F) + ℓ).

We show that S is well-defined and bijective.

a) Let F ∈ F_{n,ℓ,k+1,ℓk+q}. The sum of k elements in D(F) is n+1−(ℓk+q). Hence, the sum of k elements in S(F) is n. By Condition iii) in the definition of F_{n,ℓ}, we know that the difference of the two largest elements in S(F) is q − 1. Hence, S(F) ∈ E_{n,ℓ+1,k,q−1}.

b) To show that S is injective, it suffices to verify that given F_{1} ≠ F_{2} ∈ F_{n,ℓ,k+1,ℓk+q}, we have D(F_{1}) ≠ D(F_{2}). For i ∈ {1, 2}, write F_{i} = {f_{i,1}, …, f_{i,k+1}}. Let t ≥ 2 be the smallest such that f_{1,t} ≠ f_{2,t}. Since F_{i} is sparse,

D(F_{i}) = f_{i,2} − f_{i,1} ≤ ⋯ ≤ f_{i,t} − f_{i,t−1} ≤ ⋯, for i = 1, 2.

It follows that t is the smallest such that f_{1,t} − f_{1,t−1} ≠ f_{2,t} − f_{2,t−1}. The above arrangement of numbers in D(F_{i}) in increasing order guarantees that D(F_{1}) ≠ D(F_{2}).

c) Let ℓ + 1 ≤ n_{1} ≤ ⋯ ≤ n_{k} be such that ∑_{i=1}^{k} n_{i} = n and n_{k} − n_{k−1} = q − 1. Define m_{i} = n_{i} − ℓ for i ≤ k − 1 and m_{k} = n_{k} − ℓ − (q − 1). Consider the set

F = {ℓk + q, ℓk + q + m_{1}, …, ℓk + q + ∑_{i=1}^{k} m_{i}} .

Observe that

ℓk + q + ∑_{i=1}^{k} m_{i} = ℓk + q + ∑_{i=1}^{k−1} m_{i} + m_{k}

= ℓk + q + ∑_{i=1}^{k−1} n_{i} − ℓ(k − 1) + n_{k} − ℓ − (q − 1)

= n + 1.

Hence, F ∈ F_{n,ℓ,k+1,ℓk+q}. It is easy to see that S(F) = n_{1} ≤ ⋯ ≤ n_{k}.

We have completed the proof. Corollary 12. For n ≥ ℓ + 1 and k ≥ 2, we have |E_{n,ℓ+1,k}| = |F_{n,ℓ,k+1}|. Proof. Simply observe that

|E_{n,ℓ+1,k}| = ∑_{q=1}^{∞} |E_{n,ℓ+1,k,q−1}| and |F_{n,ℓ,k+1}| = ∑_{q=1}^{∞} |F_{n,ℓ,k+1,ℓk+q}|,

and use Lemma 11. Corollary 13. For n ≥ ℓ + 1, we have |E_{n,ℓ+1}| = |F_{n,ℓ}| + 1. Proof. By Corollary 12,

|E_{n,ℓ+1}| = ∑_{k=1}^{∞} |E_{n,ℓ+1,k}| = |E_{n,ℓ+1,1}| + ∑_{k=2}^{∞} |E_{n,ℓ+1,k}| = |E_{n,ℓ+1,1}| + ∑_{k=2}^{∞} |F_{n,ℓ,k+1}|

= |E_{n,ℓ+1,1}| + ∑_{k=3}^{∞} |F_{n,ℓ,k}| = 1 + |F_{n,ℓ}|,

because sets in F_{n,ℓ} have at least three elements. Note also that |E_{n,ℓ+1,1}| = 1, because n ≥ ℓ + 1. Proof of Theorem 6, Identity (3). Pick n ≥ 1 and ℓ ≥ 0. We first consider the case n ≥ ℓ+1. To evaluate |A_{n+1,ℓ}| − |A_{n,ℓ}|, we define an injective map f : A_{n,ℓ} → A_{n+1,ℓ} as

f(A) := (A\{n}) ∪ {n + 1}.

It is easy to see that f(A_{n,ℓ}) = {{n + 1}} ∪ C_{n} ∪ D_{n}, where

C_{n} := {{m, n + 1} : ℓ + 1 ≤ m ≤ n − 1}, and
D_{n} := {{a_{1}, …, a_{p}, n + 1} : p ≥ 2, a_{1} < ⋯ < a_{p} < n is ℓ-strong Schreier, sparse}.

Hence,

|A_{n+1,ℓ}| − |A_{n,ℓ}| = |A_{n+1,ℓ}| − |f(A_{n,ℓ})| = |A_{n+1,ℓ}\({{n + 1}} ∪ C_{n} ∪ D_{n})|.

By the definition of A_{n+1,ℓ}, C_{n}, and D_{n}, we know that A_{n+1,ℓ}\({{n + 1}} ∪ C_{n} ∪ D_{n}) is the collection consisting of {n, n + 1} and sets of the form {a_{1}, …, a_{p}, n + 1} such that i) p ≥ 2, a_{1} < ⋯ < a_{p} < n + 1,

ii) {a_{1}, …, a_{p}, n + 1} is sparse and ℓ-strong Schreier, and

iii) if a_{p} < n, then {a_{1}, …, a_{p}, n} is not sparse.

Claim 14. Let A = {a_{1}, …, a_{p}, n + 1} satisfy Conditions i) and ii). Then A satisfies Condition iii) if and only if n + 1 + a_{p−1} = 2a_{p}.

Proof. Suppose that n + 1 + a_{p−1} = 2a_{p}; equivalently, n − a_{p} = a_{p} − a_{p−1} − 1. It follows that if a_{p} < n, then {a_{1}, …, a_{p}, n} is not sparse.

Conversely, assume that Condition iii) holds. Since A is sparse, we know that

(n + 1) − a_{p} ≥ a_{p} − a_{p−1}.

Suppose, for a contradiction, that (n + 1) − a_{p} > a_{p} − a_{p−1}; equivalently,

n ≥ a_{p} + (a_{p} − a_{p−1}) > a_{p}.

According to Condition iii), {a_{1}, …, a_{p}, n} is not sparse, which, along with the fact that A is sparse, implies

n − a_{p} < a_{p} − a_{p−1};

hence, a_{p} − a_{p−1} lies strictly between two consecutive integers n − a_{p} and n + 1 − a_{p}, a contradiction. Therefore, n + 1 + a_{p−1} = 2a_{p}.

Claim 14 states that we can replace Condition iii) by the condition n + a_{p−1} = 2a_{p}. Considering the definition of F_{n,ℓ}, we have shown that

A_{n+1,ℓ}\({{n + 1}} ∪ C_{n} ∪ D_{n}) = F_{n,ℓ} ∪ {{n, n + 1}}.

Therefore, |A_{n+1,ℓ}| − |A_{n,ℓ}| = |F_{n,ℓ}| + 1. Corollary 13 then gives

|A_{n+1,ℓ}| − |A_{n,ℓ}| = |E_{n,ℓ+1}|, for all n ≥ ℓ + 1.

We consider 1 ≤ n ≤ ℓ. When n ≤ ℓ, |E_{n,ℓ+1}| = 0. On the other hand, A_{n,ℓ} = {{n}} for all n ≤ ℓ + 1. Indeed, if there exists A ∈ A_{n,ℓ} with |A| ≥ 2, then

min A ≥ ℓ|A| − ℓ + 1 ≥ ℓ + 1,

so max A ≥ min A + 1 = ℓ + 2. However, n ≤ ℓ + 1; hence, no such set A exists. Therefore, similar to |E_{n,ℓ+1}|, |A_{n+1,ℓ}| − |A_{n,ℓ}| = 0 for all n ≤ ℓ. This completes our proof that

|A_{n+1,ℓ}| − |A_{n,ℓ}| = |E_{n,ℓ+1}|, for all n ≥ 1,

which implies (3).

The proof of Identity (4) is similar to the proof of Identity (3) with obvious modifications. Specifically, we change the third condition on sets in the family F_{n,ℓ} to

n + a_{p−1} = 2a_{p}.

The change leads to the definition of F_{n,ℓ}^{s} and F_{n,ℓ,k,q}^{s}, which are the counterparts of F_{n,ℓ} and F_{n,ℓ,k,q}, respectively. The counterpart of (7) is

|F_{n,ℓ,k+1,ℓk+q}^{s}| = |E_{n,ℓ,k,q}^{d}|.

Note that the index q − 1 is changed to q. For conciseness, we leave the details for interested readers.

Proof of Theorem 7. Fix ℓ ≥ 1. We prove (5). The generating function for the sequence (|E_{n,ℓ+1}|)_{n=0}^{∞} is Ψ(x) = ∏_{i=ℓ+1}^{∞}(1 − x^{i})^{−1}. Meanwhile, for n ≥ 2, if we add the part 1 to a partition in G_{n−1,ℓ}, we have a partition in G_{n,ℓ}. This map is clearly injective. Hence, for each n ≥ 2, |G_{n,ℓ}|−|G_{n−1,ℓ}| counts the number of partitions of n that contain no parts in {1, …, ℓ}, the generating function for which is again Ψ(x). Therefore, |G_{n,ℓ}| − |G_{n−1,ℓ}| = |E_{n,ℓ+1}| for all n ≥ 2. When n = 1, we also have |G_{1,ℓ}| − |G_{0,ℓ}| = |E_{1,ℓ+1}| = 0, because ℓ ≥ 1. Hence, |G_{n,ℓ}| − |G_{n−1,ℓ}| = |E_{n,ℓ+1}| for n ∈ ℕ. By (3), |A_{n,ℓ}| = |G_{n−1,ℓ}|, as desired.

Next, we prove (6). The generating function for (|E_{n,ℓ+1}^{d}|)_{n=0}^{∞} is

Ψ(x) = ∏_{i=ℓ+1}^{∞}(1 + x^{i}) = ∏_{i=ℓ+1}^{∞} \frac{1 − x^{2i}}{1 − x^{i}} = ∏_{i=ℓ+1}^{2ℓ} \frac{1}{1 − x^{i}} ∏_{j=ℓ}^{∞} \frac{1}{1 − x^{2j+1}} .

We establish the generating function for the sequence (|H_{n,ℓ}| − |H_{n−1,ℓ}|)_{n≥1}. As above, |H_{n,ℓ}|−|H_{n−1,ℓ}| counts the number of partitions of n that neither contain a part in {1, …, ℓ} nor contain an even part greater than 2ℓ, the generating function for which is

Θ(x) = ∏_{i=1}^{ℓ}(1 + x^{ℓ+i} + x^{2(ℓ+i)} + ⋯) ∏_{j=ℓ}^{∞}(1 + x^{2j+1} + x^{2(2j+1)} + ⋯)

= ∏_{i=ℓ+1}^{2ℓ} \frac{1}{1 − x^{i}} ∏_{j=ℓ}^{∞} \frac{1}{1 − x^{2j+1}} = Ψ(x).

Therefore, |H_{n,ℓ}| − |H_{n−1,ℓ}| = |E_{n,ℓ+1}^{d}| for n ≥ 2. When n = 1, |H_{1,ℓ}| − |H_{0,ℓ}| = |E_{1,ℓ+1}^{d}| = 0, because ℓ ≥ 1. We have shown |H_{n,ℓ}| − |H_{n−1,ℓ}| = |E_{n,ℓ+1}^{d}| for n ∈ ℕ. Use (4) to obtain |H_{n−1,ℓ}| = |A_{n,ℓ}^{s}|, as desired.

3 The ℓ-strong Schreier sets and compositions

Our proof of Theorem 9 invokes two well-known results: the star-and-bar problem and the hockey-stick identity. We refer the readers to [9, Lemma 2.1] for the former and to [13, Thm. 1.2.3 item (5)] for the latter.

Proof of Theorem 9. Observe that B_{n,ℓ,1} = {n} and c(n + ℓ, ℓ + 1, 1) = 1, so

|B_{n,ℓ,1}| = c(n + ℓ, ℓ + 1, 1).

Assume that m ≥ 2. According to the star-and-bar problem,

c(n + ℓ, ℓ + 1, m) = \binom{n + ℓ − (ℓ + 1)m + (m − 1)}{m − 1} = \binom{n + ℓ − ℓm − 1}{m − 1}.

On the other hand, for B ∈ B_{n,ℓ,m}, the ℓ-strong Schreier property implies that

min B ≥ ℓm − ℓ + 1.

A set in B_{n,ℓ,m} is formed by first choosing its minimum i ≥ ℓm − ℓ + 1 then choosing m − 2 number(s) strictly between i and n; hence,

|B_{n,ℓ,m}| = ∑_{i=ℓm−ℓ+1}^{n−1} \binom{n − i − 1}{m − 2} = ∑_{i=0}^{n+ℓ−ℓm−2} \binom{i}{m − 2}.

We, therefore, have |B_{n,ℓ,m}| ≠ 0 if and only if n − i − 1 ≥ m − 2 for some i ≥ ℓm − ℓ + 1. In other words, we have |B_{n,ℓ,m}| ≠ 0 if and only if n + ℓ ≥ (ℓ + 1)m. Similarly, we have c(n + ℓ, ℓ + 1, m) ≠ 0 if and only if n + ℓ ≥ (ℓ + 1)m. Therefore, it suffices to prove that |B_{n,ℓ,m}| = c(n + ℓ, ℓ + 1, m) when n + ℓ ≥ (ℓ + 1)m. In this case, applying the hockey-stick identity, we obtain

|B_{n,ℓ,m}| = ∑_{i=0}^{n+ℓ−ℓm−2} \binom{i}{m − 2} = \binom{n + ℓ − ℓm − 1}{m − 1} = c(n + ℓ, ℓ + 1, m).

This completes our proof.

4 Tables

Below are tables for initial values of |A_{n,ℓ}|, |A_{n,ℓ}^{s}|, |E_{n,ℓ}|, |E_{n,ℓ}^{d}|, |G_{n,ℓ}|, and |H_{n,ℓ}|.

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ |A_{n,0}| & 1 & 2 & 4 & 7 & 12 & 19 & 30 & 45 & 67 & 97 & 139 & 195 & 272 & 373 & 508 & 684 \\ |A_{n,1}| & 1 & 1 & 2 & 3 & 5 & 7 & 11 & 15 & 22 & 30 & 42 & 56 & 77 & 101 & 135 & 176 \\ |A_{n,2}| & 1 & 1 & 1 & 2 & 3 & 4 & 6 & 8 & 11 & 15 & 20 & 26 & 35 & 45 & 58 & 75 \\ |A_{n,3}| & 1 & 1 & 1 & 1 & 2 & 3 & 4 & 5 & 7 & 9 & 12 & 15 & 20 & 25 & 32 & 40 \end{matrix}

Table 1. Initial values of (|A_{n,ℓ}|)_{n=1}^{∞} for 0 ≤ ℓ ≤ 3.

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 \\ |A_{n,0}^{s}| & 1 & 2 & 3 & 5 & 7 & 10 & 14 & 19 & 25 & 33 & 43 & 55 & 70 & 88 & 110 & 137 & 169 \\ |A_{n,1}^{s}| & 1 & 1 & 2 & 3 & 4 & 6 & 8 & 11 & 14 & 19 & 24 & 31 & 39 & 49 & 61 & 76 & 93 \\ |A_{n,2}^{s}| & 1 & 1 & 1 & 2 & 3 & 4 & 5 & 7 & 9 & 12 & 15 & 19 & 24 & 30 & 37 & 46 & 56 \\ |A_{n,3}^{s}| & 1 & 1 & 1 & 1 & 2 & 3 & 4 & 5 & 6 & 8 & 10 & 13 & 16 & 20 & 24 & 30 & 36 \end{matrix}

Table 2. Initial values of (|A_{n,ℓ}^{s}|)_{n=1}^{∞} for 0 ≤ ℓ ≤ 3.

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ |E_{n,1}| & 1 & 1 & 2 & 3 & 5 & 7 & 11 & 15 & 22 & 30 & 42 & 56 & 77 & 101 & 135 & 176 & 231 \\ |E_{n,2}| & 1 & 0 & 1 & 1 & 2 & 2 & 4 & 4 & 7 & 8 & 12 & 14 & 21 & 24 & 34 & 41 & 55 \\ |E_{n,3}| & 1 & 0 & 0 & 1 & 1 & 1 & 2 & 2 & 3 & 4 & 5 & 6 & 9 & 10 & 13 & 17 & 21 \\ |E_{n,4}| & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 2 & 2 & 3 & 3 & 5 & 5 & 7 & 8 & 11 \end{matrix}

Table 3. Initial values of (|E_{n,ℓ}|)_{n=0}^{∞} for small 1 ≤ ℓ ≤ 4.

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ |E_{n,1}^{d}| & 1 & 1 & 1 & 2 & 2 & 3 & 4 & 5 & 6 & 8 & 10 & 12 & 15 & 18 & 22 & 27 & 32 \\ |E_{n,2}^{d}| & 1 & 0 & 1 & 1 & 1 & 2 & 2 & 3 & 3 & 5 & 5 & 7 & 8 & 10 & 12 & 15 & 17 \\ |E_{n,3}^{d}| & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 2 & 2 & 3 & 3 & 4 & 5 & 6 & 7 & 9 & 10 \\ |E_{n,4}^{d}| & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 2 & 2 & 3 & 3 & 4 & 4 & 6 & 6 \end{matrix}

Table 4. Initial values of (|E_{n,ℓ}^{d}|)_{n=0}^{∞} for small 1 ≤ ℓ ≤ 4.

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ |G_{n,1}| & 1 & 1 & 2 & 3 & 5 & 7 & 11 & 15 & 22 & 30 & 42 & 56 & 77 & 101 & 135 & 176 & 231 \\ |G_{n,2}| & 1 & 1 & 1 & 2 & 3 & 4 & 6 & 8 & 11 & 15 & 20 & 26 & 35 & 45 & 58 & 75 & 96 \\ |G_{n,3}| & 1 & 1 & 1 & 1 & 2 & 3 & 4 & 5 & 7 & 9 & 12 & 15 & 20 & 25 & 32 & 40 & 51 \end{matrix}

Table 5. Initial values of (|G_{n,ℓ}|)_{n=0}^{∞} for small 1 ≤ ℓ ≤ 3.

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ |H_{n,1}| & 1 & 1 & 2 & 3 & 4 & 6 & 8 & 11 & 14 & 19 & 24 & 31 & 39 & 49 & 61 & 76 & 93 \\ |H_{n,2}| & 1 & 1 & 1 & 2 & 3 & 4 & 5 & 7 & 9 & 12 & 15 & 19 & 24 & 30 & 37 & 46 & 56 \\ |H_{n,3}| & 1 & 1 & 1 & 1 & 2 & 3 & 4 & 5 & 6 & 8 & 10 & 13 & 16 & 20 & 24 & 30 & 36 \end{matrix}

Table 6. Initial values of (|H_{n,ℓ}|)_{n=0}^{∞} for small 1 ≤ ℓ ≤ 3.

5 Acknowledgments

The authors would like to thank the anonymous referee for reading the paper and for the feedback.

References

[1] S. A. Argyros and I. Gasparis, Unconditional structures of weakly null sequences, Trans. Amer. Math. Soc. 353 (2001), 2019–2058.

[2] K. Beanland, H. V. Chu, and C. E. Finch-Smith, Generalized Schreier sets, linear recurrence relation, and Turán graphs, Fibonacci Quart. 60 (2022), 352–356.

[3] K. Beanland, D. Gorovoy, J. Hodor, and D. Homza, Counting unions of Schreier sets, to appear in Bull. Aust. Math. Soc. Available at https://arxiv.org/abs/2211.01049.

[4] A. Bird, Schreier sets and the Fibonacci sequence. Available at https://tinyurl.com/

uc4cbf5r.

[5] H. V. Chu, On a relation between Schreier-type sets and a modification of Turán graphs, Integers 23 (2023), 1–10.

[6] H. V. Chu, N. Irmak, S. J. Miller, L. Szalay, and S. X. Zhang, Schreier multisets and the s-step Fibonacci sequences, to appear in Proceedings of the Integer Conference 2023.

Available at https://arxiv.org/abs/2304.05409.

[7] H. V. Chu, S. J. Miller, and Z. Xiang, Higher order Fibonacci sequences from generalized Schreier sets, Fibonacci Quart. 58 (2020), 249–253.

[8] V. Farmaki and S. Negrepontis, Schreier sets in Ramsey theory, Trans. Amer. Math. Soc. 360 (2008), 849–880.

[9] M. Koloǧlu, G. S. Kopp, S. J. Miller, and Y. Wang, On the number of summands in Zeckendorf decompositions, Fibonacci Quart. 49 (2011), 116–130.

[10] E. Odell, On Schreier unconditional sequences, Contemp. Math. 144 (1993), 197–201.

[11] J. Schreier, Ein Gegenbeispiel zur Theorie der schwachen Konvergenz, Studia Math. 2 (1930), 58–62.

[12] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2023. Available

at https://oeis.org.

[13] Douglas B. West, Combinatorial Mathematics, Cambridge University Press, 2021.

2020 Mathematics Subject Classification: Primary 05A19; Secondary 05A17, 11Y55, 11B37. Keywords: Schreier set, partition, composition.

(Concerned with sequences \underline{A000009}, \underline{A000041}, \underline{A000070}, \underline{A002865}, \underline{A008483}, \underline{A008484}, \underline{A025147}, \underline{A025148}, \underline{A025149}, \underline{A025150}, \underline{A025151}, \underline{A027336}, \underline{A036469}, \underline{A038348}, and \underline{A185325}.)

Received November 6 2023; revised versions received November 8 2023; April 5 2024. Published in Journal of Integer Sequences, April 5 2024.

Return to Journal of Integer Sequences home page.