Recently, I have participated in school contest and I got this problem:

The problem is to generalize a formula for the probability P in terms of weights $$$w$$$ and sums $$$S$$$ for a given $$$n$$$, where $$$S=\sum_{j=1}^{n} w_j$$$

The probability formula involves choosing a permutation of the set $$$[2, n]$$$, which means the number of terms grows rapidly with $$$n$$$. Let's try to understand the general pattern by analyzing the cases for $$$n=3$$$ and $$$n=4$$$

$$$\textbf Case \ n = 3$$$

Given: $$$S = w_1 + w_2 + w_3$$$

For $$$n=3$$$, the formula for $$$P$$$ is:

We can factor the expression:

This represents the weighted sum of two terms where the denominators correspond to the differences between $$$S$$$ and individual terms $$$w_2$$$ and $$$w_3$$$

$$$\textbf Case \ n = 4$$$

Now, let's analyze the case for $$$n=4$$$, where the formula involves more permutations:

The expanded form looks like:

Group similar terms by factoring:

$$$\textbf Generalizing\ to\ n$$$

For any $$$n$$$, the general form of the probability formula is:

The pattern is that for each permutation of $$${2, 3, ..., n}$$$ , the numerator is the product of all $$$w_i$$$'s and the denominator involves nested sums subtracting successive terms of the permutation from $$$S$$$

$$$\textbf Recursive\ Structure$$$

The denominator has a recursive structure:

However, I don't really know how to compute $$$P$$$ with the given constraints like this

$$$1 \leq n \leq 5000$$$

$$$w_i > 0$$$ and $$$1 \leq \sum^{n}_{i=1} w_i <= 10^5$$$