Combinations under constraint

Arrangements, combinations and permutations, probability, ...
Post Reply
Posts: 28
Joined: Sat Feb 23, 2013 6:12 am

Re: Combinations under constraint

Post by Bubbler »

Do you mean, sum(E(k)) is divisible by max(E(k)), not max(S(n))?
If so, one property of the sequence F(n) will be that
dF(n) = F(n) - F(n-1) = # of subsets of S(n-1) whose sum is divisible by n, including the empty set.
Each dF(n) can be calculated using DP, having array size of n(n-1)/2 = O(n^2) and iteration cost of O(n).
I don't think there is an easy formula for either F(n) or dF(n), but someone can evaluate and post these values so we can see if they have any patterns.
I can't because I'm too busy nowadays due to 3 programming projects in 3 different CS courses(!) and my brain is so stuffed with C, Java and ML that I almost forgot how to use Python (I always use it for PE-related tasks) :shock:
Post Reply