Contar el número de bases en un subconjunto

Question

Considere la posibilidad de $\mathbb{R}^n$ como un espacio vectorial sobre $\mathbb{R}$. Considerar el subconjunto $\mathrm{S}^n = \{(x_1,\ldots,x_n) \in \mathbb{R}^n | x_i = 0 \; \mathrm{or} \; 1\;\forall i = 1,\ldots,n\}$. ¿Cuántas bases de $\mathbb{R}^n$, $\mathrm{S}^n$ contienen? por ejemplo, para n = 2, $\mathrm{S}^2 = \{(0,0),(0,1),(1,0),(1,1)\}$ y contiene tres bases, es decir,$\{(0,1),(1,0)\},\;\{(0,1),(1,1)\},\textrm{ and }\{(1,0),(1,1)\}$. Quiero una expresión general para n.

Answer 1

Este es realmente un buen problema. Es fácil de entender, pero no es fácil de resolver.

He escrito un programa en madera de Arce para encontrar los primeros términos de la secuencia. Arce se queda atascado después de $n=5$ debido a que las cifras crecen de manera exponencial. (Mi programa es probablemente muy ineficiente demasiado y utiliza demasiada memoria RAM.)

Si $b_n$ indica el número de sub-bases, luego me sale la secuencia a: $(b_n) = (1,3,29,940,104286,\ldots)$

Una secuencia similar aparece en el on-line de la enciclopedia de secuencias de enteros. De hecho, la enciclopedia sugiere que $b_6 = 40050850$, $b_7 = 53640013886$ y $b_8 = 251995529844792.$

La secuencia de $(b_n)$ parece estar dado por $n! \cdot b_n = a_n$, donde obtener más información acerca de la secuencia de $(a_n)$ se puede encontrar aquí. En particular, el enlace anterior habla de la "Clasificación de pequeño $(0,1)$ matrices", y suministros de referencias bibliográficas.

En términos de tratar de resolverlo por ti mismo, bien, yo creo que un argumento inductivo puede ser muy exitoso. Aunque, no he gestionar para la construcción de uno mismo. Un hecho clave es que si se quita un elemento de base para $\mathbb{R}^n$ usted todavía está a la izquierda con una base para $\mathbb{R}^{n-1}.$ por el Contrario, las bases para $\mathbb{R}^n$ puede ser construido a partir de las bases de $\mathbb{R}^{n-1}.$ Si el tipo de vectores que usted necesita para agregar a una base de $\mathbb{R}^{n-1}$ a fin de obtener una base para $\mathbb{R}^n$, y usted sabe $b_{n-1}$, entonces usted sabrá $b_n.$ sospecho que usted será capaz de probar por inducción, una relación de recurrencia, que usted será capaz de resolver.

Por ejemplo, si usted sabe los elementos de $S^{n-1}$, entonces sólo es necesario agregar un número extra al final de cada elemento, una $0$ e una $1$, para obtener los elementos de $S^n.$