On Dedekind Numbers and Two Sequences of Knuth

J. Berman

Department of Mathematics, Statistics, and Computer Science

University of Illinois at Chicago Chicago, IL 60607 USA

                    jberman@uic.edu

P. Köhler^{1}

Mathematisches Institut Justus-Liebig-Universität Giessen Arndtstr. 2 35392 Giessen Germany

           peter.koehler@math.uni-giessen.de

Abstract

We consider the sequence whose n^{th} term is the number F (n) of anti-chains in the partially ordered set whose elements are 0, 1, …, n − 1 and the order relation is coordinate-wise on the binary representation of each integer. This sequence is a sort of “background” sequence to its more prominent subsequence of Dedekind numbers, that is, the sequence whose terms are F (2^{k}). We also consider the sequence of first differences with terms F (n) − F (n − 1). We discuss, state, and prove some (recursive) relations between the terms of these three sequences.

1 Introduction

Let P_{n} denote the partially ordered set (poset) whose elements are 0, 1, …, n − 1 and the order relation is coordinate-wise with respect to the binary representation of the integers in P_{n}. Thus, if n = 2^{k}, then P_{n} is a Boolean lattice with top element 2^{k} − 1 and atoms 2^{i} for 0 ≤ i ≤ 2^{k−1}.

1Author’s present address: peter@koehler-weilburg.de.

For each n let F (n) be the number of anti-chains in P_{n}. So F (2^{k}) is the number of anti-chains in a Boolean lattice with k atoms, that is, F (2^{k}) is a Dedekind number. The exact values of the Dedekind numbers are known only for k ≤ 8. The computation for the case k = 8 is described in Wiedemann [7]. The sequence of Dedekind numbers is \underline{A000372} in the On-Line Encyclopedia of Integer Sequences [6]. The many entries in the comments and references for this sequence there attest to the wide interest in it.

The integer sequence with terms F (n) is a background sequence for the sequence of Dedekind numbers. It is \underline{A132581} and was authored by D. E. Knuth. The function Δ(n) = F (n) − F (n − 1) gives the terms for the first differences of \underline{A132581}; we tacitly extend the definition by Δ(0) = 0.

The sequence of Δ values is \underline{A132582} and is also authored by Knuth. Another way to define this sequence would be to say that Δ(n) is the number of anti-chains containing n − 1 in the partially ordered set P_{n}.

In this paper we investigate the poset P_{n} and the two functions F and Δ. Our main interest is in finding expressions for F (n) and for Δ(n) in terms of F or Δ applied to integers less than n.

In Section 2 we present the basics on posets and lattices that we will use. Section 3 contains lemmas that express the number of anti-chains in an arbitrary finite poset as the sum of the number of anti-chains in certain subposets. We use these lemmas to find two formulas for Dedekind numbers F (2^{k}) for arbitrary k that involve the function F applied to arguments less than 2^{k}. In Section 4 we present formulas for Δ(n) that only involve the F and Δ functions applied to arguments less than n. The final section of the paper is a summary that contains a list of the formulas proved in the paper. As an application, we show how these formulas may be used to determine Δ(n) in the interval 16 ≤ n ≤ 32.

2 Basics

A semi-ideal of a poset P is a subset I ⊆ P, which is closed downwards, i.e., it satisfies the condition p ∈ I, q ≤ p ⟹ q ∈ I. A semi-filter is a subset F, which is closed upwards, i.e., it satisfies the condition p ∈ F, q ≥ p ⟹ q ∈ F. An anti-chain of P is a set of mutually incomparable elements. For a poset P and an element p ∈ P let sub(p) denote the semi-ideal {q ∈ P | q ≤ p} and super(p) denote the semi-filter {q ∈ P | p ≤ q} and let cone(p) denote the union sub(p) ∪ super(p) of these. To facilitate notation we will use the term cocone(p) as an abbreviation of P \ cone(p), as well as cosub(p) for P \ sub(p) and cosuper(p) for P \super(p). If the context of the poset P is necessary we will express this via a prefix P. as in P. cosub(p) and P. cosuper(p). This comes in handy in expressions like P. cosub(p). cosub(q), which of course is equal to P \ (sub(p) ∪ sub(q)). We will also use cosub(p, q) as a shorthand for this set, as well as cosuper(p, q) for the poset P \(super(p)∪super(q)). For other notation and terminology on partially ordered sets and Boolean lattices we follow the monographs of Balbes and Dwinger [1] and Birkhoff [3].

It is well known that the set of semi-ideals and the set of semi-filters of a poset P form distributive lattices I(P) and F(P) with set intersection and set union. Both these lattices are isomorphic to the lattice of A(P) of anti-chains of P, where the meet- and join-operations are slightly more complicated. Let α(P) denote the number of elements of A(P).

We recall from Section 1 the definition of the poset P_{n} as the set {0, …, n−1} with binary ordering, i.e., coordinate-wise with respect to the binary representation of the elements. In particular, we note that P_{0} is the empty poset. Since the usual ordering of ℕ is different from the binary ordering we express the latter via ≤_{b} and ≥_{b} where necessary. We note for later reference that the natural ordering is an extension of the binary ordering in the sense that p ≤_{b} q implies p ≤ q, as well as p ≥_{b} q implies p ≥ q for all p, q ∈ ℕ. To put it differently, we have P_{n}. sub(p) ⊆ [0, p] and P_{n}. super(p) ⊆ [p, n − 1], where we use the handy interval notation [p, q] with respect to the natural ordering, i.e., [p, q] = {x | p ≤ x ≤ q}.

Figure 1 shows the poset P_{16}.

[figure: 0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15]

