Number of monotonic increasing Boolean
N functions of N variables
- --------------------------------------
0 2 (T, F)
1 3 (T, F, P)
2 6 (T, F, P, Q, P AND Q, P OR Q)
3 20
4 168 = 8 * 3 * 7
5 7581 = 3 * 7 * 19^2
6 7,828,354 = 2 * 359 * 10903 (Ouch!)
N from 0 to 4 suggest that a formula should exist, but 5 and 6 are
discouraging. A difficult generalization: Given two partial orderings, find
the number of maps from one to the other that are compatible with the ordering.
A related puzzle: A partition of N is a finite string of non-increasing
integers that add up to N. Thus 7 3 3 2 1 1 1 is a partition of 18. Sometimes
an infinite string of zeros is extended to the right, filling a half-line. The
number of partitions of N, P(N), is a fairly well understood function.The generating function is
infinity
======
\ n 1
> P(n) X = ------------------
/ infinity
====== /===\
n = 0 ! ! k
! ! (1 - X )
! !
k = 1
A planar partition is like a partition, but the entries are in
a two-dimensional array (the first quadrant) instead of a string.
Entries must be non-increasing in both the x and y directions. A
planar partition of 34 would be:
1 3 1 3 2 2 1 7 6 4 3 1Zeros fill out the unused portion of the quadrant. The number of planar partitions of n, PL(n), is not a very well understood function.
The generating function is
infinity
======
\ n 1
> PL(n) X = -------------------
/ infinity
====== /===\
n = 0 ! ! k k
! ! (1 - X )
! !
k = 1
No simple proof of the generating function is known. Similarly, one can define
cubic partitions with entries in the first octant, but no one has been able to
discover the generating function. Some counts for cubic partitions and a
discussion appear in Knuth, Math. Comp. 1970 or so.
Clue: (Stop! Perhaps you would like to work on this awhile.)
Lemma: Functions synthesizable with one NOT are those where the image of any upward path (through variable space) has at most one decrease (that is, from T to F).