Número de maneras de arreglar elementos de $n$ $m$ posiciones teniendo exactamente $k$ elementos adyacentes

Question

Fue hace más de 20 años desde que estudió matemáticas y estoy atascado. Agradecería algo de ayuda para entender esto (probablemente muy simple) problema.

He a $n$ artículos que me puede colocar en $m$ posiciones. $m$ ≥ $n$. El número total de combinaciones es el viejo y fiel a ${m \choose n}$, pero también necesito la partición de las combinaciones de k - el número de elementos directamente uno al lado del otro

Lo que estoy buscando es la mejor muestra con un par de ejemplos.

Cinco posiciones y de cuatro elementos pueden combinarse de dos maneras al $k$ es de cuatro, de dos maneras al $k$ es de tres y de una manera cuando $k$ es de dos

.

Cinco posiciones y tres elementos se pueden combinar de tres maneras al $k$ es de tres, seis maneras al $k$ es de dos y de una manera cuando $k$ es uno.

Cinco posiciones y un elemento que se puede combinar en cinco maneras al $k$ es uno.

Lo que estoy tratando de encontrar es una función de $f(m, n, k)$ que me dan el número de combinaciones para un cierto valor $k$. Por ejemplo:

$f(5, 3, 3)$ => $3$
$f(5, 3, 2)$ => $6$
$f(5, 3, 1)$ => $1$

Por supuesto, sumando el número de combinaciones para todos válido $k$${m \choose n}$.

Sólo jugando con la pluma y el papel que he observado en algunos casos el borde

$f(x, x, x)$ => $1$
$f(x, 1, 1)$ => $x$
$f(x, y, y)$ => $x-y+1$

Ayúdame, por favor!

Answer 1

Basta considerar la función de $g(m,n,k)$, que cuenta el número de maneras de seleccionar $n$ posiciones de $m$ que en la mayoría de los $k$ posiciones consecutivas escogidos; tenga en cuenta que $f(m,n,k)=g(m,n,k)-g(m,n,k-1)$. La función de $g$ satisface de una forma más simple recurrencia de $f$, es decir, $$g(m,n,k)=\begin{cases} {m\choose n},&n\le k\\ \sum_{r=1}^{k+1} g(m-r,n-r+1,k),&n>k \end{casos}$$ donde la suma surge de la ruptura de los casos de acuerdo a la ubicación de la última vacante de la célula.

Por inducción, podemos demostrar que, de fijo, $n$ y $k$, $g(m,n,k)$ es un polinomio en a $m$ grado $n$$m>k$. Esto es claro para $n\le k$ por las condiciones iniciales. Para $n>k$ vemos que $g(m,n,k)-g(m-1,n,k)$ es una suma de polinomios de grado $n-1, n-2, \ldots, n-k$, es decir, $g(m,n,k)-g(m-1,n,k)$ tiene el grado $n-1$. Así de diferencia finita de cálculo nos dice $g(m,n,k)$ es un grado $n$ polinomio; de hecho, nos dice cómo escribir este polinomio explícitamente, habiendo utilizado la recurrencia a generar $n+1$ términos. Que puede ser suficiente para sus necesidades.

Alternativamente, usted puede obtener una especie de forma cerrada mediante la generación de funciones. Indicar las celdas vacías por $0$ y llenos de células por $1$. Para cada una de las $r$$0\le r\le k$, definir un $r$-bloque $r$ $1$'s seguido por una $0$. Si queremos añadir temporalmente un extra de vacantes de la célula hasta el final, cada configuración válida puede ser el único descrito por la que se establecen una secuencia de $r$-bloques, por diversas $r$, por lo que el número total de $1$'s $n$ y el número total de células del es $m+1$. Tenga en cuenta que con el fin de obtener la densidad de $n$, tenemos que usar la $m+1-n$ bloques. Estándar exponencial generatingfunctionology implica que $g(m,n,k)$ es el coeficiente de $x^{m+1}\,z^{m+1-n}/(m+1-n)!$ en $$ G_k(x,z) := {\rm exp}\left( z(x + x^2 + \cdots + x^{k+1})\right).$$

(Básicamente, $z$ etiquetas el número total de bloques, por lo que el g.f. es exponencial en $z$, e $x$ etiquetas de las longitudes de los bloques. El $m$ se convierte en $m+1$ debido a que el extra de la celda vacía que hemos añadido.) Para llevar las cosas en un círculo completo, este dice:

$$ f(m,n,k) = \left[\frac{x^{m+1}\,z^{m+1-n}}{(m+1-n)!} \right]\left( G_k(x,z) - G_{k-1}(x,z)\right).$$

Answer 2

No hay ninguna fórmula simple, pero usted puede usar una simple propiedad recursiva para calcular de manera eficiente $f$.

Las condiciones de la frontera :

1. si $k>n$ o $n>m$ $f(m,n,k)=0$

2. si $k=m=n$ $f(m,n,k)=1$

Entonces, cualquier válido (m,n,k) configuraciones :

1. comienza con $i$ ocupado células seguido por una celda vacía y un $(m-i-1,n-i,k)$ configuración (para cualquier $i\le k$)
2. comienza con $k$ ocupado células seguido por una celda vacía y un $(m-k-1,n-k,i)$ configuración (para cualquier $i<k$)

$$f(m,n,k)=\sum_{i=0}^kf(m-i-1,n-i,k)+\sum_{i=0}^{k-1}f(m-k-1,n-k,i)$$

Using that, you can very efficiently compute $f$ with some dynamic programming. An example in python :

_db={}
def f(m,n,k) :
    if k>n or n>m: return 0
    if k==n and k==m : return 1
    if (m,n,k) in _db : return _db[(m,n,k)]
    _db[(m,n,k)]=sum(f(m-i-1,n-i,k) for i in range(k+1))
    _db[(m,n,k)]+=sum(f(m-k-1,n-k,i) for i in range(k))
    return _db[(m,n,k)]

And then compute $f(300,60,8) = 3093843836691461760481283005507531400353771346949728892427692$ en un par de segundos.