NUmber of linear dichotomies of a binary d-Dim space

[Danny L. Silver]

It is well known that a d-dimensional 2-class hypothesis space containing
n patterns in "general position" will have L(n,d) linear dichotomies
[see 1,2,3]; where L(n,d) is computed using a recursive equation:
    L(n,d) = L(n-1,d) + L(n-1,d-1)
with the boundary conditions of:    L(1,d) = 2 and L(n,1) = 2n.
This can also be stated as:
    L(n,d) = 2 SUM(i=0 to d) ( n-1 )   ; for n >  d
                             (  i  )  
    L(n,d) = 2^n                       ; for n <= d

Example:
d = 2, n = 4,  then:
L(4,2) = L(3,2) + L(3,1)
       = L(2,2) + L(2,1) + 2(3)
       = L(1,2) + L(1,1) + 4 + 6
       = 2 + 2 + 4 + 6
       = 14

Furthermore, there will be L(n,d)/2 (eg. 14/2 = 7) hyperplanes involved in 
partitioning the classes for the (eg. 14) dichotomies.

However, if the patterns are based on binary components, then the
pattern points are the vertices of a hypercube;  in which case the general
position condition does not hold and the L(n,d) value provides only an upper
bound on the number of linear dichotomies.  

Question:   Is there an expression/procedure for computing the exact
number of liner dichotomies of a binary d-dimensional hypothesis space?

Any information would be most helpful.

I will collect and summarize received replies on this matter.

.. Many thanks, Danny.


Ref:
(1) "The Mathematical Foundations of Learning Machines"  by Nils J.
Nilsson, Morgan Kaufman, San Mateo, CA;  1990 (originally published
in 1965 as"learning Machines").  -- p. 32-34

(2) "Neural Networks in Computing Intelligence" by LiMin Fu,
McGraw-Hill, inc, NY, 1994.  -- p. 71-73

(3) A set of n points are said to be in "general position" in a 
d-dimensional space iff no subset of d+1 points lies on any d-1
dimensional hyperplane.  In the case of a binary hypercube, this 
implies that no subset of d+1 pattern points may lie on any one
d-1 hypercube face.
-- 

=========================================================================
=  Daniel L. Silver    University of Western Ontario, London, Canada    =
=                      N6A 3K7 - Dept. of Comp. Sci. - Office: MC27b    =
=  dsilver at csd.uwo.ca  H: (519)473-6168   O: (519)679-2111 (ext.6903)   =
=========================================================================