Figure 1: The Boolean poset B_{4} = P_{16} with 16 elements.

If n is of the form n = 2^{k}, then P_{n} is a Boolean poset, which we also denote by B_{k}. The atoms of B_{k} are the elements 2^{0}, 2^{1}, …, 2^{k−2}, 2^{k−1} and the dual atoms are the elements 2^{k} − 2, 2^{k} − 3, …, 2^{k} − 1 − 2^{k−1}. For this Boolean poset we have a slightly closer connection between the binary and the linear ordering. That is,

P_{n}. super(p) = [p, n − 1] if and only if p = 2^{k} − 2^{m} for some m ≤ k,  (1)
P_{n}. sub(p) = [0, p] if and only if p = 2^{m} − 1 for some m ≤ k.  (2)

Both are immediate consequences of the sum formula 2^{m−1} − 1 = ∑_{i=0}^{i=m−1} 2^{i}.

Another way to see this is via the binary representation of the elements of B_{k} as a 0-1–sequence. So for k = 4 these elements are

2^{k} − 2^{0} = 15 = 1111,
2^{k} − 2^{1} = 14 = 1110,
2^{k} − 2^{2} = 12 = 1100,
2^{k} − 2^{3} = 8 = 1000,
2^{k} − 2^{4} = 0 = 0000.

In general, these elements are those, whose binary representation is a sequence with ‘leading ones’.

Every automorphism of B_{k} is determined by its action on the atoms, and therefore the automorpism group of B_{k} is isomorphic to the symmetric group on k elements. Of particular interest in the following is the atom inflection β, which maps the atom 2^{0} onto the atom 2^{k−1}, the atom 2^{1} onto the atom 2^{k−2}, and so on. Figure 2 shows the order automorphism β of B_{4}. (Note that in order to avoid excessive arrows we restrict ourselves to indicate the action by an appropriate labelling.) We also denote the isomorphism that exchanges the atoms 2^{i} and 2^{j} and keeps all the other atoms fixed, by ρ_{i,j}.

Figure 3 shows ρ_{0,1} on B_{4}.

The complementation γ defined by γ(x) = 2^{k} − 1 − x is an order anti-automorphism. Figure 4 shows γ on B_{4}.

The composition δ = βγ is an order anti-automorphism that acts like a top-down inflection. Figure 5 shows δ on B_{4}.

And since γ commutes with all the order isomorphisms, the group of all order automorphisms and order anti-automorphisms of B_{k} is is isomorphic to the (direct) product of the symmetric group and an inflection group of order 2.

Let D_{n} denote the lattice I(P_{n}). Then for P_{8} as shown in Figure 6, the lattice D_{8} consists of the 20 semi-ideals

∅, {0}, {0, 1}, {0, 2}, {0, 4},
{0, 1, 2}, {0, 1, 4}, {0, 2, 4}, {0, 1, 2, 3}, {0, 1, 2, 4}, {0, 1, 4, 5}, {0, 2, 4, 6},
{0, 1, 2, 3, 4}, {0, 1, 2, 4, 5}, {0, 1, 2, 4, 6}, {0, 1, 2, 3, 4, 5}, {0, 1, 2, 4, 6}, {0, 1, 2, 5, 6},
{0, 1, 2, 3, 4, 5, 6}{0, 1, 2, 3, 4, 5, 6, 7}

and has the lattice diagram of Figure 7.

[figure: 0 = β(0); 1 = β(8); 2 = β(4); 3 = β(12); 4 = β(2); 5 = β(10); 6 = β(6); 7 = β(14); 8 = β(1); 9 = β(9); 10 = β(5); 11 = β(13); 12 = β(3); 13 = β(11); 14 = β(7); 15 = β(15)]
Figure 2: The action of β on B_{4} = P_{16}.

If we let D_{01} denote the variety of all distributive lattices with 0 and 1, and FD_{01}(n) denote the free algebra of D_{01} on n generators, then it is well known that D_{2^{n}} ≅ FD_{01}(n) for all n ∈ ℕ.

The values of \underline{A132581} and its difference sequence \underline{A132582} have been computed for the first 212 terms (J. M. Aranda). In order to illustrate the results of the following sections, we list the first 32 terms in Table 1.

3 Formulas for F (n)

An old result allowing a (recursive) computation of the number of anti-chains of a poset is taken from Berman and Köhler [2, Thm. 2.1].

Lemma 1. For every poset P and every p ∈ P, we have α(P) = α(P \ {p}) + α(cocone(p)).

Applying this to the poset P_{n} and the element n − 1 gives

F (n) = F (n − 1) + α(cocone(n − 1)).  (3)

Actually (3) is still the basis for the computation of the known sequence terms. For later use we introduce the notion of a pivot. For a poset Q and an element q ∈ Q we say that the poset Q pivots on the element q to produce the two smaller sets Q \ {q} and Q. cocone(q).

Using the arguments of Lemma 1 in a slightly more sophisticated way one can obtain the following alternative from a Campo and Erné [4, Cor. 3.2].

Lemma 2. For every poset P and every p ∈ P, we have α(P) = α(cosuper(p))+α(cosub(p)).

[figure: 0 = ρ_{0,1}(0); 1 = ρ_{0,1}(2); 2 = ρ_{0,1}(1); 3 = ρ_{0,1}(3); 4 = ρ_{0,1}(4); 5 = ρ_{0,1}(6); 6 = ρ_{0,1}(5); 7 = ρ_{0,1}(7); 8 = ρ_{0,1}(8); 9 = ρ_{0,1}(10); 10 = ρ_{0,1}(9); 11 = ρ_{0,1}(11); 12 = ρ_{0,1}(12); 13 = ρ_{0,1}(14); 14 = ρ_{0,1}(13); 15 = ρ_{0,1}(15)]
Figure 3: The action of ρ on B_{4} = P_{16}.

