2
$\begingroup$

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?

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

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – user202729 Oct 3 '17 at 8:12
  • $\begingroup$ Am sorry I don't understand. Why should the "vice versa" part matter here? $\endgroup$ – shwetha Oct 3 '17 at 8:16
  • $\begingroup$ 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 $=$. $\endgroup$ – user202729 Oct 3 '17 at 8:18
  • $\begingroup$ 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 $\endgroup$ – shwetha Oct 3 '17 at 8:27
1
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.