Vale la pena señalar que el problema es equivalente a la siguiente:
¿Cuál es el máximo número de células de un arreglo de $n$ hyperplanes puede dividir $\mathbb R^k$ a?
Aquí, yo uso "hyperplane" como en "codimension $1$ subespacio". Más útil, supongamos que representan este tipo de acuerdo como el número de no-cero mapas de $f_1,\ldots,f_n$ $f_i:\mathbb R^k\rightarrow\mathbb R$ y el hyperplanes en la disposición de ser el núcleo de cada mapa. Una célula es entonces un subconjunto de a $\mathbb R^k$ con un determinado signo para cada una de las $f_i$ - por ejemplo, el conjunto donde cada una de las $f_i$ es positivo es una celda (si no está vacío).
De esta reducido el problema a la suya, definir un mapa de $f:\mathbb R^k\rightarrow \mathbb R^n$
$$f(x)=(f_1(x),f_2(x),\ldots,f_n(x)).$$
Nos encontramos con que $f(\mathbb R^k)$ es un subespacio de dimensión $k$ $\mathbb R^n$ de manera tal que la imagen de cualquier célula es exactamente la intersección de que hyperplane con algunos cuadrante y la preimagen de un cuadrante es exactamente una celda. Por lo tanto, hay el mismo número de células en el arreglo, ya que hay cuadrantes interceptada por los asociados en el subespacio.
Para llegar desde tu problema a la reducción de uno, elegir un lineal arbitraria y bijective mapa de $\pi:S\rightarrow \mathbb R^k$ donde $S$ es el subespacio de dimensión $k$ en cuestión. Luego, se definen $f_i(\pi(x))$ a la igualdad de $x_i$, es decir, cada una de las $f_i$ da $i^{th}$ coordenadas de $\pi^{-1}(x)$. El núcleo de cada una de las $f_i$ será la imagen de la hyperplanes $x_i=0$ bajo $\pi$ y cada célula será la proyección de un cuadrante. Juntos, estos bastan para mostrar que los problemas son equivalentes.
Creo que es más fácil conseguir un asimiento en esta modificado el problema. En particular, supongamos que tenemos un arreglo de $n$ hyperplanes $H_1,\ldots,H_n$ $\mathbb R^k$ y añadir un poco de hyperplane $H'$ a él y desea saber cuántos más células fueron creados por este hyperplane. Así, obtenemos las células más exactamente al $H'$ se divide una célula existente en dos. Podemos encontrar cuántas veces $H'$ ¿ que considerando las células inducidas en $H'$ por el hyperplanes $H_1\cap H',\ldots,H_n\cap H'$. Es decir, las nuevas células en $\mathbb R^k$ creado mediante la adición de la hyperplane $H'$ corresponden a las células en un $k-1$ dimensiones disposición de $n$ hyperplanes.
Dejando $F(n,k)$ ser el máximo número de células en dicho acuerdo, se obtiene la relación
$$F(n+1,k)\leq F(n,k) + F(n,k-1).$$
Uno puede encontrar, más fuerte, que si usted elige un conjunto de $n$ hyperplanes tal que la intersección de cualquier $n+1$ de ellos es un punto (es decir, de modo que están en posición general) que esta enlazado se obtiene (esto puede ser demostrado por inducción), así
$$F(n+1,k)=F(n,k) + F(n,k-1).$$
A continuación, tenemos las condiciones iniciales
$$F(1,k)=2$$
$$F(n,1)=2.$$
Estos únicamente especificar la función. Uno puede usar esto para probar, por inducción, la fórmula:
$$F(n,k)=2\sum_{d=0}^k{n-1 \choose d}.$$