Applying this to the Boolean poset B_{n} and an atom of the form 2^{k} we get

Formula 3. For all n, k ∈ ℕ with k ≤ n, we have F (2^{n}) = F (2^{n} − 2^{k}) + F (2^{n} − 2^{n−k}).

This gives the following interesting special cases

F (2^{n}) = F (2^{n} − 1) + 1,
F (2^{n})F (2^{n} − 2) + F (2^{n−1}),
F (2^{n}) = F (2^{n} − 4) + F (3 · 2^{n−2}).

In particular, the case where n is even and k = \frac{n}{2} yields F (2^{n}) = 2 · F (2^{n} − 2^{k}), and this is another proof of the fact that | FD(n)| is even for even n.

Formula 3 was stated without proof by J. M. Aranda in the Formula section of \underline{A132581}. Before starting the proof of Formula 3 we begin with some general remarks about the

elements 2^{n}−2^{k} of B_{n}. As already mentioned in Section 2 (1),(2), integers of the form 2^{n}−2^{k} have the unique and special property that [2^{n} − 2^{k}, 2^{n} − 1] = super(2^{n} − 2^{k}). The elements 2^{n} − 2^{k} form a maximal chain in B_{n} that appears on the right side of the diagram of B_{n}. The complement of 2^{n} −2^{k} is 2^{k} −1 and all of these complements appear as a maximal chain on the left side in the diagram of B_{n}. And it is also easy to see that the anti-automorphism δ maps 2^{n} − 2^{k} onto 2^{n} − 2^{n−k}. As a result, the poset cone(2^{n} − 2^{k}) is dually isomorphic to cone(2^{n} − 2^{n−k}). In particular, cone(2^{n} − 2^{k}) is isomorphic to the poset B_{k} placed above the poset B_{n−k} with the bottom element of B_{k} equal to the top element of B_{n−k}. This can also be expressed as

cone(2^{n} − 2^{k}) = [2^{n} − 2^{k}, 2^{n} − 1] ∪ {i · 2^{k} | i = 0, 1, …, 2^{n−k} − 1}.  (4)

[figure: 0 = γ(15); 1 = γ(14); 2 = γ(13); 3 = γ(12); 4 = γ(11); 5 = γ(10); 6 = γ(9); 7 = γ(8); 8 = γ(7); 9 = γ(6); 10 = γ(5); 11 = γ(4); 12 = γ(3); 13 = γ(2); 14 = γ(1); 15 = γ(0)]

Figure 4: The action of γ on B_{4} = P_{16}.

In addition

B_{n}. cosuper(2^{n} − 2^{k}) is isomorphic to P_{2^{n}−2^{k}}  (5)
B_{n}. cosub(2^{n} − 2^{k}) is dually isomorphic to P_{2^{n}−2^{n−k}}.  (6)

We also note that (5) and (6) hold for every element of rank n − k, i.e., for every element above exactly n − k atoms.

Proof. (of Formula 3) Combining (5), (6), and Lemma 2 gives the result.

Using the principle of inclusion and exclusion one can easily extend the result of Lemma 2 to a summation of more terms.

Lemma 4. For every poset P and every p, q ∈ P, we have α(P) = α(cosuper(p, q)) + α(cosub(p)) + α(cosub(q)) − α(cosub(p, q)).

Lemma 5. For every poset P and every p, q ∈ P, we have α(P) = α(cosub(p, q)) + α(cosuper(p)) + α(cosuper(q)) − α(cosuper(p, q)).

With the help of Lemma 4 and and two conveniently chosen elements of B_{n} we get

Formula 6. For k, n ∈ ℕ with 1 ≤ k < n, we have F (2^{n}) = F (2^{n} −2^{n−k} −2^{n−k−1})+2F (2^{n} − 2^{k}) − F (2^{n} − 2^{k} − 2^{k−1}).

E.g., for n = 5, k = 2 we have F (32) = F (20) + 2 · F (28) − F (26) and for n = 5, k = 3 we have F (32) = F (26) + 2 · F (24) − F (20).

Proof. Let P = B_{n}. We consider the two elements a_{1} = 2^{n}−2^{n−k} and a_{2} = 2^{n}−2^{n−k}−2^{n−k−1} and note that a_{2} is the image of a_{1} under the automorphism ρ_{n−k,n−k−1}, that exchanges the atoms 2^{n−k} and 2^{n−k−1} and keeps the other atoms fixed.

[figure: 0 = δ(15); 1 = δ(7); 2 = δ(11); 3 = δ(3); 4 = δ(13); 5 = δ(5); 6 = δ(9); 7 = δ(1); 8 = δ(14); 9 = δ(6); 10 = δ(10); 11 = δ(2); 12 = δ(12); 13 = δ(4); 14 = δ(8); 15 = δ(0)]

Figure 5: The action of δ on B_{4} = P_{16}.

[figure: 7; 6; 5; 3; 4; 2; 1; 0]

Figure 6: The Boolean poset B_{3} = P_{8} with 8 elements.

By Lemma 4 we have F (2^{n}) = α(P. cosuper(a_{1}, a_{2}))+α(P. cosub(a_{1}))+α(P. cosub(a_{2}))− α(P. cosub(a_{1}, a_{2})). We first observe that P. cosuper(a_{1}, a_{2}) = P_{a_{2}}, which accounts for the first term in the formula.

