Progress on Dedekind's Problem

```The note Dedekind's Problem defines the set of monotone Boolean (i.e.,
functions expressible using only AND and OR logical operations), and
discusses the problem of enumerating all the monotone functions of n
variables.  One approach is to consider M(n,k), which is the number of
monotone Boolean functions of n variables with exactly k mincuts.
The following is a table giving M(n,k) for the first several values
of n:

M(n,k), the number of distinct monotone Boolean
functions of n variables with k mincuts
-----------------------------------------------
n
k     0    1    2     3      4       5         6        7         8
---   ---  ---  ---  ----  -----   -----    ------   ------  --------
0     1    1    1     1      1       1         1        1         1
1     1    2    4     8     16      32        64      128       256
2               1     9     55     285      1351     6069     26335
3                     2     64    1090     14000   153762   1533504
4                           25    2020     82115  2401910  58089465
5                            6    2146    304752     :         :
6                            1    1380    759457     :         :
7                                  490   1308270
8                                  115   1613250
9                                   20   1484230
10                                    2   1067771
11                                         635044
12                                         326990
13                                         147440
14                                          57675
15                                          19238
16                                           5325
17                                           1170
18                                            190
19                                             20
20                                              1
---  ---  ---   ---   ----   -----   -------
Tots   2     3    6    20    168    7581   7828354

In the previous note I gave the formulas for M(n,k) with k=0,1,2,3
as follows

M(n,0) = 1

M(n,1) = 2^n

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)

These formulas give the horizontal rows of the preceding table,
including the leading zeros.  Its clear from these cases that, in
general, M(n,k) must be expressible as a sum of the form

1   2^n
M(n,k)  =  --- SUM   c_m  m^n
n!  m=2

for some integer coefficients c_m.  In the original version of this
note I asked if anyone knew the formulas for M(n,k) with k > 3.  This
was also Problem #7 on my Most Wanted List.

In September of 1999 I received an email from Vladeta Jovovic informing
me that he, G. Kilibarda, and Z. Maksimovic of the University of
Belgrade are preparing a paper in which they give the expressions
for M(n,k) for k = 4 to 10.  They were kind enough to send me these
expressions, and they are fascinating.  As one would expect, they are
of the form noted above, and consequently the summation for k=10 has
roughly 2^10 =1024 terms, less the number of terms for which the
coefficient c_m happens to be zero.

With k=4 we seek a formula M(n,4) that gives the values from the 4th
row of the table above, i.e.,

0   0   0   0   25   2020    82115   2401910    58089465  ...

for n = 0,1,2,...  The formula found by Jovovic, Kilibarda, Maksimovic
for k=4 is

1   /  n        n        n     n       n      n       n
M(n,4) = --- ( 16  - 12*12  + 24*10 + 4*9  - 18*8  + 6*7  - 36*6
4!  \

n       n       n      n \
+ 36*5  + 11*4  - 22*3  + 6*2   )
/

There are some very interesting patterns in the coefficients c_m of
these expressions.  Looking at the highest powers with non-zero
coefficients, we have

k
---
2      4^n  -   2 *  3^n  +    1 *   2^n
3      8^n  -   6 *  6^n  +    6 *   5^n  +    3 *   4^n  + ...
4     16^n  -  12 * 12^n  +   24 *  10^n  +    4 *   9^n  + ...
5     32^n  -  20 * 24^n  +   60 *  20^n  +   20 *  18^n  + ...
6     64^n  -  30 * 48^n  +  120 *  40^n  +   60 *  36^n  + ...
7    128^n  -  42 * 96^n  +  210 *  80^n  +  140 *  72^n  + ...
8    256^n  -  56 *192^n  +  336 * 160^n  +  280 * 144^n  + ...
9    512^n  -  72 *384^n  +  504 * 320^n  +  504 * 288^n  + ...
10   1024^n  -  90 *768^n  +  720 * 640^n  +  840 * 576^n  + ...

Clearly the bases tend to double at each level, once the pattern is
initiated.  Also, the coefficients fall into easily recognizable
sequences.

We can also examine the coefficients of the lowest powers in each
expression.  It appears that these are closely related to the Stirling
numbers of the first kind.  If we denote the absolute values of the
Stirling numbers by S{m,n}, indexed as shown below

n
1     2     3     4     5     6     7     8
m   ----- ----- ----- ----- ----- ----- ----- -----
---
1      1     0     0     0     0     0     0     0
2      1     1     0     0     0     0     0     0
3      2     3     1     0     0     0     0     0
4      6    11     6     1     0     0     0     0
5     24    50    35    10     1     0     0     0
6    120   274   225    85    15     1     0     0
7    720  1764  1624   735   175    21     1     0
8   5040 13068 13132  6769  1960   322    28     1

then the non-zero coefficients of the lowest powers are as summarized
below

Term             Coefficient
-----   -----------------------------------
2^n     1 S{k,1}
3^n    -2 S{k,2}
4^n     1 S{k,2}
5^n     6 S{k,3}
6^n    -6 S{k,3}
7^n     6 S{k,4}
8^n     1 S{k,3} -  24 S{k,4}
9^n     4 S{k,4}
10^n    24 S{k,4}
11^n    20 S{k,5}
12^n   -12 S{k,4} - 120 S{k,5}
13^n   120 S{k,5}
14^n   150 S{k,5}
15^n  -120 S{k,5} -  20 S{k,6}
16^n     1 S{k,4} - 120 S{k,5} + 180 S{k,6}
17^n    10 S{k,5} - 360 S{k,6}
18^n    20 S{k,5} - 240 S{k,6}
19^n   750 S{k,6}
20^n    60 S{k,5} + 480 S{k,6}
21^n  -540 S{k,6}
22^n  -240 S{k,6}
23^n  -720 S{k,6} +  70 S{k,7}
24^n   -20 S{k,5} - 180 S{k,6} - 840 S{k,7}
25^n    36 S{k,6} +2520 S{k,7}

and so on.  Placing the coefficients of the Stirling numbers into a
table, we have

Multiplier of Stirling Number S{k,j} in Coefficient of Term
Term    1    2    3     4     5      6     7      8      9    10
----   ---  ---  ---  ----  ----   ----  -----  -----  ----  -----
2^n    1
3^n        -2
4^n         1
5^n              6
6^n             -6
7^n                    6
8^n              1   -24
9^n                    4
10^n                   24
11^n                          20
12^n                  -12   -120
13^n                         120
14^n                         150
15^n                        -120    -20
16^n                    1   -120    180
17^n                          10   -360
18^n                          20   -240
19^n                                750
20^n                          60    480
21^n                               -540
22^n                               -240
23^n                               -720     70
24^n                         -20   -180   -840
25^n                                360   2520
26^n                                480    420
27^n                                120  -7560
28^n                                810  -2520
29^n                                     13860
30^n                               -720   6580
31^n                                     -8400     70
32^n                           1   -360  -2520  -1120           -1
---  ---  ---   ---     ---
Sum    1   -1   1    -1       1

Is there a simple way of determining these coefficients for arbitrary
terms?  The "roundness" of these numbers, and the fact that each
column sums to +-1, suggests that there might be a useful combinatorial
interpretation.
```