Número de agrupaciones de varios subconjuntos de combinaciones utilizando un algoritmo codicioso

Question

Esta pregunta está relacionada con la que hice anteriormente.

Considerar en orden todos los ${n + k - 1\choose k}$ formas de elección de $k$ enteros de $\{0,n-1\}$ con repeticiones. Por ejemplo, si $n=5$ $k=3$ tenemos:

(0, 0, 0),
(0, 0, 1),
(0, 0, 2),
(0, 0, 3),
(0, 0, 4),
(0, 1, 1),
[...]

Vamos ahora a considerar cada combinación como un multi-subconjunto de los números enteros.

Mirar esta lista de arriba a abajo, me gustaría grupo consecutivo de múltiples subconjuntos juntos en un codicioso, de manera que el tamaño de la intersección de todos los multi-subconjuntos de un grupo es, al menos,$k-1$.

Para $n = 5, k = 3$, las agrupaciones quedaría como sigue:

(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (0, 0, 4)
(0, 1, 1), (0, 1, 2), (0, 1, 3), (0, 1, 4)
(0, 2, 2), (0, 2, 3), (0, 2, 4)
(0, 3, 3), (0, 3, 4)
(0, 4, 4)
(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4)]
(1, 2, 2), (1, 2, 3), (1, 2, 4)]
(1, 3, 3), (1, 3, 4)
(1, 4, 4)
(2, 2, 2), (2, 2, 3), (2, 2, 4)
(2, 3, 3), (2, 3, 4)
(2, 4, 4)
(3, 3, 3), (3, 3, 4)
(3, 4, 4), (4, 4, 4)

Estoy interesado en el número de agrupaciones que se obtiene por este algoritmo voraz. Podemos ver que para $n = 5, k = 3$ el número de es $14$.

Para $n = 4, k = 4$ creo que el siguiente $17$ agrupaciones.

(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 0, 2), (0, 0, 0, 3)
(0, 0, 1, 1), (0, 0, 1, 2), (0, 0, 1, 3)
(0, 0, 2, 2), (0, 0, 2, 3)
(0, 0, 3, 3)
(0, 1, 1, 1), (0, 1, 1, 2), (0, 1, 1, 3)
(0, 1, 2, 2), (0, 1, 2, 3)
(0, 1, 3, 3)
(0, 2, 2, 2), (0, 2, 2, 3)
(0, 2, 3, 3), (0, 3, 3, 3)
(1, 1, 1, 1), (1, 1, 1, 2), (1, 1, 1, 3)
(1, 1, 2, 2), (1, 1, 2, 3)
(1, 1, 3, 3)
(1, 2, 2, 2), (1, 2, 2, 3)
(1, 2, 3, 3), (1, 3, 3, 3)
(2, 2, 2, 2), (2, 2, 2, 3)
(2, 2, 3, 3), (2, 3, 3, 3)
(3, 3, 3, 3)

Es posible dar una fórmula exacta para este número de enteros positivos arbitrarios $n> k$?

---

Para $n = 2, 3, 4, 5$ I calcula la respuesta de $k = 1,\dots 20$.

• $n = 2$ da 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11.

Esta es una simple secuencia.

• $n = 3$ da 1, 3, 5, 8, 11, 15, 19, 24, 29, 35, 41, 48, 55, 63, 71, 80, 89, 99, 109, 120

Esto se esta OEIS secuencia. El hecho interesante es que las diferencias entre números consecutivos es exactamente la secuencia de $n = 2$.

• $n = 4$ da $1, 4, 9, 17, 28, 43, 62, 86, 115, 150, 191, 239, 294, 357, 428, 508, 597, 696, 805, 925$. Este es OEIS A005744.

De nuevo las diferencias entre números consecutivos es exactamente la secuencia de $n = 3$.

• $n = 5$ da $1, 5, 14, 31, 59, 102, 164, 250, 365, 515, 706, 945, 1239, 1596, 2024, 2532, 3129, 3825, 4630, 5555$.

Esto no está en la OEIS, pero de nuevo las diferencias entre números consecutivos es exactamente la secuencia de $n = 4$.

Answer 1

Como con la pregunta anterior, las diferencias de patrón que usted señala de la siguiente manera a partir de la observación de que el algoritmo voraz, nunca poner $(0,n-1,n-1,\dots,n-1)$ $(1,1,1,\dots,1)$ en el mismo grupo de las $n>2$. Como resultado, podemos por separado averiguar lo que el algoritmo voraz que hace a la multi-subconjuntos que comienzan con $0$, y lo que hace a la multi-subconjuntos que comienzan con $1, 2, \dots, n$.

