Solución para el número de $n$ -secuencias de pares de elementos de a $p$ -con exactamente $k$ coincidencias último-primero

Question

Sea $n, p, k \in \mathbb{N}$ tal que $n > 1$ , $n \geq p$ y $1 \leq k < n$ . Sea $P$ sea un conjunto de $p$ elementos. Consideremos secuencias de la forma $$(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$$

donde:

1. Cada $(x_i, y_i) \in P^2$ y
2. Hay exactamente $k$ único $i, j$ tal que $i < j$ y $y_i = x_j$ .

Por ejemplo, si $k = 2$ y $P = {a, b, c, d}$ entonces lo siguiente estaría bien:

$$(a, b), (b, a), (a, d), (c, c)$$

Pero lo siguiente no lo sería:

$$(a, b), (b, a), (a, b), (b, a)$$

¿Existe una solución de forma cerrada (o, de hecho, cualquier solución) en términos de $n, p, k$ que da el número de secuencias como las descritas?

Answer 1

Creo que lo he descubierto.

Sea $m={n\choose 2}$ . El número de secuencias posibles es $$p^3(p-1)^{m-k} {m\choose k}$$ para $k \leq m$ .

Si $k > m$ no hay secuencias.