## Dedekind's Problem

```A simple Boolean function maps n binary inputs to a single binary
output.  There are 2^n possible input states, each of which maps to
either 0 or 1 at the output.  Thus, the number of possible functions
of this form is 2^(2^n).  Each of these can be realized by means of
the elementary logic operations AND, OR, and NOT.

An important subset of all possible Boolean functions is the MONOTONE
functions, which consist of those functions that can be realized using
just AND and OR operations (no NOT operations).  For a more detailed
description, see Generating the Monotone Boolean Functions.

Dedekind's Problem is to determine the number M(n) of distinct monotone
functions of n variables. Although Dedekind first considered this
question in 1897, there is still no concise closed-form expression
for M(n).  As of 1999 the following values are known

n            M(n)
---  -----------------------
0                         2
1                         3
2                         6
3                        20
4                       168
5                      7581
6                   7828354
7             2414682040998
8   56130437228687557907788

Quite a lot of work has been done to prove upper and lower bounds on M(n),
but no closed-form expression is known.

One way of partitioning the number of distinct monotone functions
of n variables is to classify them according to the number of distinct
input states that map to the output value of 1.  For example, in the
case n=5 we have

# of events                      # of events
k     with k states              k     with k states

0           1                   17          605
1           1                   18          580
2           5                   19          530
3          10                   20          470
4          20                   21          387
5          35                   22          310
6          61                   23          215
7          95                   24          155
8         155                   25           95
9         215                   26           61
10         310                   27           35
11         387                   28           20
12         470                   29           10
13         530                   30            5
14         580                   31            1
15         605                   32            1
16         621                 Total        7581

As you would expect, this is a symmetrical partition.  Another way
of splitting up M(n) is according to the number of "mincuts" needed
to specify the function.  The mincuts of a monotone function consist
of the set of input states in that function, LESS the "redundant"
states.  (Given two states X and Y, the state X is redundant to Y iff
X U Y = Y.)  For example, the functions of 5 variables can be divided
up as follows:

# of distinct functions
k     with k mincuts

0          1
1         32
2        285
3       1090
4       2020
5       2146
6       1380
7        490
8        115
9         20
10          2

Total       7581

If we had a general formula for the number of distinct monotone
functions (of n variables) with k mincuts, we would have a solution
of Dedekind's Problem.  Let M(n,k) denote this number.

Obviously  M(n,0) = 1  and  M(n,1) = 2^n.  In addition, I've noticed
that
M(n,2) = (2^n)(2^n - 1)/2  -  (3^n - 2^n)

M(n,3) = (2^n)(2^n - 1)(2^n - 2)/6  -  (6^n - 5^n - 4^n + 3^n)

Does anyone know of similar formulas for M(n,k) with k > 3?

Postscript:  For the answer, see Progress on Dedekind's Problem.
```