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$$$