Número de maneras de dividir un palo de entero de la longitud de $N$

Question

Supongamos que tenemos un palo de entero de la longitud de $N$. Estoy buscando (preferiblemente de forma cerrada) la fórmula que da el número de maneras en que podemos dividir el palo en 3 partes con distintos integral longitudes.

EDIT: Además, cada parte en cualquier división único largo que no aparece en ninguna otra división de $N$.

EDIT2: Basado en coffeemath la respuesta, sólo para aclarar, estoy interesado en el número máximo de las sumas $F(n)$. Dado que algunos $N$, contar el número de todas las posibles maneras de dividir stick $N$ en 3 partes tales que la longitud de cualquier parte en cualquier válida la división es el número único de entre $1$$N$.

Answer 1

La matriz $$\matrix{1&30&16&4&24&31&7&18&13&15&28\cr17&2&32&20&5&14&23&8&29&22&11\cr33&19&3&27&22&6&21&25&9&10&12\cr}$$ uses each integer $1,2,\puntos,33$ exactly once; each column sums to $51$ (so we have $11$ ways to divide a stick of length $51$ into three parts); and, as a bonus, each row sums to $187$. Hay una calculadora que se encuentra este tipo de cosas.

Se ha demostrado que un $m\times n$ magia rectángulo existe proporcionado $m$ $n$ tienen la misma paridad y exceder $1$, con la única excepción de $m=n=2$. Tomando $m=3$, esto le da una manera de dividir un palo de longitud $(9n+3)/2$ en tres partes en $n$ formas, donde a $n$ es arbitraria número impar superior a $1$. Está muy claro que el palo no puede ser dividido en tres partes, en más de $n$ maneras; si usted puede hacerlo en $k$ formas, los números utilizados deben sumar a $k(9n+3)/2$, sino que también debe agregar al menos,$3k(3k+1)/2$, y esto se ve fácilmente implicar $k\le n$.

En resumen, si $N$ es de la forma $(9n+3)/2$, $n$ no extraña, entonces el número de maneras es $(2N-3)/9$.

La magia rectángulos teorema ha sido demostrado, y las construcciones, y en muchos documentos. Uno, el que da las referencias a los demás, es Thomas R Hagedorn, Magia rectángulos revisited, Matemáticas Discretas, 207 (1999) 65-72. Por supuesto, la construcción es un poco exagerado para este problema, que en realidad no necesita una magia rectángulo, sólo necesitamos las columnas de sumas sean iguales y no se preocupan acerca de la fila sumas. He aquí una sencilla construcción que sólo resuelve la construcción original, sin dar una magia rectángulo: $$\matrix{1&2&3&4&5&6&7&8&9&10&11\cr17&18&19&20&21&22&12&13&14&15&16\cr33&31&29&27&25&23&32&30&28&26&24\cr}$$ El patrón debe ser clara.

EDIT: Ahora, supongamos $N$ no es de la forma $(9n+3)/2$ $n$ impar. Vamos a escribir $n'=n+1$$n''=n+2$, y $${9n+3\over2}\lt N\lt{9n''+3\over2}$$ for some odd $n$. First, we note that $F(N)\ge n$; if $N-(1/2)(9n+3)=k$, then just add $k$ to each entry in the bottom row in the construction above. and you have $n$ ways to divide $N$ into three parts. Second, note that $F(N)\le(2N-3)/9$, el argumento de un par de párrafos sobre la suma de los números involucrados. Así, obtenemos

