Solution of Buckets

Because two subsequences will be in the same bucket if they have the same elements, their position does not really matter.

Let's fix a some arbitrary frequencies for all the elements in our initial array.

Let this array be a
a[i]= the arbitrary frequency of the number i
Let's also denote:
freq[i] = the total frequency of the number i in the whole array
Note that a[i] ≤ freq[i] for each i

The size of the bucket containing all these subsequences with be:

Now we only need a way to compute the sum of products of all possible a. We can compute the product of a sum which will give us every single possbile combination. This product is the following:

In the end, because we want the size of each bucket to be squared, and remove the empty set, we need to compute the following formula:

Questions?

Sponsors Gold