Lower bound on number of permutations of a set, where some transpositions are fixed My question is as follows:

Let $N(n) = N = \{1, 2, ...,n\}$, and let ${\rm Aut}(N)$ denote the automorphism group over $N$, so $|{\rm Aut}(N)| = N!$ (in this case this is just the group of permutations over $N$).
Then suppose we had two sequences of numbers, $\{x_i\}_{i=1}^m, \{y_i\}_{i=1}^m \subset N$ with $m \leq n$, and we wanted the collection of functions $f \in{\rm Aut}(N)$ such that $f(x_i) = y_i$ for $i=1,...m$.  Call the set of functions satisfying this restriction $A \subset {\rm Aut}(N)$.
Then what is the lower bound on the magnitude of $A$, given $m$?

I want to say it is $(n-m)!$ but I am unsure it is right.  My thinking is that once you fix $f(x) = y$, you than prune away the set of functions that do not map $x$ to $y$, and hence the remaining set of functions are those that satisfy the restriction, but also permute the elements $N \setminus x$.  Then you can get an induction to get $(n-m)!$ as the magnitude of $A$, but I may be wrong.
 A: The set of permutations of $\{1, \dots, n\}$ that fix $\{1, \dots, m\}$ for $0 \leq m \leq n$ is in bijective correspondence with the set of permutations of $\{m+1, \dots, n\}$. Hence, the number of such permutations is indeed $(n-m)!$, as you suggested.
This can easily be modified to work for subsets $\{x_1, \dots, x_m\}$ and $\{y_1, \dots, y_m\}$ of size $m$, i.e. the $\{x_i\}$ are distinct and the $\{y_i\}$ as well. How?

 Let $\sigma: N \to N$ satisfy $\sigma(i) = x_i$ for $1 \leq i \leq m$ and extend its definition to all of $N$ by filling in the remaining elements of $N$ in increasing order, i.e. let $\sigma(m+1)$ be the least $j$ such that $j \not\in \{x_1, \dots x_m\}$, etc. In a completely analogous fashion, define another permutation $\tau: N \to N$ such that $\tau(i) = y_i$ for all $0 \leq i \leq m$.
Now, the map $\rho \mapsto \tau \rho \sigma^{-1} =: \rho'$ is a bijection, sending a permutation $\rho:N \to N$ that fixes $\{1, \dots, m\}$ to a different permutation $\rho'$ that satisfies $\rho'(x_i) = y_i$.

Now, if there are some collisions, say
$$
\bigl\lvert \{x_1, \dots, x_m\} \bigr\rvert = 
\bigl\lvert \{y_1, \dots, y_m\} \bigr\rvert = k,
$$
where $0 \leq k \leq m$, then the number of permutations that satisfy $f(x_i) = y_i$ for $0 \leq i \leq n$ is $(n-k)! \geq (n-m)!$, hence the previous count is a lower bound.
