Let n and d be integers and $A_{d,n}$ be the set of all pairs (f,r) of functions $f:[d] \to [n]$ and $r:[d]\to [d]$ satisfying
f is weakly increasing
$r(i) \leq i$ for all $i \in [d] $
if $f(i)=f(j)$ for some $i<j$ then $r(i)<r(j)$.
Prove that $|{A_{d,n}}|=n^d$
The only idea I’ve had so far seems straightforward: to find a bijection between $A_{d,n}$ and the set of all functions $g:[d]\to [n]$ (let’s call that set $G$. I tried to show that every function in G could be written as $g(i)=f(r(i))$ but I’m having a hard time doing so, and especially that it is unique. Any ideas? Is there maybe another way to do it?