Skip to main content
Incorporated some comments and an example.
Source Link
Douglas Zare
  • 28k
  • 6
  • 90
  • 130

The question seems like it should be known. However, but I was not able to find it anywhere. 

How many binary strings of length n$n$ are required. So so that for every k$k$ positions in these strings, all $2^k$ possible sequencessubsequences occur?

For example, suppose $n=3$, and $k=2$. We want a set of binary strings of length $3$ so that if you look at the first and third symbols (or first two, or last two), you will see all $4$ patterns $00$, $01$, $10$, and $11$. For example, the strings with an even number of $1$s $\{ 000, 011, 110, 101\}$ induce all subsequences on each set of two positions.

Let $f(n,k)$ be the minimum number. Trivially, $f(n,k) \ge 2^k$ so $f(3,2)=4$.

I am interested in precise upper and lower bounds for $f(n,k)$. Bounds whichthat are within a constant of each other (independent of n$n$ and k$k$) suffice for my purposes.

The question seems like it should be known. However, I was not able to find it anywhere. How many binary strings of length n are required. So that for every k positions in these strings all $2^k$ possible sequences occur? I am interested in precise upper and lower bounds. Bounds which are within a constant of each other (independent of n and k) suffice for my purposes.

The question seems like it should be known, but I was not able to find it anywhere. 

How many binary strings of length $n$ are required so that for every $k$ positions in these strings, all $2^k$ possible subsequences occur?

For example, suppose $n=3$, and $k=2$. We want a set of binary strings of length $3$ so that if you look at the first and third symbols (or first two, or last two), you will see all $4$ patterns $00$, $01$, $10$, and $11$. For example, the strings with an even number of $1$s $\{ 000, 011, 110, 101\}$ induce all subsequences on each set of two positions.

Let $f(n,k)$ be the minimum number. Trivially, $f(n,k) \ge 2^k$ so $f(3,2)=4$.

I am interested in precise upper and lower bounds for $f(n,k)$. Bounds that are within a constant of each other (independent of $n$ and $k$) suffice for my purposes.

Source Link
Anahita
  • 363
  • 1
  • 8

Repeats of all binary strings of length k

The question seems like it should be known. However, I was not able to find it anywhere. How many binary strings of length n are required. So that for every k positions in these strings all $2^k$ possible sequences occur? I am interested in precise upper and lower bounds. Bounds which are within a constant of each other (independent of n and k) suffice for my purposes.