Moreover α(P. cosub(a_{1})) = F (2^{n} − 2^{k}) by (5). And as a_{1} is mapped onto a_{2} by the automorphism ρ_{n−k,n−k−1}, we have the same result for P. cosub(a_{2}). This accounts for the second term in the formula.

To account for the subtraction of the last term we use the anti-automorphism δ as in the derivation of (4). Let b_{i} = δ(a_{1}) for i = 1, 2. Then P. cosub(a_{1}, a_{2}) is dually isomorphic to P. cosuper(b_{1}, b_{2}) and by the argument of the first part this shows that α(cosub(a_{1}, a_{2}) = α(P. cosuper(b_{1}, b_{2})) = F (b_{2}).

In addition, it would be possible to formulate an analog to Lemma 4 for three elements. There was, however, no immediate application of that to gain another recursion formula involving F -terms.

Other recursions are possible, but they are more conveniently formulated using the terms of the Δ-sequence—we will discuss that in the following section.

[figure]

Figure 7: The lattice D_{8}.

4 Formulas for Δ(n)

Let d(n) denote the poset P_{n}. cosub(n − 1). As n − 1 is a maximal element of P_{n} we have P_{n}. cosuper(n − 1) = P_{n} \ {n − 1} and P_{n}. cosub(n − 1) = P_{n}. cocone(n − 1) and therefore Δ(n) = α(d(n)) by Lemma 1 and Lemma 2.

We wish to find formulas for Δ(n) that involve the functions Δ and F applied to arguments that are less than n.

Formula 7. For all n, k ∈ ℕ with 0 ≤ k ≤ n, we have Δ(2^{n} − 2^{k} + 1) = Δ(2^{n} − 2^{n−k} + 1).

E.g., for n = 5, k = 2 we have Δ(29) = Δ(25).

Proof. In order to prove the formula it suffices to show that the poset d(2^{n} −2^{k} +1) is dually isomorphic to d(2^{n} + 2^{n−k} + 1). By definition, we have

d(2^{n} − 2^{k} + 1) = P_{2^{n}−2^{k}+1}. cocone(2^{n} − 2^{k}).

And by (5) we have B_{n} = [0, 2^{n} − 2^{k}] ∪ super(2^{n} − 2^{k}). Therefore

B_{n}. cocone(2^{n} − 2^{k}) = P_{2^{n}−2^{k}+1}. cocone(2^{n} − 2^{k}) = d(2^{n} − 2^{k} + 1).

And as δ(2^{n} − 2^{k}) = 2^{n} − 2^{n−k}, we get

δ(d(2^{n} − 2^{k} + 1)) = δ(B_{n}. cocone(2^{n} − 2^{k})) = B_{n}. cocone(2^{n} − 2^{n−k}) = d(2^{n} − 2^{n−k} + 1).

\begin{matrix}n & F (n) & Δ(n) & n & F (n) & Δ(n) \\ 1 & 2 & 1 & 17 & 335 & 167 \\ 2 & 3 & 1 & 18 & 483 & 148 \\ 3 & 5 & 2 & 19 & 765 & 282 \\ 4 & 6 & 1 & 20 & 849 & 84 \\ 5 & 11 & 5 & 21 & 1466 & 617 \\ 6 & 14 & 3 & 22 & 1681 & 215 \\ 7 & 19 & 5 & 23 & 1988 & 307 \\ 8 & 20 & 1 & 24 & 2008 & 20 \\ 9 & 39 & 19 & 25 & 3700 & 1692 \\ 10 & 53 & 14 & 26 & 4414 & 714 \\ 11 & 78 & 25 & 27 & 5489 & 1075 \\ 12 & 84 & 6 & 28 & 5573 & 84 \\ 13 & 134 & 50 & 29 & 7265 & 1692 \\ 14 & 148 & 14 & 30 & 7413 & 148 \\ 15 & 167 & 19 & 31 & 7580 & 167 \\ 16 & 168 & 1 & 32 & 7581 & 1 \end{matrix}

Table 1: F (n) and Δ(n).

The fact that B_{n}. cocone(2^{n} − 2^{k}) = d(2^{n} − 2^{k} + 1) allows for a description of the poset d(2^{n} − 2^{k} + 1) as follows. The minimal elements of this poset are the k atoms 2^{0}, 2^{1}, …, 2^{k−1} of B_{n}. The maximal elements of this poset are the n − k co-atoms

(2^{n} − 1) − 2^{n−1}, (2^{n} − 1) − 2^{n−2}, …, 2^{k}

of B_{n}. An element b of B_{n} is in d(2^{n} − 2^{k} + 1) if and only if there exist elements a and c such that a ≤ b ≤ c with a one of the k atoms in this list of minimal elements and c one of the n − k co-atoms in this list of maximal elements. Despite this description, we do not have a direct formula for the number of anti-chains in this poset.

We do have, however, a sum formula, which can be proven along the same lines as Formula 6.

Formula 8. For all k, n ∈ ℕ with 1 ≤ k ≤ n − 1, we have

Δ(2^{n} − 2^{k} + 1) = Δ(2^{n} − 2^{k} − 2^{k−1} + 1) + Δ(2^{n} − 2^{n−k} − 2^{n−k−1} + 1).

E.g., for n = 5, k = 2 we have Δ(29) = Δ(27) + Δ(21) and, combining this with Formula 7, Δ(27) = Δ(25) − Δ(21).

Proof. Let a = 2^{n} − 2^{k} and P = P_{a+1}, Then d(a + 1) = P. cosub(a). Let

x = ρ_{k−1,k}(a) = 2^{n} − 2^{k} − 2^{k−1}.

Then P. super(x) = {i | x ≤ i < a}, since x is covered by the k−1 elements x+2^{0}, …, x+2^{k−2}. As a result, P. cosuper(x) = P \ {i | x ≤ i < a} and that is easily seen to be isomorphic to P_{x+1} via the isomorphism ρ_{k−1,k}.

We form d_{1} = d(a + 1). cosub(x) and d_{2} = d(a + 1). cosuper(x). By Lemma 2 we have Δ(a + 1) = α(d_{1}) + α(d_{2}). So it remains to show that α(d_{2}) = α(d(2^{n} − 2^{k} − 2^{k−1} + 1)) and α(d_{1}) = α(d(2^{n} − 2^{n−k} − 2^{n−k−1} + 1)).

For d_{2} this is rather immediate, since d_{2} = P. cosuper(x). cosub(a) and that is, by the remark above, isomorphic to P_{x+1}. cosub(x), which is d(x + 1).

For d_{1} this is not as obvious, but we can make use of the dual isomorphism between d(a + 1) and d(2^{n} + 2^{n−k} + 1) of the proof of Formula 7. In fact, δ(a) = 2^{n} − 2^{n−k} and δ(x) = 2^{n} − 2^{n−k} − 2^{n−k−1}. This implies that d_{1} is dually isomorphic to

d(2^{n} + 2^{n−k} + 1). cosuper(2^{n} − 2^{n−k} − 2^{n−k−1}).

And this finally is, by the same reasoning as for d_{2} above, isomorphic to d(2^{n} − 2^{n−k} − 2^{n−k−1} + 1).

Applying Formula 8 for specific combinations of n, k gives some interesting connections. For even n, say n = 2q, we get

Δ(2^{2q} − 2^{q} + 1) = 2 · Δ(2^{2q} − 2^{q} − 2^{q−1} + 1),

e.g., Δ(13) = 2 · Δ(11) or Δ(57) = 2 · Δ(53).

An additional curiosity here is that Δ(13) = 50 and 50 is the largest Δ value among all Δ(i) for i ≤ 2^{4} and Δ(57) = 2453690 is the largest Δ value among all Δ(i) for 1 ≤ i ≤ 2^{6}. This suggests the general result for n = 2q that Δ(2^{2q} − 2^{q} + 1) is the largest value of Δ(i) for i ≤ n.

If we continue to speculate in this way for n odd, say, n = 2q − 1 and if we look for the value of Δ(i) that is largest among all i ≤ 2^{n}, then

for n = 2 · 2 − 1 = 3 the largest value is 5 = Δ(5) = Δ(7),

for n = 2 · 3 − 1 = 5 the largest value is 1692 = Δ(25) = Δ(29),

for n = 2 · 4 − 1 = 7 the largest value is 510955171111 = Δ(113) = Δ(121).

This suggests that in general the largest Δ(i) value for i ≤ n = 2q − 1 is obtained by Δ(2^{2q−1} − 2^{q−1} + 1) and by Δ(2^{2q−1} − 2^{q} + 1). Proving this may be quite difficult.

We also note that from Table 1 we see that the equalities

Δ(2^{5} − 3) = 6Δ(2^{4} + 3) and
Δ(2^{4} − 3) = 2 · Δ(2^{3} + 3)

hold. But Δ(2^{6} − 3) = 580655 = 5 · 116131, and 116131 is prime and is not a Δ or an F value.

Here are some other recursion formulas.

Formula 9. For all k, n ∈ ℕ with 0 ≤ k ≤ n − 1, we have Δ(2^{n} − 2^{k}) = F (2^{n−1} − 2^{k}).

Proof. Let P = P_{2^{n}} and a = 2^{n} − 2^{k}. Then by (5) P. cosuper(a) = P_{a} and therefore d(a) = P. cosuper(a). cosub(a − 1). We now observe that a − 1 = 2^{n} − 1 − 2^{k} is a dual atom of P and, as noted right after (6), this implies that the poset Q with

Q = P. cosub(a − 1)

is dually isomorphic to P_{2^{n−1}}. If ϕ is this dual isomorphism then

ϕ(Q. cosuper(a)) = P_{2^{n−1}}. cosuper(ϕ(a))

and ϕ(a) has rank k in P_{2^{n−1}}. As a result, ϕ(Q. cosuper(a)) is isomorphic to P_{2^{n−1}−2^{k}}, which proves Formula 9.

Formula 10. For all n, k ∈ ℕ with 0 ≤ k ≤ n − 1, we have Δ(2^{n} + 2^{k}) = F (2^{n} − 2^{k}).

Proof. Δ(2^{n} + 2^{k}) = α(P_{2^{n}+2^{k}}. cocone(2^{n} + 2^{k} − 1)). The element 2^{n} + 2^{k} − 1 is the join in the lattice B_{n+1} of the atom 2^{n} and 2^{k} − 1. So 2^{k} − 1 is covered by 2^{n} + 2^{k} − 1. Thus, the semi-ideal sub(2^{n} + 2^{k} − 1) is the union of the interval [0, 2^{k} − 1] and the interval [2^{n}, 2^{n} + 2^{k} − 1]. Therefore, the poset P_{2^{n}+2^{k}}. cocone(2^{n} + 2^{k} − 1) consists of P_{2^{n}} \ P_{2^{k}}, which is dually isomorphic to P_{2^{n}−2^{k}}.

We next find formulas for Δ(2^{n} + i) for i ≤ 7 that only involve the functions Δ and F applied to arguments less than 2^{n} + i. By virtue of Formula 10 we need only consider i = 3, 5, 6, 7. The proofs will involve frequent use of the pivot notion introduced right after Lemma 1.

Let Q denote P_{2^{n}+i}. cocone(2^{n} + i − 1). Then Δ(2^{n} + i) = α(Q) and for any p ∈ Q by Lemma 1 we have α(Q) is the sum α(Q \ {p}) + α(Q. cocone(p)). If both summands are known then we are done. If not then choose a poset for which the α value is not known and apply Lemma 1. Continue in this way until all the α values are known and add up these values. This will be a formula for Δ(2^{n} + i).

In the context in which we are working a poset S has the value of α(S) known if S or its dual is isomorphic to a P_{k} for k < 2^{n} + i or to a poset whose α value was determined at an earlier stage in the proof.

An important fact to consider in choosing the element on which a poset is to pivot is that for any j ≤ i the poset [0, 2^{n} − 1] ∩ cocone(2^{n} + j) is dually isomorphic to P_{2^{n}−j}, which is a poset with a known α value. We use the heuristic of choosing pivot elements of the form 2^{n} + j wherever possible so as to obtain posets that are either entirely in [0, 2^{n} − 1] that are dually isomorphic to P_{r} for r ≤ 2^{n} or are isomorphic to a P_{r} for r = 2^{n} + j for which α(P_{r}) has already been determined. This method suffices in our proofs for i = 3, 6, and 7. For determining α(Q) for Q ⊆ [0, 2^{n} − 1] that are not isomorphic or dually isomorphic to a P_{k} we look for a poset Q′ for which α(Q′) had been determined by the use of Lemma 1 earlier in the proof. This is the case for our proof of the formula for Δ(2^{n} + 5).

Formula 11. For every n ∈ ℕ with n ≥ 2, we have Δ(2^{n} + 3) = F (2^{n} − 2) + F (2^{n} − 3).

Proof. The poset Q = P_{2^{n}+3}. cocone(2^{n}+2) consists of [0, 2^{n}+2]\{0, 2^{1}, 2^{n}, 2^{n}+2}. Pivoting it with p = 2^{n} + 1 yields Q \ {p} = P_{2^{n}} \ {0, 1} and Q. cocone(p) = P_{2^{n}} \ {0, 1, 2}. And these posets are dually isomorphic to P_{2^{n}−2} and P_{2^{n}−3} as desired.

Formula 12. For every n ∈ ℕ with n ≥ 1, we have

Δ(2^{n} + 5) = 2 · Δ(2^{n} + 3) + Δ(2^{n} + 4) − Δ(2^{n−1} + 3) − Δ(2^{n−1} + 4).

E.g., Δ(21) = 2 · Δ(19) + Δ(20) − Δ(11) − Δ(12) = 2 · 282 + 84 − 25 − 6 = 617.

Proof. Let Q = d(2^{n} + 5). Then by definition

Q = P_{2^{n}+5}. cocone(2^{n} + 4) = P_{2^{n}+5} \ {0, 4, 2^{n}, 2^{n} + 4}.

First pivot Q on the element 2^{n} + 3. Then we get the pivot components Q_{1} and Q_{2} with Q_{1} = Q \ {2^{n} + 3} and Q_{2} = Q. cocone(2^{n} + 3) = [5, 2^{n} − 1], which is easily seen to be dually isomorphic to P_{2^{n}−5}. This pivot of Q gives

α(Q) = α(Q_{1}) + α(Q_{2})  (7)
α(Q_{2}) = F (2^{n} − 5).  (8)

Another pivoting of Q_{1} at 2^{n} + 2 leads to the components Q_{11} = Q_{1} \ {2^{n} + 2} and Q_{12} = Q_{1}. cocone(2^{n} +2). Now Q_{11} is easily seen to be isomorphic to d(2^{n} +3) via the isomorphism ρ_{1,2} of B_{n} that interchanges the atoms 2^{1} and 2^{2}. This accounts for one of the occurrences of Δ(2^{n} + 3) in the formula.

α(Q_{1}) = α(Q_{11}) + α(Q_{12})  (9)
α(Q_{11}) = α(d(2^{n} + 3)))  (10)

