Collares contadores

Question

Supongamos que tenemos un collar con $n$ cuentas. Cada cuenta es roja o azul. Me gustaría preguntar cómo se cuenta el número de collares $f(n,m,k)$ que satisfagan los siguientes requisitos:

1) Hay exactamente $m$ cuentas rojas; $(0 \leq m \leq n)$ .

2) No hay dos cuentas rojas adyacentes;

3) El número de cuentas azules con dos cuentas rojas adyacentes es $k$ exactamente.

Tenga en cuenta que la rotación del collar se cuenta de manera diferente. Por ejemplo, "azul azul rojo" es diferente de "rojo azul azul".

Algunos casos de prueba: $f(4,2,2)=2: \color{red}{1}0\color{red}{1}0, 0\color{red}{1}0\color{red}{1}$

$f(5,2,1)=5: 0\color{red}{1}011, 10\color{red}{1}01, 110\color{red}{1}0, 0110\color{red}{1}, \color{red}{1}0110$ , donde $0$ representa una cuenta roja y $1$ representa una azul. He coloreado las cuentas azules satisfaciendo el tercer requisito.

Tenga en cuenta que $a_n=\sum_{m,k}f(n,m,k)$ son Números de Lucas . También me he dado cuenta de que para los fijos $m$ y $k$ la serie $f(n,m,k)$ parece tener una función generadora que se parece a $\frac{a-bx}{(1-x)^c}$ donde $a$ , $b$ y $c$ son constantes relacionadas con $m$ y $k$ .

Answer 1

La fórmula mágica $$f(n,m,k)=2{m-1 \choose k-1}{n-2m-1\choose m-k-1}+3{m-1 \choose k}{n-2m \choose m-k}$$

Derivación

Cualquier collar que cumpla los tres requisitos tiene $m$ cadenas de una o más cuentas azules consecutivas bordeadas de cuentas rojas. Por lo tanto, debe tener $m-k$ cadenas de dos o más cuentas azules consecutivas.

Consideremos los collares que no contienen tres cuentas azules consecutivas (los llamaremos collares mínimos). Es evidente que $n=3m-k$ para un collar mínimo.

Consideraremos dos casos:

1. La primera cuenta es roja y las dos últimas son rojas y luego azules O la última cuenta es roja y las dos primeras son azules y luego rojas.
2. La primera y la última cuenta o las dos primeras cuentas o la última dos cuentas son azules.

Hay $2{m-1 \choose k-1}$ collares mínimos de tipo 1 y $3{m-1 \choose k}$ collares mínimos de tipo 1.

Por último, podemos utilizar el segundo teorema de estrellas y barras para calcular el número de formas de añadir un $n-3m+k$ bolas azules a un collar mínimo añadiéndolas a cadenas de dos o más bolas azules consecutivas.

Para los collares de tipo 1 existen $n-2m-1 \choose m-k-1$ formas de hacerlo.

Para los collares de tipo 2, las bolas azules pueden añadirse al principio o al final del collar para que haya $n-2m \choose m-k$ formas de hacerlo.

La conexión del número Lucas

Llamaremos bueno a un collar si no tiene cuentas rojas adyacentes. Como las rotaciones se cuentan de forma diferente, supondremos que cada collar tiene un lugar especial donde se pueden insertar las cuentas.

$a_n$ es el número de collares buenos de n cuentas. Puedo explicar por qué $a_n=a_{n-1}+a_{n-2}$ . Esta es la relación de recurrencia para los números de Lucas.

Cualquier buen collar de longitud $n-1$ puede convertirse en un buen collar de longitud $n$ insertando una cuenta azul.

Cualquier buen collar de longitud $n-2$ que tiene una cuenta roja adyacente a su ubicación especial puede convertirse en un buen collar de longitud $n$ insertando una cuenta azul y una roja, y hay un orden único en el que se pueden insertar estas dos cuentas.

Ahora considere los buenos collares de longitud $n-2$ que tienen dos cuentas azules adyacentes a su ubicación especial. Insertando primero una cuenta azul y luego una roja podemos crear un buen collar de longitud $n$ que no ha sido ya contabilizado. Obsérvese que, si la segunda cuenta que se inserta es azul, entonces acabamos añadiendo una cuenta azul a una longitud $n-1$ buen collar y crear un collar ya contado.