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

This is sequence A000372 in the On-Line Encyclopedia of Integer 
Sequences, which provides several references.  Quite a lot of work 
has been done to prove upper and lower bounds on M(n), but no one has 
been able to figure out a good closed form expression.

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.