To obtain the other parts, we show that they arise as pivot components of known posets. In fact, if we pivot Q_{11} at 2, we get Q_{111} = Q_{11} \ {2} and Q_{112} = Q_{11}. cocone(2). We see that Q_{111} = Q_{12} and Q_{112} is mapped onto d(2^{n−1} + 3) by the automorphism η of P_{n+1} that fixes the atom 2^{0} and cycles the other atoms via 2^{n} ↦ ⋯ ↦ 2^{2} ↦ 2^{1} ↦ 2^{n}. Figure 8 shows η on B_{4}.

This gives

α(Q_{11}) = α(d(2^{n} + 3)) = α(Q_{12}) + α(d(2^{n−1} + 3)).  (11)

Finally we consider d(2^{n} +4) = {4, …, 2^{n} −1} and pivot it on 4. Obviously d(2^{n} +4)\{4} = Q_{2}. And d(2^{n} + 4). cocone(4) is mapped onto d(2^{n−1} + 4) by the automorphism ρ_{2,n−1} that exchanges the atoms 2^{2} and 2^{n−1}. This gives

α(d(2^{n} + 4)) = α(d(2^{n−1} + 4)) + α(Q_{2}).  (12)

[figure: 0 = η(0); 1 = η(1); 2 = η(4); 3 = η(5); 4 = η(8); 5 = η(9); 6 = η(12); 7 = η(13); 8 = η(2); 9 = η(3); 10 = η(6); 11 = η(7); 12 = η(10); 13 = η(11); 14 = η(14); 15 = η(15)]

