Número posible de conjuntos para dado N

Question

Cuántos posible válido colecciones están allí para un determinado número entero positivo N dadas las condiciones siguientes:

Todas las cantidades de 1 a N debería ser posible se hizo mediante la selección de algunos de los números enteros. También esto tiene que ser hecho en forma tal que si a cualquier número entero entre 1 y N puede ser hecho en más de una forma por la combinación de otros enteros, a continuación, que el conjunto de números enteros no es válido.

Por ejemplo, con N = 7, Las colecciones son válidos:{1,1,1,1,1,1,1},{1,1,1,4},{1,2,2,2},{1,2,4} No válido colecciones son: {1,1,1,2,2} porque la suma suma de 7 y 2 pueden ser realizados por {1,1} y {2}, 3 puede ser hecha por {1,1,1} y {1,2}, 4 puede ser hecha por {1,1,2} y {2,2} y de manera similar, 5, 6 y 7 también se puede hacer en varias formas utilizando el mismo conjunto. {1,1,3,6} porque todos los de 1 a 7 puede ser únicamente hechos, pero la suma no es 7 (11).

Answer 1

Estas son las particiones perfectas en OEIS. a(n-1) = suma de todas a(i-1) que divide a n y i < n.

Answer 2

El término yo uso es el "conjunto múltiple". Tenga en cuenta que su conjunto múltiple debe contener 1 (ya que esta es la única manera de obtener una suma de 1). Supongamos que hay $r$ diferentes valores de $a_1 = 1, \ldots, a_r$ en el conjunto múltiple, con $k_j$ copias de $a_j$. A continuación, debemos tener $a_j = (k_{j-1}+1) a_{j-1}$$j = 2, \ldots, r$, e $N = (k_r + 1) a_r - 1$. Trabajando hacia atrás, si $A(N)$ es el número de multisets sumar a $N$, para cada factorización $N+1 = ab$ donde $a$ $b$ son enteros positivos con $b > 1$ usted puede tomar $a_r = a$, $k_r = b - 1$, junto con cualquier válido conjunto múltiple de sumar a $a-1$. Por lo tanto $A(N) = \sum_{b | N+1, b > 1} A((N+1)/b - 1)$$N \ge 1$,$A(0) = 1$. Tenemos, entonces, si he programado la derecha, 1, 1, 2, 1, 3, 1, 4, 2, 3, 1, 8, 1, 3, 3, 8, 1, 8, 1, 8, 3 para $N$ de 1 a 20. Esto coincide con OEIS secuencia A002033, "Número perfecto de particiones de n".

Answer 3

Suponga que la colección contiene un conjunto finito de distintos números de $\{n_1 ... n_k\}$ y que la colección contiene el número $n_i$ $t_i$ veces (también se puede suponer que el $n_i$ son ordenados) Luego, su condición es la de que para cada número $x$ entre 0 y $N$, $x$ puede ser escrito como $x = \Sigma u_i n_i$ $0 \leq u_i \leq t_i$ exactamente de una manera.

Esto es posible si y sólo si $n_1 = 1$, forall $i$, $n_i = \Sigma_{j\lt i} t_i n_i$, y $N = \Sigma t_i n_i$.

Usted puede probar esta haciendo una inducción en $k$, a partir de $k=N=0$ para el caso base. El caso base es fácil. La inducción no es un caso difícil :

Si usted tiene una colección que contenga $k$ términos distintos que pueden hacer todos los números hasta el $N_k$, entonces la única manera de extender en una colección más grande es mediante la adición de $n_{k+1} = N_k+1$. Si tienes que elegir un número más pequeño, a continuación, $n_{k+1}$ se puede escribir de dos maneras, si tienes que elegir un número más alto, entonces usted no puede hacer $N_k+1$. Y entonces, si usted tiene una colección de $k+1$ términos, entonces el sub-colección que contiene la primera $k$ términos distintos que también es válido y tiene que escribir cada número hasta el $n_{k+1}-1$ para el mismo tipo de razones.

Por lo tanto, válido colección de $k$ términos distintos que hace que cada número hasta el $N$ está determinado por la secuencia de $(n_1=1, \ldots n_k, n_{k+1}=N+1)$ donde $n_i$ divide $n_{i+1}$ : $$n_i = \Sigma_{j \lt i} t_j n_j = n_{i-1} + t_{i-1} n_{i-1} = (t_{i-1} + 1) n_{i-1}$$ Así que esto demuestra por qué son sucesivas de los múltiplos de cada uno de los otros y de cómo recuperar la $t_i$ a partir de la secuencia.

El 4 colecciones que dio como ejemplo se corresponden, respectivamente, a las secuencias de $(1,8), (1,2,8), (1,4,8), (1,2,4,8)$.

El número de secuencias válidas depende de los exponentes en el primer descomposición de $N+1$ : si $N+1$ es una fuente primaria de energía $p^a$, entonces hay exactamente $2^{a-1}$ secuencias válidas, ya que tienes que elegir si usted escoge $p^i$ o no $0 \lt i \lt a$.

Si $N+1$ tiene varios primos divisores, creo que no es una buena fórmula de dar el número de colecciones desde el conjunto múltiple de los exponentes en el primer factorización de $N+1$.