1. Si $(1/2)(9n+3)\lt N\lt (1/2)(9n'+3)$,$f(N)=n$;

2. Si $(1/2)(9n'+3)\le N\lt(1/2)(9n''+3)$, $f(N)$ es $n$ o $n+1$.

En resumen, para cada $N$, tenemos una fórmula para $f(N)$ que es exacto en algunos intervalos, y se apaga en la mayoría de las $1$ en otros rangos. Sospecho que el $n+1$ es en general correcta, en la situación en la que no hemos fijado las cosas. Por ejemplo, para $N=20$, tenemos $$((9)(4)+3)/2\lt N\lt((9)(5)+3)/2$$ with the left inequality barely holding, and we get $f(20)=4$ from $$\matrix{1&2&3&4\cr5&7&8&6\cr14&11&9&10\cr}$$

Answer 2

Este es un ejemplo de la consecución de $a$ distintas sumas de dinero para un palo de longitud $6a$. No específico entero se produce dos veces en cualquier suma de dinero, o dos veces en dos diferentes sumas de dinero, o de forma más concisa todos los números que intervienen en las cantidades son distintas. Yo creo que es lo que el OP significa que en la declaración de la "EDITAR".

Los triples se $T_k=[k,3a-2k+1,3a+k-1]$ $1 \le k \le a.$ Cada uno triple, a continuación, tiene suma $6a$ como se desee, y los números utilizados son todas diferentes. La mitad de los números van de 2 $k$ se ejecuta a través de $\{1,2,...,a\}$ con el último de $3a-2a-1=a+1$, justo después de que el mayor número $a$ el primer plazo en triples, y el primer número del medio es el más grande de los números centrales a saber, $3a-2\cdot 1+1=3a-1,$ que es justo antes de que el menor de la tercera elementos de los triples, es decir,$3a+1-1=3a$. Después de que la tercera elementos de las tripletas aumentar en 1 de cada paso hasta llegar a la más alta tercer elemento del triple, es decir, $3a+a-1=4a-1$ (por Lo que el último triple $T_a$$[a,a+1,4a-1]$).

No sé si mejor que se puede hacer por un palo de longitud $6a$, pero no he sido capaz de demostrar que; puede ser que algunos otros sheme de conseguir diferentes triples podría dar más de $a$ sumas de dinero para la $6a$ palo largo. Lo que traté de hacer fue tener la mitad de los números bajando dos cada vez, y hacer que el bloque de comenzar justo después del final de la primera cuadra subiendo uno cada vez, y al final justo antes de que el bloque final que de nuevo se sube de uno en uno cada vez. No puedo pensar en una densa manera de empacar los triples.

Por el camino, en mi opinión, dada la restricción de ningún número que se utiliza dos veces en un solo triple, o incluso en cualquier lugar en la lista de tripletas obtenidos, el OP debe especificar si su pregunta es encontrar el número máximo de las sumas decir $F(n)$ para un determinado palo de longitud $n$, o en el otro lado tal vez el OP está interesado en una fórmula de tipo $F(n,t)$ para el número de maneras en que un palo de longitud $n$ puede ser cortado en tres partes en $t$ formas, no hay números repetidos. Esto último sería mucho más difícil, e incluso un comprobada fórmula para $F(n)$ parece difícil, al menos para mí.

EDITAR En esta construcción "en el medio de los números" son separadas 2 aparte. Y en la mayoría de los casos más triples pueden ser encontrados en los números no utilizados de la gama media. Por ejemplo, en el caso de $a=4$ con palo de longitud $6a=24$, $a=4$ triples formado mediante la construcción son

$[1,11,12],\ [2,9,13],\ [3,7,14],\ [4,5,15]$

Los números no utilizados de la gama media componen otro triple $[6,8,10],$, de modo que para varilla longitud de 24 uno puede encontrar de 5 triples.

Para el caso de $a=10$ (palo de longitud 60) además de los diez construye automáticamente se triplica, la falta de los números centrales son los nueve números del 12 al 28, y estos pueden ser puestos en las tres triples $[12,20,28],\ [14,22,24],\ [16,18,26].$, por Lo que para varilla de longitud 60 el número máximo de triples de al menos 13.

Answer 3

Supongo que sus longitudes tienen que ser números enteros. Deje $a, b,c$ ser las longitudes.

Desea $a+b+c=N$ $a,b,c$ pares distintos.

Puesto que la ecuación es homogénea en $a,b,c$ podemos encontrar las soluciones para que $a<b<c$ y, a continuación, por permuting tenemos todas las soluciones (por lo tanto el número de soluciones se multiplicará por 6).

Ahora bien, esto es un simple recuento de problema.

$N=a+b+c < 3c$, lo $c > \frac{N}{3}$. También se $c=N-a-b <N-2$.

Para cada uno de ellos fijo $\frac{N}{3} < c < N-2$ necesita contar todas las soluciones de la ecuación $a+b =N-c$ $a < b <c$ . Esto es muy fácil, ya que cualquier $b$, se obtiene un único $a$, la única cosa que tienes que asegurarte es que el $a < b <c$.

Después de encontrar este número, agregue esto por $c$ y se obtiene la fórmula...

Answer 4

Creo que usted está preguntando acerca de las particiones de un entero en partes distintas. Que es, usted está interesado en $$ q_k(N) := \# \{ (a_1, \dots, a_s) \; : \; a_1 > \dots > a_s > 0, \; \sum a_i = N \} $$ (e $s$ es permitido ser cualquier cosa). Se puede demostrar que los $q_k(N + \binom{k}{2}) = p_k(N)$ donde $p_k(N)$ es igual al número de particiones de $N$ exactamente $k$ partes. Entonces, si $N$ no es demasiado grande, usted puede calcular el $p_k(N)$ a través de la recurrencia $p_k(N) = p_{k-1}(N-1) + p_k(N-k)$. (Condiciones de Base se $p_k(k) = 1$ para todos los $k$, $p_{n-1}(n) = 1$, $p_1(n) = 1$, y $p_2(n) = \lfloor n/2 \rfloor$.)

Answer 5

Estos valores (donde el primer término es el recuento de $N=6$ aquí) formulario de secuencia A001339 en la Enciclopedia en Línea de Secuencias de Enteros.

El número de formas de partición de la $N$ en exactamente tres distintas entero positivo partes es igual al número de formas de partición de la $N-6$ en un máximo de tres (no negativo) enteros partes. La siguiente observación explica una correspondencia uno a uno: Si $N-6=a+b+c$ enteros no negativos $a \le b \le c$, $N = (a+1) + (b+2) + (c+3)$ es una partición de a $N$ en tres distintos entero positivo partes.

No hay forma cerrada es siempre en OEIS, por lo que uno puede suponer que no hay ninguna.

("Edit" (EDITAR comentario en la pregunta original es claro para mí, así que esto no puede ser la respuesta correcta.)