Journal of Integer Sequences, Vol. 24 (2021), Article 21.10.7

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

P. Köhler
Mathematisches Institut
Justus-Liebig-Universität Giessen
Arndtstr. 2
35392 Giessen


We consider the sequence whose nth 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(2k). 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