## Saturday, April 24, 2010

### Board Game

## 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

**dimensions and**d

**boundaries. For example,**b

f(3,b) = 1 + b + ∑ + ∑

_{x=0..b−1}x

_{y=0..b−1}∑

_{x=0..y−1}x

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 +∑ =

1 +∑ =

1 + b +∑ =

1 +

_{x=0..b−1}f(d−1,x)

1 +

_{y=0..b−1}(1+∑

_{x=0..y−1}f(d−2,x))

1 + b +

_{y=0..b−1}∑

_{x=0..y−1}f(d−2,x)

Removing subscripts for brevity,

**1 + b +**∑∑f(d−2,x) =

∑ + ∑ + ∑ =

∑ + ∑ + ∑ =

∑ + ∑ + ... + ∑ + ∑ =

∑ + ∑ + ... + ∑ + ∑ =

∑

^{0}1

^{1}1

^{2}(1+∑f(d−3,x))

^{0}1

^{1}1

^{2}1+∑

^{3}f(d−3,x)

^{0}1

^{1}1

^{d−1}1

^{d}f(0,x)

^{0}

^{1}

^{d−1}

^{d}

_{x>−1,x<d+1,x<b+1}∑

^{x}

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

**, the triangular number**∑

^{2}

**. Now make a stack of pages with successive triangular numbers on them. The total number of points in the stack is**P

_{2}(b−1)

**, the tetrahedral number**∑

^{3}

**. In general,**P

_{3}(b−2)

**is the polytopic number**∑

^{d}

**P**. The diagonals of Pascal's triangle of binomial coefficients are the polytopic numbers. Thus,

_{d}(b−d+1)**, and**∑ = P =

^{d}

_{d}(b−d+1)

^{(b+1)!}/

_{d!(b−d+1)!}

**.**f(d,b) = ∑

_{x>−1,x<d+1,x<b+1}

^{(b+1)!}/

_{x!(b−x+1)!}