A question regarding the construction of binary sequences

74 Views Asked by At

Suppose we want to find all binary sequences with a length $K$ that contain $N$ ones. We know that the number of such sequences is $P = K$ choose $N$.

As an example, for $K=4,N=2$ we get the following sequences:

$$1100$$

$$1010$$

$$1001$$

$$0110$$

$$0101$$

$$0011$$

Now suppose that we define a function $f(k,p)$ where $k = 1,2,...,K$ and $p = 1,2,...,P$. The values of this function are $0$ and $1$. As an example for the sequences above: $f(1,1) = 0, f(4,1) = 1$ etc.

My question is whether there's a closed form for the function $f(k,p)$ or not. By closed form I mean an expression, complicated as it may be, which immediately gives all binary entries for each $k$ and $p$.

Edit 1 (19/09/2023): I came across another useful thread in which a recursive formula was given to the decimal representation of the binary sequences:

Equation for generating integers for n-bit binary strings with k bits set to 1

I understand that it is possible, in principle, to convert any recursion into iteration (Church-Turing theorem), however the recursive function given in that thread can branch into various sub-domains. How does one convert such a function into something iterative?