Número de secuencias unimodulares

Question

Una secuencia $c_1 , c_2, ... , c_k$ sobre {1,...,n} se llama unimodular si se cumple que hay un $1 \leq i \leq k $ tal que $c_1 \leq c_2 \leq ... \leq c_i \geq c_{i+1} \geq... \geq c_k$ .

¿Alguien conoce una forma cerrada para contar Secuencias Unimodulares de longitud k sobre un alfabeto de tamaño n? No creo que sea fácil, tal vez utilizando algunas funciones generadoras.

Pero también serían interesantes los límites asintóticos.

Answer 1

A continuación expongo cómo lo resolvería yo. Es probable que existan soluciones más cortas:

1) Primero definimos una función $f(m,l)$ que cuenta secuencias decrecientes de longitud $l$ con límite superior $m$ . Vemos que $f(m,l) = C(m,l)$ ya que corresponde a la elección de un $l$ -de un subconjunto de elementos de un $m$ -conjunto de elementos.

2) Vemos que hay $l+1$ formas de formar tuplas $(a,b)$ s.t. $a+b = l$ . Estos son $(0,l), (1,l-1), \ldots, (l-1,1), (l,0)$ .

Con esto, contamos

$g(l) = \sum_{j=0}^l \sum_{i=1}^n f(i-1, j) \cdot f(i-1,l-j)$

para obtener el número de secuencias de longitud total $l+1$ (el valor máximo, $i$ se empalma en medio de las secuencias).

3) Ahora las secuencias deben ser "rellenadas" con elementos repetitivos. Este es esencialmente el problema de $k$ bolas indistinguibles en $l$ cajas distinguibles.

Esto se suma para todos los $l$ .

$\sum_{l=1}^k  C(l + k - 1, k) \cdot g(l-1)$

da el número de secuencias unimodulares.

La fórmula cerrada podría existir, y Maple/Mathematica podría incluso servírtela directamente :-).

Answer 2

Considere la secuencia $1,2,\dotsc,m,\dotsc,2,1$ . Distribuir $k-1$ en cualquier lugar antes de cualquiera de los números (pero no después del último $1$ ), y colocar un $k$ -antes del marcador $m$ ; entonces los números detrás de los marcadores forman una secuencia unimodular con el valor más alto $m$ y estas secuencias están en correspondencia uno a uno con las formas de colocar estos marcadores. Hay

$$\binom{2m-2+k-1}{k-1}=\binom{2m+k-3}{k-1}$$

tales formas, y sumando sobre todos los valores posibles de $m$ rinde

$$ \sum_{m=1}^n\binom{2m+k-3}{k-1} $$

para el número total de secuencias unimodulares. Wolfram|Alpha tiene una especie de forma cerrada para esto, pero no se ve muy bien.