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.
Return to MathPages Main Menu