Friday, February 5, 2010

Counting Linear Regions

The question "how many" has motivated me in what little math I have done. For example, how many tetrahedron overlaps are there? That led me to the question of how many equivalent linear spaces there are. I used a recursive formula to define linear space in the first entry on this blog. Now I will present the closed form for f(d,b), the number of nonempty regions in a linear space of d dimensions and b boundaries. For example,
f(3,b) = 1 + b + x=0..b−1x + y=0..b−1x=0..y−1x
By definition,
f(d,b) =
f(d,b−1) + f(d−1,b−1) =
f(d,b−2) + f(d−1,b−2) + f(d−1,b−1) =
f(d,0) + f(d−1,0) + f(d−1,1) + f(d−1,2) + ... + f(d−1,b−1) =
1 + x=0..b−1f(d−1,x) =
1 + y=0..b−1(1+∑x=0..y−1f(d−2,x)) =
1 + b + y=0..b−1x=0..y−1f(d−2,x) =

Removing subscripts for brevity,
1 + b + ∑∑f(d−2,x) =
01 + 11 + 2(1+∑f(d−3,x)) =
01 + 11 + 21+∑3f(d−3,x) =
01 + 11 + ... + d−11 + df(0,x) =
0 + 1 + ... + d−1 + d =
x>−1,x<d+1,x<b+1x

I have always liked figurate numbers. For example, the triangular numbers are 1, 3, 6, 10, 15, .... Consider points on a page. Each line has one more point than the last. Then the total number of points is 2, the triangular number P2(b−1). Now make a stack of pages with successive triangular numbers on them. The total number of points in the stack is 3, the tetrahedral number P3(b−2). In general, d is the polytopic number Pd(b−d+1). The diagonals of Pascal's triangle of binomial coefficients are the polytopic numbers. Thus, d = Pd(b−d+1) = (b+1)!/d!(b−d+1)!, and f(d,b) = x>−1,x<d+1,x<b+1(b+1)!/x!(b−x+1)!.

No comments: