##
**
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

P. Köhler

Mathematisches Institut

Justus-Liebig-Universität Giessen

Arndtstr. 2

35392 Giessen

Germany

**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.

**
Full version: pdf,
dvi,
ps,
latex
**

(Concerned with sequences
A000372
A006356
A132581
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**