Cuántas secuencias $a_1,a_2,...,a_n$ en longitud $k$ así que $a_i \in \{1,2,3,4....,n\}$ satisfacer

Question

Tengo las siguientes dos preguntas:

Cuántas secuencias $a_1,a_2,...,a_n$ en longitud $k$ así que $a_i \in \{1,2,3,4....,n\}$ satisfacer :

1) $a_1<a_2<....<a_k$ mientras que $(a_{i+1} \neq a_i+1)$

2) $a_1 \leq a_2 \leq .... \leq a_k$ mientras que $(a_{i+1} \neq a_i+1)$

He reflexionado sobre estas cuestiones, si lo he entendido bien $a_1,...a_n$ son números por lo tanto la cuestión es elegir $k$ números sin números secuenciales pero me resulta difícil de resolver, he pensado en utilizar tal vez el principio de exclusión de la inclusión ya que no encuentro una manera de contar esto.

¿Alguna idea? Gracias.

Answer 1

De la longitud original $k$ secuencia $a_1,\dots,a_k$ formamos una biyección con la longitud relacionada $k+1$ secuencia $b_1,\dots,b_{k+1}$ donde

$b_i = \begin{cases} a_1&\text{if}~i=1\\ a_i-a_{i-1}&\text{if}~i\in\{2,3,\dots,k\}\\ n-a_k&\text{if}~i=k+1\end{cases}$

Observe que $b_1+b_2+b_3+\dots+b_{k+1} = a_1+(a_2-a_1)+(a_3-a_2)+\dots+n-a_k = n$ como los telescopios de la serie.

Dadas las condiciones que $1\leq a_1\leq a_2\leq a_3\leq\dots \leq n$ Esto implica las condiciones:

$\begin{cases}b_1+b_2+\dots+b_{k+1} = n\\ 1\leq b_1\\0\leq b_2\\ \vdots\\ 0\leq b_{k+1}\end{cases}$

Alternativamente, dadas las condiciones que $0<a_1<a_2<a_3<\dots a_k< n+1$ esto implica las condiciones:

$\begin{cases} b_1+b_2+\dots+b_{k+1} = n\\ 1\leq b_1\\ 1\leq b_2\\ \vdots\\ 1\leq b_k\\0\leq b_{k+1}\end{cases}$

Si se añade la condición adicional de que $a_i\neq a_{i-1}+1$ para cualquier $i$ ( nota: su error tipográfico $a_i\neq a_{i+1}+1$ es siempre verdadera ya que $a_i\leq a_{i+1}<a_{i+1}+1$ en ambos escenarios ), entonces esto es equivalente a añadir la restricción de que $b_i\neq 1$ para cualquier $i\in\{2,3,\dots,k\}$

En el caso de las desigualdades estrictas, esto se gestiona fácilmente haciendo el cambio de variable $c_1=b_1-1$ , $c_i = b_i-2$ para cada $i\in\{2,3,\dots,k\}$ . Enfoque como siempre con estrellas y barras.

En el caso de $a_1\leq a_2\leq\dots$ Entonces puedes acercarte como en mi respuesta para Número de formas de escribir $n$ como suma de $k$ enteros no negativos sin 1 iterando sobre cuántos y cuáles de los $b_i$ son cero.

---

Como un aparte y para que la respuesta sea más completa, la cuestión de encontrar cuántas soluciones enteras hay para el sistema:

$\begin{cases} x_1+x_2+\dots+x_k=n\\ 0\leq x_i~\text{for each}~i\end{cases}$

se puede encontrar a través de estrellas y barras y tiene respuesta $\binom{n+k-1}{k-1}=\binom{n+k-1}{n} = \left(\!\!\binom{n}{k}\!\!\right)$