Solution for the number of $n$-length sequences of pairs of elements from a $p$-element set with exactly $k$ last-first matches

Question

Let $n, p, k \in \mathbb{N}$ such that $n > 1$, $n \geq p$ and $1 \leq k < n$. Let $P$ be a set of $p$ elements. Consider sequences of the form $$(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$$

where:

1. Each $(x_i, y_i) \in P^2$; and
2. There are exactly $k$ unique $i, j$ such that $i < j$ and $y_i = x_j$.

For example, if $k = 2$ and $P = {a, b, c, d}$, then the following would be OK:

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

But the following would not be:

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

Is there a closed-form (or indeed, any) solution in terms of $n, p, k$ which gives the number of sequences like the ones described?

Answer 1

I believe I figured it out.

Let $m={n\choose 2}$. The number of possible sequences is $$p^3(p-1)^{m-k} {m\choose k}$$ for $k \leq m$.

If $k > m$ there are no sequences.