Four, (50 points) Given a positive integer $n \geqslant 3$, label each side and each diagonal of a regular $n$-gon with a positive integer not exceeding $r$, such that: (1) Each positive integer $1,2,3, \cdots, r$ appears among the numbers labeled on the sides or diagonals; (2) In each $\triangle P_{i} P_{j} P_{k}$, two of the sides are labeled with the same number, and this number is greater than the number on the third side. Find:
(1) The maximum positive integer $r$ that satisfies the above conditions;
(2) For the maximum positive integer $r$, find the number of different labeling methods that satisfy the problem.
Let's translate the provided text into English, maintaining the original formatting and structure:

---

Let the labeling that satisfies condition (2) be called "good", and the labeling that satisfies both conditions (2) and (1) be called "very good". We will refer to the diagonals and sides of the polygon collectively as edges, and the numbers marked on the edges as the distances between the corresponding two vertices.

Suppose $AB$ is the edge labeled with the maximum value $r$, and $C$ is a vertex different from $A$ and $B$. By condition (2), one of $AC$ and $BC$ is labeled with $r$, and the other is labeled with a number less than $r$. Therefore, we can divide all the vertices into two groups: the first group includes the vertices that are at a distance $r$ from point $A$ (point $B$ is in this group), and the second group includes the vertices that are at a distance $r$ from point $B$ (point $A$ is in this group).

Let $X$ be any vertex in the first group different from point $B$, and $Y$ be any vertex in the second group different from point $A$. In $\triangle AXY$, since $AY$ is not labeled with $r$ and $AX$ is labeled with $r$, $XY$ must be labeled with $r$. Therefore, the number marked on the line connecting any vertex in the first group to any vertex in the second group is $r$.

For any two vertices $X$ and $Y$ in the first group, in $\triangle AXY$, since $AX$ and $AY$ are both labeled with $r$, $XY$ must be labeled with a number less than $r$. Similarly, the number marked on the edge connecting any two vertices in the second group is also less than $r$.

A good labeling should satisfy: the number marked on the edge connecting any vertex in the first group to any vertex in the second group is the maximum value $r$, and the labeling within each group is good, with all numbers marked on the edges being less than $r$.

(1) Use mathematical induction to prove that the maximum value of $r$ is $n-1$.
When $n=3$, it is easy to see that $r=2$ is the maximum value, so the conclusion holds.
Assume the conclusion holds for $n=3, 4, \cdots, n-1$ (where $n>3$), and we will prove that it also holds for $n$.
For an $n$-sided polygon $P$, divide the vertices into two groups, with the first group containing $k$ vertices and the second group containing $n-k$ vertices. By the induction hypothesis, the $k$ vertices in the first group form a $k$-sided polygon $P_1$ with at most $k-1$ different numbers (not necessarily from 1 to $k-1$); similarly, the $n-k$ vertices in the second group form an $(n-k)$-sided polygon $P_2$ with at most $n-k-1$ different numbers. The edges connecting vertices in the first group to vertices in the second group are all labeled with the maximum number, so there are at most $(k-1) + (n-k-1) + 1 = n-1$ different numbers. Therefore, by mathematical induction, $r_{\max} = n-1$.

The above proof actually provides a recursive construction: if an $(n-1)$-sided polygon has a very good labeling with $r_{\max} = n-2$, and the $n$-th vertex of the $n$-sided polygon is connected to each vertex of the $(n-1)$-sided polygon with edges labeled $n-1$, then a very good labeling that satisfies the conditions is obtained.

(2) Let $f(n)$ be the number of very good labelings of an $n$-sided polygon $P$ using the numbers $1, 2, \cdots, n-1$ on each edge. We will use mathematical induction to prove that $f(n) = \frac{n!(n-1)!}{2^{n-1}}$. When $n=3$, $r=2$, and $f(3) = C_3^1 = 3$.
Assume that for $k=3, 4, \cdots, n-1$ (where $n>3$), $f(k) = \frac{k!(k-1)!}{2^{k-1}}$ holds.
For an $n$-sided polygon $P$, divide the $n$ vertices into two non-empty groups, with the first group containing $k$ vertices, and there are $C_n^k$ ways to do this. Each vertex in the first group must be connected to each vertex in the second group with edges labeled $n-1$, and we need to choose $k-1$ numbers from $1, 2, \cdots, n-2$ to label the edges of the $k$-sided polygon $P_1$ formed by the vertices in the first group, which can be done in $C_{n-2}^{k-1}$ ways. The remaining $n-1-k$ numbers are used to label the edges of the $(n-k)$-sided polygon $P_2$ formed by the vertices in the second group, and $P_1$ has $f(k)$ very good labelings, and $P_2$ has $f(n-k)$ very good labelings.

Since choosing $k$ vertices as the first group is equivalent to choosing the remaining $n-k$ vertices as the first group, each very good labeling is counted twice, so
$$
f(n) = \frac{1}{2} \sum_{k=1}^{n-1} C_n^k C_{n-2}^{k-1} f(k) f(n-k) = \frac{1}{2} \sum_{k=1}^{n-1} \frac{n!}{k!(n-k)!} \cdot \frac{(n-2)!}{(k-1)!(n-k-1)!} f(k) f(n-k)
$$
$$
\begin{array}{l}
\quad = \frac{n!(n-1)!}{2(n-1)} \sum_{k=1}^{n-1} \frac{f(k)}{k!(n-k)!} \cdot \frac{f(n-k)}{(k-1)!(n-k-1)!} = \frac{n!(n-1)!}{2(n-1)} \sum_{k=1}^{n-1} \frac{1}{2^{k-1}} \cdot \frac{1}{2^{n-k-1}} = \\
\frac{n!(n-1)!}{2^{n-1}}.
\end{array}
$$

In conclusion, by mathematical induction, the number of different labeling methods that satisfy the maximum number $r = n-1$ is $f(n) = \frac{n!(n-1)!}{2^{n-1}}$.

---