Figure 8: The action of η on B_{4} = P_{16}.

Combining all these intermediate results we end up with

α(Q_{2}) = α(d(2^{n} + 4)) − α(d(2^{n−1} + 4)) by (12)  (13)
α(Q_{12}) = α(d(2^{n} + 3)) − α(d(2^{n−1} + 3)) by (11)  (14)
α(Q_{1}) = 2α(d(2^{n} + 3)) − α(d(2^{n−1} + 3)) by (9), (10) and (14)  (15)
α(Q) = 2α(d(2^{n} + 3)) + α(d(2^{n} + 4)) −  (16)
α(d(2^{n−1} + 4) − α(d(2^{n−1} + 3)) by (7), (13) and (15),

and this is Formula 12.

Formula 13. For every n ∈ ℕ with n ≥ 3, we have

Δ(2^{n} + 2^{2} + 2^{1}) = Δ(2^{n} + 6) = F (2^{n} − 4) + F (2^{n} − 5) + F (2^{n} − 6).

E.g., Δ(22) = F (12) + F (11) + F (10) = 53 + 78 + 84 = 215.

Proof. By definition the poset d(2^{n} + 2^{2} + 2^{1}) is P_{2^{n}+2^{2}+2^{1}}. cocone(2^{n} + 2^{2} + 2^{0}), which is P_{2^{n}+2^{2}} \ {0, 1, 4, 5, 2^{n}, 2^{n} + 1}. Let P denote d(2^{n} + 2^{2} + 2^{1}). First pivot P on the element 2^{n} + 2 + 1. We have P. cocone(2^{n} + 2 + 1) = P_{2^{n}} \ {0, 1, 2, 3, 4, 5}, which is dually isomorphic to P_{2^{n}−6}.

Let Q denote P \ {2^{n} + 2 + 1}. We pivot Q on the element 2^{n} + 2. We have

Q. cocone(2^{n} + 2) = P_{2^{n}} \ {0, 1, 2, 4, 5},

which is dually isomorphic to P_{2^{n}−5}. We also have Q \ {2^{n} + 2} = P_{2^{n}} \ {0, 1, 4, 5}, which is dually isomorphic to P_{2^{n}−4}. Thus, Δ(2^{n} + 2^{2} + 2^{1}) is the sum of F (2^{n} − 6), F (2^{n} − 5), and F (2^{n} − 4).

Formula 14. For every n ∈ ℕ with n ≥ 3, we have

Δ(2^{n} + 2^{2} + 2^{1} + 2^{0}) = Δ(2^{n} + 7) = F (2^{n} − 7) + F (2^{n} − 6) + Δ(2^{n} + 6).

E.g., Δ(23) = F (9) + F (10) + Δ(22) = 39 + 53 + 215 = 307.

Note that this formula for a Δ value involves both F values and a Δ value.

Proof. Let P be the poset

P = d(2^{n} + 2^{2} + 2^{1} + 2^{0}) = d(2^{n} + 7) = P_{2^{n}+7}. cocone(2^{n} + 6)
= (P_{2^{n}} \ {0, 2, 4, 6}) ∪ {2^{n} + 1, 2^{n} + 3, 2^{n} + 5}.

We pivot P on the element 2^{n} + 5.

Then P. cocone(2^{n} +5) = (P_{2^{n}} \{0, 1, 2, 4, 5, 6})∪{2^{n} +3}. We pivot P. cocone(2^{n} +5) on the element 2^{n} + 3 to get the posets P_{2^{n}} \ {0, 1, 2, 4, 5, 6} and P_{2^{n}} \ {0, 1, 2, 3, 4, 5, 6}. These are dually isomorphic to P_{2^{n}−6} and P_{2^{n}−7}, respectively.

We also have P_{2^{n}+5} = (P_{2^{n}} \ {0, 2, 4, 6}) ∪ {2^{n} + 1, 2^{n} + 3}. But then

d(2^{n} + 6) = P_{2^{n}+6}. cocone(2^{n} + 5) = (P_{2^{n}} \ {0, 1, 4, 5}) ∪ {2^{n} + 2, 2^{n} + 3},

which is isomorphic to the poset P_{2^{n}+5} by the automorphism ρ_{0,1} of the Boolean lattice B_{2^{m+1}} that interchanges the atoms 2^{0} and 2^{1} and leaves all the other atoms fixed. Hence the number of anti-chains in the poset P_{2^{n}+5} is equal to Δ(2^{n} + 6). Thus Δ(2^{n} + 7) = Δ(2^{n} + 6) + F (2^{n} − 6) + F (2^{n} − 7).

The proof of our final formula does not involve pivots but does make use of the inclusionexclusion argument of Lemma 5.

Formula 15. For every n ∈ ℕ with n ≥ 1, we have

Δ(2^{n} + 2^{n−1} + 1) = F (2^{n} + 2^{n−1} − 1) − 2 · F (2^{n} − 2).

E.g., Δ(25) = F (23) − 2 · F (14).

Proof. Let a = 2^{n} + 2^{n−1}, and let Q be the poset P_{a}. Then Q = {0, …, a − 1} and it is easily seen that d(a + 1) = Q \ {0, 2^{n−1}, 2^{n}} = Q. cosub(2^{n−1}, 2^{n}).

From Lemma 5 we infer that

α(Q) = α(Q. cosub(2^{n−1}, 2^{n})) + α(Q. cosuper(2^{n−1}) +
α(Q. cosuper(2^{n})) − α(Q. cosuper(2^{n−1}, 2^{n})).

Again it is easily seen that Q. cosuper(2^{n}) is equal to P_{2^{n}} and via the isomorphism ρ_{n−1,n} of P_{n+1} we see that Q. cosuper(2^{n−1}) is isomorphic to P_{2^{n}}.

Similarly we infer that Q. cosuper(2^{n−1}, 2^{n}) is equal to P_{2^{n−1}}.

Combining all these observations we see that

F (a) = Δ(a + 1) + 2 · F (2^{n}) − F (2^{n−1}).  (17)

Now by the definition of Δ, we have

F (a) = F (a − 1) + Δ(a)  (18)

and by Formula 10

Δ(a) = F (2^{n} − 2^{n−1}) = F (2^{n−1}).  (19)

Substituting first (18) and then (19) into (17) we get

Δ(a + 1) = F (a − 1) + 2 · F (2^{n−1}) − 2 · F (2^{n}).  (20)

By Formula 3 we have

F (2^{n}) = F (2^{n} − 2^{1}) + F (2^{n} − 2^{n−1}) = F (2^{n} − 2) + F (2^{n−1})  (21)

Finally substituting (21) into (20) we arrive at

Δ(a + 1) = F (a − 1) − 2 · F (2^{n} − 2),  (22)

which is Formula 15.

5 Summary

These are the formulas obtained so far.

For k, n ∈ ℕ with 0 < k < n Formula 3: F (2^{n}) = F (2^{n} − 2^{k}) + F (2^{n} − 2^{n−k}), Formula 6: F (2^{n}) = F (2^{n} − 2^{n−k} − 2^{n−k−1}) + 2F (2^{n} − 2^{k}) − F (2^{n} − 2^{k} − 2^{k−1}), Formula 7: Δ(2^{n} − 2^{k} + 1) = Δ(2^{n} − 2^{n−k} + 1), Formula 8: Δ(2^{n} − 2^{k} + 1) = Δ(2^{n} − 2^{k} − 2^{k−1} + 1) + Δ(2^{n} − 2^{n−k} − 2^{n−k−1} + 1), Formula 9: Δ(2^{n} − 2^{k}) = F (2^{n−1} − 2^{k}), Formula 10: Δ(2^{n} + 2^{k}) = F (2^{n} − 2^{k}), Formula 11: Δ(2^{n} + 2^{1} + 2^{0}) = F (2^{n} − 2) + F (2^{n} − 3), Formula 12: Δ(2^{n} + 2^{2} + 2^{0}) = 2 · Δ(2^{n} + 3) + Δ(2^{n} + 4) − Δ(2^{n−1} + 3) − Δ(2^{n−1} + 4), Formula 13: Δ(2^{n} + 2^{2} + 2^{1}) = F (2^{n} − 4) + F (2^{n} − 5) + F (2^{n} − 6), Formula 14: Δ(2^{n} + 2^{2} + 2^{1} + 2^{0}) = F (2^{n} − 7) + F (2^{n} − 6) + Δ(2^{n} + 6), Formula 15: Δ(2^{n} + 2^{n−1} + 1) = F (2^{n} + 2^{n−1} − 1) − 2 · F (2^{n} − 2).

An application of these formulas gives numerical values for the values of Δ for n = 16, …, 32—with the exception of Δ(26), where we leave it as an open question whether the formula given there is a special case of a more general one. Thus we have

Δ(16) = 1 by Formula 3, Δ(17) = F (15) = 167 by Formula 10, Δ(18) = F (14) = 148 by Formula 10, Δ(19) = F (13) + F (14) = 282 by Formula 11, Δ(20) = F (12) = 84 by Formula 10, Δ(21) = 2 · Δ(19) + Δ(20) − Δ(11) − Δ(12) = 617 by Formula 12, Δ(22) = F (12) + F (11) + F (10) = 215 by Formula 10, Δ(23) = F (9) + F (10) + Δ(22) = 307 by Formula 14, Δ(24) = F (8) = 20 by Formula 10, Δ(25) = F (23) − 2 · F (14) = 1692 by Formula 15, Δ(26) = F (18) + F (13) + F (11) + F (7) = 714, Δ(27) = Δ(25) − Δ(21) = 1075 by Formulas 7 and 8, Δ(28) = F (12) = 84 by Formula 9, Δ(29) = Δ(25) = 1692 by Formula 7, Δ(30) = F (14) = 148 by Formula 9, Δ(31) = F (15) = 167 by Formula 9, Δ(32) = 1 by Formula 3.

6 Acknowledgments

We acknowledge and thank the referee for the many suggestions that improved our paper.

References

[1] R. Balbes and P. Dwinger, Distributive Lattices, Univ. of Missouri Press, 1974.

[2] J. Berman and P. Köhler, Cardinalities of finite distributive lattices, Mitt. Math. Sem. Giessen 121 (1976), 103–124. Available at: https://oeis.org/A006356/a006356.pdf.

[3] G. Birkhoff, Lattice Theory, Amer. Math. Soc. Coll. Publ., Vol. 25, 3rd edition, 1967.

[4] F. a Campo and M. Erné, Exponential functions of finite posets and the number of extensions with a fixed set of minimal points, J. Combin. Math. Combin. Comput. 110 (2019), 125–156.

[5] M. Erné, Ordnungskombinatorik, Lecture Notes, University of Hannover, 2005.

[6] N. J. A. Sloane et al., On-Line Encyclopedia of Integer Sequences, available at https://

   oeis.org.

[7] D. Wiedemann, A computation of the eighth Dedekind number, Order 8 (1991), 5–6.

2020 Mathematics Subject Classification: Primary 06A07; Secondary 06A11, 06B25. Keywords: Dedekind number, anti-chain.

(Concerned with sequences \underline{A000372}, \underline{A006356}, \underline{A132581}, and \underline{A132582}.)

Received July 13 2021; revised versions received December 23 2021; December 27 2021. Published in Journal of Integer Sequences, December 27 2021.

Return to Journal of Integer Sequences home page.