# Find the generating function of a sequence $a_n$

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?

• A mapping doesn't necessarily have to be bijective, even if it accepts a full domain.
– orlp
Commented Oct 3, 2017 at 7:16
• @orlp But it requires f takes all values between 1 and n. How can it not be bijective? Commented Oct 3, 2017 at 7:18
• $f(n) = 1$ can take any value and maps everything to $1$.
– orlp
Commented Oct 3, 2017 at 7:20
• @orlp A small question (somewhat unrelated): $[n]$ denotes the set of positive integers from $1$ to $n$ (that is, $\{1, 2, ..., n\}$?) Commented Oct 3, 2017 at 7:21
• @user202729 In this context, yes.
– orlp
Commented Oct 3, 2017 at 7:26

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!?

• But not vice versa, e.g., a mapping $[n] \mapsto [n-1]$ cannot be converted to a map $[n-1] \mapsto [n-1]$ such that it takes on all the values in range $[n-1]$. For example, $\{1, 2, 3, 3, 4\}$ is a onto $[5]\mapsto [4]$ function, but $\{1,2,3,3\}$ is not a onto $[4]\mapsto [4]$ function. Commented Oct 3, 2017 at 8:12
• Am sorry I don't understand. Why should the "vice versa" part matter here? Commented Oct 3, 2017 at 8:16
• That is, you've only proven number of onto $[n]\mapsto[n-1]$ functions is $\geq$ number of onto $[n-1]\mapsto[n-1]$ functions multiply with $n-1$, not necessarily $=$. Commented Oct 3, 2017 at 8:18
• I think $a_{n-1}$ is not the number of onto maps from [n-1] to [n-1] but the number of maps satisfies the given conditions in op' s question which doesn't include onto conditions. Also I have not tried to find the number of onto maps from [n] to [n-1]. I think question doesn't required to find onto maps Commented Oct 3, 2017 at 8:27

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.