**Motivation.** (Please skip if you are not in the mood for "chitchat".) Last night I listening to a classical radio station, and for the umpteenth time, they played Mendelssohn's [Psalm 42](https://en.wikipedia.org/wiki/Psalm_42_(Mendelssohn)), a composition that I like very much. Luckily, a week ago, when they played it, it was followed by a different piece (Rodeo by Copland) than yesterday (Bach d-minor piano concerto). I wondered how long they can proceed so that piece $X$ is never immediately followed by piece $Y$ two separate times. Which led to the following little problem.


**Formalization.** We regard any positive integer $n$ as the set of its predecessors, so $n = \{0,\ldots,n-1\}$. For positive integers $m, n\in \mathbb{N}$ we say that a map $f : m\to n$ is a *radio-playing* function if whenever $a,b \in m-1$ with $a\ne b$ and $f(a) = f(b)$, then $f(a+1) \neq f(b+1)$.


Using the pigeonhole principle, it is easy to see that if $m > n^2$ there cannot be a radio-playing function $f : m\to n$. So, given $n\in \mathbb{N}\setminus \{0\}$, let $A\_n$ be the largest integer such that there is a radio-playing function $f: A\_n \to n$.


What is the value of $A\_n$ in terms of $n$?



Radio-playing sequence
I think you're just asking for a de Bruijn sequence of order $2$ on $n$ symbols, in which case the answer is $n^2$ because the non-simple digraph on $n$ vertices where $u \to v$ for every $u, v$ (including $u=v$) and the edges $u \to v$ and $v \to u$ are considered distinct unless $u=v$ is Eulerian.


