4
$\begingroup$

I hope I'm not asking a question that has previously been asked (and answered).

I have to determine how many subsets of $[n]:=\{1,\dots,n\}$ of size $k$ contain exactly one couple $(i,i+1)$ of subsequent integers. I have used the following approach: let $T=(t_1,\dots,t_n)\subset\{0,1\}^n$ be a binary string of length $n$, identifying a subset of size $k$ drawn from $[n]$, i.e. $\sum_i t_i=k$. For $T$ to meet the conditions stated above, it must be the case that $T$ contains $k-2$ non consecutive ones and a couple of consecutive ones.

To build such sequence, I used the method of stars and bars: first find a sequence of length $k-1$ with no consecutive numbers and then obtain a sequence of length $k$ with one consecutive couple.

  1. Place $n-k$ consecutive zeros in a string.
  2. There are $n-k+1$ places where $k-1$ ones can be placed so that they are non consecutive, hence there are $\binom{n-k+1}{k-1}$ sequences of length $n-1$ with $k-1$ ones that are non consecutive.
  3. Add an extra one close to the previous one. For any sequence in $(2.)$ there are $(k-1)$ possibilities.

Overall, that would give $(k-1)\times\binom{n-k+1}{k-1}$ possibilities.

Does this make sense? Thanks!

$\endgroup$
7
  • $\begingroup$ I think it should be $(k-1)\binom{n-k-1}{k-1}$ $\endgroup$
    – Asinomás
    Sep 23, 2016 at 16:01
  • $\begingroup$ It does not work, because when you re-insert back an element, nothing grants that the situation in which you take $3$ consecutive elements is avoided. $\endgroup$ Sep 23, 2016 at 16:14
  • $\begingroup$ @JackD'Aurizio, the $n-k+1$ places for the ones are the places (bars) between two zeros plus at the ends: so the process seems ok and $3$ consecutive elements should not happen, or there is a bug I do not see ? $\endgroup$
    – G Cab
    Sep 23, 2016 at 16:25
  • $\begingroup$ @JackD'Aurizio I see the process as $$00000\quad \Rightarrow \quad \_^{\left( {} \right)} 0^1 0^1 0^{\left( {} \right)} 0^{\left( 1 \right)} 0^{\left( {} \right)} \quad \Rightarrow \quad \_^{\left( {} \right)} 0^1 0^{11} 0^{\left( {} \right)} 0^{\left( 1 \right)} 0^{\left( {} \right)} $$ $\endgroup$
    – G Cab
    Sep 23, 2016 at 16:34
  • 1
    $\begingroup$ Just a terminology fix: it is best to replace close with to the right of one previously placed $1$. Then it is clear that the answer is $(k-1)$ times a binomial coefficient provided by stars and bars. $\endgroup$ Sep 23, 2016 at 16:49

2 Answers 2

2
$\begingroup$

By way of enrichment here is a solution using generating functions. We start by selecting the first value:

$$\frac{z}{1-z}.$$

Then we add in $k-1$ gaps, marking gaps of size one (consecutive values):

$$\left(uz+\frac{z^2}{1-z}\right)^{k-1}.$$

Finally we sum all contributions (subsets) that terminate in at most $n$:

$$[z^n] \frac{1}{1-z} \times \cdot.$$ We get the answer

$$[z^n] [u^1] \frac{z}{1-z} \left(uz+\frac{z^2}{1-z}\right)^{k-1} \frac{1}{1-z}.$$

The coefficient extractor in $u$ ensures that we have exactly one pair of consecutive items. We get

$$[z^n] \frac{z}{1-z} \times z {k-1\choose 1} \left(\frac{z^2}{1-z}\right)^{k-2} \times \frac{1}{1-z}.$$

This is

$$(k-1) [z^n] \frac{z^{1+1+2k-4}}{(1-z)^k} = (k-1) [z^n] \frac{z^{2k-2}}{(1-z)^k} = (k-1) [z^{n-2k+2}] \frac{1}{(1-z)^k} \\ = (k-1) {n-2k+2+k-1\choose k-1} = (k-1) {n-k+1\choose k-1}.$$

$\endgroup$
0
0
$\begingroup$

It may be of interest to consider an additional method for solving this type of problems.

Seq_2_adj

As shown in the sketch, consider a subset $\left\{ {a_{\,1} ,\,a_{\,2} ,\,\; \cdots \,,a_{\,k} = h} \right\}$ with the given requisites, and whose last element equals $h$.
Let's take the backward delta $\left[ {a_{\,1} - 0,\,a_{\,2} - a_{\,1} ,\,\; \cdots \,,a_{\,k} - a_{\,k - 1} } \right]$ which will have all positive elements, of which (apart eventually the 1st element) only one will have value $=1$ and the others shall be greater than that, alltogether summing to $h$.
Let's eliminate the element with Delta $=1$, we are left with $k-1$ element, the 1st with min. value $1$ and the remaining with min. value $2$.
Let's deduct such a minimum threshold, and we arrive to get a weak composition of $h-2k$ into $k-1$ parts, with $4 \leqslant 2k \leqslant h$. Their total number is known to be $$ \left( \begin{gathered} \left( {h - 2k} \right) + \left( {k - 1} \right) - 1 \\ \left( {k - 1} \right) - 1 \\ \end{gathered} \right) = \left( \begin{gathered} h - k - 2 \\ k - 2 \\ \end{gathered} \right)\quad \left| \begin{gathered} \,2 \leqslant k \hfill \\ \;2k \leqslant h \hfill \\ \end{gathered} \right. $$ Multiplying by the number of possible positions of the eliminated element, and summing over $h$ we get $$ \begin{gathered} \left( {k - 1} \right)\sum\limits_{2k\, \leqslant \,h\, \leqslant \,n} {\left( \begin{gathered} h - k - 2 \\ k - 2 \\ \end{gathered} \right)} = \left( {k - 1} \right)\left( {\left( \begin{gathered} n + 1 - k - 2 \\ k - 1 \\ \end{gathered} \right) - \left( \begin{gathered} 2k - k - 2 \\ k - 1 \\ \end{gathered} \right)} \right) = \hfill \\ = \left( {k - 1} \right)\left( {\left( \begin{gathered} n - k - 1 \\ k - 1 \\ \end{gathered} \right) - \left( \begin{gathered} k - 2 \\ k - 1 \\ \end{gathered} \right)} \right)\quad \left| \begin{gathered} \,2 \leqslant k \hfill \\ \;2k \leqslant n \hfill \\ \end{gathered} \right. = \left( {k - 1} \right)\left( \begin{gathered} n - k - 1 \\ k - 1 \\ \end{gathered} \right) \hfill \\ \end{gathered} $$

$\endgroup$

You must log in to answer this question.

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