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