Encuentre el número de ordenados $k$ -tuplas

Question

Dejemos que $n$ sea un número entero positivo. Hallar el número de ordenadas $k$ -tuplas $(a_1,a_2, \ldots, a_k), k\le n$ de $\{1,2,\ldots, n\}$ que satisfaga al menos una de las condiciones:

1. Existen $ s,t\in \{1,2,\ldots, k\} $ tal que $ s<t $ et $ a_s> a_t $ ,
2. Existen $ s \in \{1,2,\ldots, k\} $ tal que $ a_s -s $ es un número impar.

No entiendo cómo empezar. Por favor, ayúdenme. Gracias de antemano.

Answer 1

Aquí tienes una pista (bastante larga) para que vayas por el buen camino.

En el mundo del recuento, a veces las cosas con una restricción "existe" son mucho más difíciles de controlar que una restricción "para todos". Por ejemplo, considere la cuestión de:

A. Cuántos pedidos $k$ -tuplas $(a_1,\dots,a_k)$ con $a_i\in\{0,\dots,9\}$ satisfacen la propiedad de que $a_i=9$ para algunos $i$ ? (en otras palabras, existe $1\leq i\leq k$ tal que $a_i=9$ )

esto puede ser bastante difícil de contar ya que tenemos que tener en cuenta muchas cosas como: dónde está el $9$ ¿Cuántos? $9$ ¿hay en la tupla?

Sin embargo, considere un problema similar:

B. Cuántos pedidos $k$ -tuplas $(a_1,\dots,a_k)$ con $a_i\in\{0,\dots,9\}$ satisfacen la propiedad de que ninguno de la $a_i=9$ ? (en otras palabras, para todos $1\leq i\leq k$ tenemos $a_i\neq9$ )

Este es mucho más fácil de contar: esto sólo significa que todos $a_i$ muestra de $\{0,\dots,7,9\}$ y por lo tanto tenemos $9^k$ tal $k$ -tuplas. Sin embargo, ¡obsérvese que esto es lo contrario al problema A! En particular, dado que hay $10^k$ pedido $k$ -tuplas en total, la respuesta al problema A es $10^k-9^k$ .

---

Podemos emplear una estrategia similar para abordar sus problemas. En lugar de intentar contar directamente el $k$ -en los problemas (1) y (2), intente los problemas opuestos:

1') Cuántos $k$ -tuplas $(a_1,\dots,a_k)$ con $a_i\in\{1,\dots,n\}$ satisfacer que $a_s\leq a_t$ para todos $s\leq t$ ?

2') Cuántos $k$ -como las anteriores satisfacen que $a_s-s$ es incluso para todos $s$ ?

El problema (1') consiste en contar el número de secuencias monótonas de longitud $k$ con números entre $1$ et $n$ por lo que se puede intentar resolver este problema de forma recursiva: dejemos que $M(k,n)$ sea la respuesta a (1') para algún $k$ et $n$ Entonces sabemos que

• $M(k,1)=1$ porque la única solución aquí es $(1,1,1,\dots)$
• para calcular $M(k,n+1)$ , dividir los casos en función de lo que el último número es. Por ejemplo, si $a_k=n$ entonces el $(k-1)$ -tupla $(a_1,\dots,a_{k-1})$ es monótona donde cada $a_i\in\{1,\dots,n\}$ (para garantizar que $a_i\leq a_k$ ), por lo que hay $M(k-1,n)$ tales tuplas. En general, si $a_k=L$ entonces habrá $M(k-1,L)$ formas de elegir $a_1,\dots,a_{k-1}$ monótono y encajando $\{1,2,\dots,L\}$ y por lo tanto obtenemos la recurrencia $$ M(k,n+1) = \sum_{L=1}^{n+1}M(k-1,L) $$ Te dejo que encuentres una forma cerrada de esto (siéntete libre de elegir cualquier forma alternativa de enfocar este problema también; esto es sólo un posible enfoque).

En cuanto al problema (2'), observe que cuando $s$ es par, entonces $a_s-s$ es par si $a_s$ es par; si $s$ es impar, entonces $a_s-s$ es par si $a_s$ es impar. Por lo tanto, usted está tratando de contar el número de $k$ -tuplas $(a_1,\dots,a_k)$ donde $a_{2i}\in\{2,4,6,\dots\}$ et $a_{2i-1}\in\{1,3,5,\dots\}$ son todos como máximo $n$ .

Una vez que tengas una respuesta para (1') y (2'), puedes concluir con las respuestas para (1) y (2) observando que hay $n^k$ total $k$ -tuplas $(a_1,\dots,a_k)$ donde $a_i\in\{1,\dots,n\}$ para todos $i$ .