Deje $m(n,k)$ el número de multi-subconjunto de las agrupaciones el algoritmo voraz que nos da. A continuación, para$n>2$$k>1$, tenemos:

1. El multi-subconjuntos de partida con $0$ todos de acuerdo en que el primer elemento. Así que si ignoramos el líder de $0$, estamos dividiendo multi-subconjuntos de tamaño $k-1$ en grupos por el algoritmo voraz, y nos pondremos $m(n,k-1)$ agrupaciones de allí.
2. El resto de la multi-subconjuntos no incluyen $0$ a todos. Así que sólo uso el $n-1$ valores de $\{1,2,\dots,n-1\}$, y nos pondremos $m(n-1,k)$ agrupaciones de allí.

Así, por $n>2$$k>1$,$m(n,k) = m(n,k-1) + m(n-1,k)$.

Al $k=1$, podemos poner todos los de un elemento multi-subconjuntos en una agrupación, por lo $m(n,1) = 1$.

Al $n=2$, nuestro multi-subconjuntos $\{00\dots00, 00\dots01, 00\dots11,\dots, 01\dots11, 11\dots11\}$. Cada uno comparte $k-1$ elementos con el multi-subconjunto siguientes en el orden lexicográfico, pero sólo $k-2$ con el de después, así que todos nuestros grupos son de tamaño $2$, posiblemente con la excepción de la última multi-subconjunto. Hay $k+1$ multi-subconjuntos, por lo $m(2, k) = \left\lceil\frac{k+1}{2}\right\rceil$.

---

Hasta ahora, hemos confirmado que los patrones en sus cálculos continuar. El obstáculo para encontrar una forma cerrada para $m(n,k)$ es que el caso base $\left\lceil\frac{k+1}{2}\right\rceil$ es muy molesto para tratar con.

Podemos encontrar una fórmula fija $n$ que casi polinomio en $k$ mediante la observación de que $\delta(n,k) = \frac{(-1)^k}{2^n}$ también satisface la relación de recurrencia $$\delta(n,k) = \delta(n-1,k) + \delta(n,k-1)$$ and therefore $m(n,k) - \delta(n,k)$ does, too. We have $m(2,k) - \delta(2,k) = \frac{k}{2} + \frac34$, which is exactly linear in $k$, and from the formula $$m(n,k) - \delta(n,k) = m(n,1) -\delta(n,1) + \sum_{j=2}^k \bigl(m(n-1,j) - \delta(n-1,j)\bigr)$$ we can get a quadratic formula for $m(3,k) -\delta(3,k)$, a cubic formula for $m(4,k)-\delta(4,k)$, y así sucesivamente.

Nos puede encontrar todos los de $m(n,k)$ en la OEIS mirándolo como la tabla triangular $$\begin{matrix} 1 \\ 1 & 2 \\ 1 & 3 & 2 \\ 1 & 4 & 5 & 3 \\ 1 & 5 & 9 & 8 & 3 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{de la matriz}$$ donde el $j^{\text{th}}$ diagonal desde la parte superior es la secuencia de las $m(j+1,k)$. (Este es un truco útil cuando se tiene una secuencia con dos parámetros.) Lectura por filas, este triángulo es la secuencia de A181971 en la OEIS, pero no es cerrado fórmula.

También podemos encontrar las desigualdades de delimitación $m(n,k)$ que nos permiten, al menos, se derivan de la asymptotics.

• Si definimos $m_-(n,k) = \frac12\binom{n+k-2}{k-1}$,$m_-(n,1) = \frac12 \le m(n,1)$$m_-(2,k) = \frac k2 \le m(2,k)$. También, $m_-(n,k) = m_-(n-1,k) + m_-(n,k-1)$, por lo que podemos inductivamente demostrar que $m_-(n,k) \le m(n,k)$ todos los $k$.
• Si definimos $m_+(n,k) =\binom{n+k-2}{k-1}$,$m_+(n,1) = 1 \ge m(n,1)$$m_+(2,k) = k \ge m(2,k)$. También, $m_+(n,k) = m_+(n-1,k) + m_+(n,k-1)$, por lo que podemos inductivamente demostrar que $m_+(n,k) \ge m(n,k)$ todos los $k$.

Por lo tanto, tenemos $$\frac12 \binom{n+k-2}{k-1} \le m(n,k) \le \binom{n+k-2}{k-1}$$ for all $n \ge 2$ and $k \ge 1$, which lets us estimate $m(n,k)$ to within a factor of $2$.