- #1

derpetermann

- 1

- 0

The more general definition of the problem is this:

What is the probability of finding a k-subset in a d-dimensional random binary array of length n, such that this subset has at least s_1 ones in dimension 1, s_2 ones in dimension 2, ..., s_d ones in dimension d. The total number of ones per dimension (ts_1 to ts_d) are fixed.

Is there a name to this problem? I tried to google, but I really did not know what to look for, since the problem definition is quite unwieldy to begin with.

Is the problem tractable analytically? If yes does the solution scale to larger d, k and n when solved algorithmically?

Your help is highly appreciated! Thanks a lot in advance!