3
$\begingroup$

What is the number of ways to chose a set $A =\{a_1 , \ldots ,a_k \}$ from $ N = \{1, \ldots, n\}$, s.t. $N-A$ consists of exactly $m$ maximal intervals, where an interval is defined as a subset of N consisting of consecutive numbers.

For example choosing $\{3,4,7\}$ from $\{1,2,3,4,5,6,7,8\}$ would result in the $3$ maximal intervals, $\{1,2\}$, $\{5,6\}$ and $\{8\}$

2 Answers 2

1

Let's extend $N$ to $N_2 = \{0,1,2,3,\ldots,n,n+1\}$ with $n+2$ elements. We chose $k+2$ elements of this for $A_2$, always including $0$ and $n+1$, so $N_2-A_2$ has $m$ non-empty runs and so $A_2$ has $m+1$ non-empty runs.

In effect we have decomposed $N_2$ into $2m+1$ parts of non-empty runs. The way of calculating this is well known and gives ${n+1 \choose 2m}$ as a result for your question.

If $k$ is fixed then it becomes very slightly more complicated: you have to decompose the $k+2$ elements of $A_2$ into $m+1$ non-empty parts and the $n-k$ elements of $N_2-A_2$ into $m$ parts, so the answer is ${k+1 \choose m}{n-k-1 \choose m-1}.$

0

Suppose $A$ has size $k$. For example, suppose $n=10$, $m=5$ and $k=4$. Then, a choice of $A$ is the same as diving up $\{1,2,\ldots,10\}$ into runs of 0s and 1s, with $k=4$ ones and no two ones adjacent. So, for instance, 0010101010.

The the $m$ intervals will contain a total of $n-k$ elements (the $0$s). The ways of choosing the lengths of the runs of $0$s correspond to compositions of $n-k$ into $m$ parts. There are $\binom{n-k-1}{m-1}$ ways to do that.

Similarly, there are $k$ $1$s, divided into $m-1$ runs, which is compositions of $k$ into $m-1$ parts, so $\binom{k-1}{m-2}$.

Once you have a composition for the $0$s and a composition for the $1$s, the set $A$ is totally determined (interleave the runs of $0$s and $1s$). So, summing over $k$ gives $\sum_{k=0}^n \binom{n-k-1}{m-1}\binom{k-1}{m-2}$

  • 0
    Argh... I thought I had. But I think you're right and I missed it.2012-02-23