Problem 1312

To solve this problem, we need to count the number of permutations of the set $\{1, 2, \ldots, n\}$ such that for any $1 \leq i, j \leq k$ and any positive integer $m$, we have $f^m(i) \neq j$. This means that the first $k$ elements must be in separate cycles in the permutation.

1. Understanding the Problem:
- We are given a set $\{1, 2, \ldots, n\}$.
- We need to count permutations where the first $k$ elements are in separate cycles.
- This means that for any $1 \leq i, j \leq k$ and $i \neq j$, $f^m(i) \neq j$ for any positive integer $m$.

2. Permutations and Cycles:
- A permutation can be represented as a product of disjoint cycles.
- For the first $k$ elements to be in separate cycles, each of these elements must be in a cycle of length 1 (i.e., a fixed point) or in a cycle that does not include any other of the first $k$ elements.

3. Counting the Permutations:
- We need to count the number of ways to arrange the first $k$ elements such that they are in separate cycles.
- The remaining $n-k$ elements can be arranged in any way.

4. Deriving the Formula:
- The number of ways to arrange the first $k$ elements such that they are in separate cycles is given by the number of derangements of $k$ elements, denoted by $D_k$.
- A derangement is a permutation where no element appears in its original position.
- The number of derangements of $k$ elements is given by:
$$D_k = k! \sum_{i=0}^{k} \frac{(-1)^i}{i!}$$
- The remaining $n-k$ elements can be arranged in $(n-k)!$ ways.

5. Combining the Results:
- The total number of permutations is the product of the number of derangements of the first $k$ elements and the number of permutations of the remaining $n-k$ elements:
$$\text{Total permutations} = D_k \cdot (n-k)!$$

The final answer is $\boxed{D_k \cdot (n-k)!}$.