2
$\begingroup$

This is a combinatorial problem encountered in calculating the relative occurrence of certain outputs produced by an algorithm based loosely on genetics, in order to predict the probability that a certain outcome will take place.

We are faced with an ordered set S of N sets of 4 arbitrarily chosen bits. Example for N = 2: S = {{1,1,1,0}, {1,0,0,0}}

We wish to determine the number of ways K to produce a binary number containing exactly n 1-bits by selecting one bit from each set, where the ith bit is taken from the ith set. Example for N = 2: Given S = {{1,1,1,0}, {1,0,0,0}}, there are ten ways to form a binary number containing exactly one 1-bit: 10 has nine possibilities, and 01 has one possibility.

The general problem can be solved by brute force, simply iterating over all possibilities and counting them. However, we would like to perform these calculations for reasonably large numbers N and n, and would therefore like to find a general solution that is not computationally heavy, if it exists.

It stands to reason that a solution, if it exists, should depend on N and n, as well as the numbers $k_j$ of sets in S with j 1-bits ($j = 0,...,4$). My gut tells me that K probably follows some nice distribution (binomial, perhaps) between the extremes (i.e. selecting only ones from sets of all ones, or selecting only zeros sets of only zeros).

If there is no general solution, then an approximative method would also be of interest.

Edit: A more intuitive way to describe the problem would be this:

Suppose you have N bags, each of which contains 4 tiles with a letter on it. You are tasked with building words of length N by taking one tile from each bag. Moreover

  • The only letters that may exist in the bags are A and B.
  • You must build a word that contains exactly n instances of the letter A.
  • You must always pick letters from the bags in the same order (the bags are numbered).
  • The number of As and Bs in each bag is arbitrary, but known.

How many such words can you form?

$\endgroup$
8
  • $\begingroup$ So, the only thing that matters about the sets in $S$ is how many $1's$ are in each of them. And then you have to separately count the cases given the selection of sets from which you draw the $1's$. Any reason to expect a useful formula? $\endgroup$
    – lulu
    Commented Jun 16, 2021 at 13:04
  • $\begingroup$ Correct! I am not sure if there is a useful formula, but I am hoping there is. There are a lot of symmetries to the problem so it seems like it might reduce to a nice formula if you take everything into account, but I could not find it. $\endgroup$
    – plkav
    Commented Jun 16, 2021 at 13:09
  • $\begingroup$ I don't see any useful symmetries. It's even hard to count the ways to choose $n$ viable sets from $S$ (to get the $1's$ from). $\endgroup$
    – lulu
    Commented Jun 16, 2021 at 13:11
  • $\begingroup$ K should be invariant under permutations of the order of the sets, that's one symmetry at least. The binomial coefficient gives us the number of ways to pick n from N, but some of those selections will be unviable (like you mentioned). However, after choosing sets to take a 1 from, the number of ways to do it is given by multiplying the number of 1s in the selected sets with the number of 0s in the unselected sets. If you selected a set without any ones, then that multiplication yields zero. But this is only useful if you do the brute force iterative summation. $\endgroup$
    – plkav
    Commented Jun 16, 2021 at 13:18
  • 1
    $\begingroup$ If $N$ is reasonably small (like $\le 10^5$) this is a straightforward dynamic programming exercise following @lulu's recursion: $O(N^2)$ time and $O(N)$ memory. For large $N$ you can use the fact that this is essentially the sum of $3$ binomially distributed variables (it's trivial to compute the effect of sets with $j=0$ and $j=4$). Any large value of $k_j$ could reasonably be approximated by a normal distribution (except at the tails I guess). $\endgroup$
    – Erick Wong
    Commented Jun 17, 2021 at 0:21

1 Answer 1

Reset to default
1
$\begingroup$

Basically you answer is

$$ [x^n]\prod_{i=0}^4(4-i+ix)^{k_i} $$

If we take

$$ F_i=(4-i+ix)^{k_i} $$

then you are calculating the $n$-th coefficient of the convolution of these five polynomials ($F_0,\dots,F_4$). You can compute the answer for $n\in[0,t]$ all at once with a time complexity of $O(t\log t)$ with FFT algorithm. I'm not sure if this satisfies your requirement, but it's the best one I can come up with.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .