Find the generating function of a sequence $a_n$

Question

Let $a_n$ be the number of mappings $f : [n] \rightarrow [n]$ such that if $f$ takes on a value $i$,then it takes on all the values $j: 1\le j\le i$. Find a closed form(i.e. a form that can be evaluated in a finite number of operations) of the generating function of $a_n$.

For a mapping that satisfies the above condition, its image $f([n])$ must be one of ${[1],[2],\dots,[n]}$.
#surjections from $[n]$ to $[k]$ = $k!S(n,k)$, where $S(n,k)$ stands for Stirling number of the second kind. Thus the generating function $$A(x)=\sum_{n=0}^{\infty}x^n\sum_{k=1}^n k!S(n,k)=\sum_{k=0}^\infty k! \sum_{n=k}^\infty x^n S(n,k)$$ And we already know the generating function of S(n,k) has a closed form: $$\sum_{n=k}^\infty x^n S(n,k)=\frac{x^k}{(1-x)(1-2x)\dots(1-kx)}$$ But how do I obtain a closed form of the generating function of $a_n$ using the above equations?

Answer 1

Proceeding along your line.....

The # required mappings f that takes n =n!.
The # required mappings f that doesn't take n at all=(n-1) $a_{n-1} $.
(Reason:
Now for no i in [n], f(i)=n. So f(n) has to take one of the values in the set [n-1]. Now each mapping $[n-1] \rightarrow [n-1]$ can be extended to [n] by giving a value for f(n) in [n-1]. Thus given a map [n-1] $\rightarrow$ [n-1] satisfying the given conditions, it can be extended to [n] in n-1 ways. And #mappings f:[n-1]$\rightarrow$ [n-1] satisfying the given conditions = $a_{n-1} $.
So #mappings f that doesn't take n at all= (n-1)$a_{n-1} $.) Hope it helps!?

Answer 2

You can construct the recurrence relation this way...

Let $g(a, b)$ be the number of surjective $[a]\mapsto [b]$ functions (that is, they takes on the values $1, 2, ..., b$). So, $a_n = \sum_{i=1}^n g(n,i)$.

Base case (those ones are easy to prove): $$g(n,n) = n!$$ $$g(n,0) = 0$$ (for $n > 0$)

Recurrence relation: $$g(n,k)= k\times(g(n-1,k)+g(n-1,k-1))$$ (for $n > k$)

From that recurrence relation hopefully you can construct closed-form for generating function of $a_n$ series.

---

Proof for recurrence relation:

Consider $f:[n]\mapsto[k]$. There are 2 cases:

• $f(1),f(2),...,f(n-1)$ takes $k$ values. There are $g(n-1,k)$ ways for choosing $n-1$ first values of $f$, and $k$ ways to choose value of $f(n)$.
• $f(1),f(2),...,f(n-1)$ takes $k-1$ values. Therefore, $f(n) \notin \{f(1),...,f(n-1)\}$. There are $k$ ways to choose value of $f(n)$, and for each way of choosing $f(n)$ there are $g(n-1,k-1)$ ways to construct $\{f(1),...,f(n-1)\}$, because $f':x\mapsto f(x)$ where $x \in [n-1]$ has image $[k] \setminus f(n) $, and there is a 1-to-1 mapping between surjective $[n-1]\mapsto [k] \setminus f(n)$ functions and surjective $[n-1] \mapsto [k-1]$ functions.