1
$\begingroup$

I have the follow two questions :

How many sequences $a_1,a_2,...,a_n$ in length $k$ so $a_i \in \{1,2,3,4....,n\}$ satisfy :

1) $a_1<a_2<....<a_k$ while $(a_{i+1} \neq a_i+1)$

2) $a_1 \leq a_2 \leq .... \leq a_k$ while $(a_{i+1} \neq a_i+1)$

I did some thinking about these questions, if I understood it correctly $a_1,...a_n$ are numbers therefore the question is to choose $k$ numbers without sequential numbers yet find it hard to solve, I thought of maybe using inclusion exclusion principle since I don't find a way to count this.

Any ideas? Thanks.

$\endgroup$
  • 1
    $\begingroup$ Relate this problem involving $0<a_1<a_2<\dots<a_k<n+1$ to the sequence $b_1=(a_1-0),b_2=(a_2-a_1),b_3=(a_3-a_2),\dots,b_k=(a_k-a_{k-1}),b_{k+1}=(n-a_k)$. What can you say about $b_1+b_2+\dots+b_{k+1}$? Are each $b_i$ bounded in a particular way? Does this match a known problem type to you? $\endgroup$ – JMoravitz May 31 '16 at 17:09
  • 1
    $\begingroup$ Not sure I understand the "while" condition tacked on these - it seems like the inequalities would take of this without further specification. Possible typo? $\endgroup$ – Joffan May 31 '16 at 17:24
  • $\begingroup$ @Joffan The while condition means that there are not sequential numbers for example 1,5,6,8 is not valid since 5,6 $\endgroup$ – JaVaPG May 31 '16 at 17:35
  • $\begingroup$ @JMoravitz I say that the following need to apply $1 \leq i \leq k+1,b_{i+1}-b{i}>1$ I also think that $b_1+...b_n=n$ $\endgroup$ – JaVaPG May 31 '16 at 17:39
  • $\begingroup$ @JaVaPG so you meant to write "while $a_i \neq a_{i-1}+1$" - ok $\endgroup$ – Joffan May 31 '16 at 17:45
2
$\begingroup$

From the original length $k$ sequence $a_1,\dots,a_k$, we form a bijection to the related length $k+1$ sequence $b_1,\dots,b_{k+1}$ where

$b_i = \begin{cases} a_1&\text{if}~i=1\\ a_i-a_{i-1}&\text{if}~i\in\{2,3,\dots,k\}\\ n-a_k&\text{if}~i=k+1\end{cases}$

Notice that $b_1+b_2+b_3+\dots+b_{k+1} = a_1+(a_2-a_1)+(a_3-a_2)+\dots+n-a_k = n$ as the series telescopes.

Given the conditions that $1\leq a_1\leq a_2\leq a_3\leq\dots \leq n$, this implies the conditions:

$\begin{cases}b_1+b_2+\dots+b_{k+1} = n\\ 1\leq b_1\\0\leq b_2\\ \vdots\\ 0\leq b_{k+1}\end{cases}$

Alternatively, given the conditions that $0<a_1<a_2<a_3<\dots a_k< n+1$ this implies the conditions:

$\begin{cases} b_1+b_2+\dots+b_{k+1} = n\\ 1\leq b_1\\ 1\leq b_2\\ \vdots\\ 1\leq b_k\\0\leq b_{k+1}\end{cases}$

If you add the additional condition that $a_i\neq a_{i-1}+1$ for any $i$ (note: your typo $a_i\neq a_{i+1}+1$ is always true since $a_i\leq a_{i+1}<a_{i+1}+1$ in both scenarios), then this is equivalent to adding the restriction that $b_i\neq 1$ for any $i\in\{2,3,\dots,k\}$

In the case with strict inequalities, this is easily managed by making the change of variable $c_1=b_1-1$, $c_i = b_i-2$ for each $i\in\{2,3,\dots,k\}$. Approach as usual with stars and bars.

In the case with $a_1\leq a_2\leq\dots$, then you can approach as in my answer for Number of ways to write $n$ as sum of $k$ non-negative integers without 1, iterating over how many and which of the $b_i$ are zero.


As an aside and to make for a more complete answer, the question of finding how many integer solutions there are to the system:

$\begin{cases} x_1+x_2+\dots+x_k=n\\ 0\leq x_i~\text{for each}~i\end{cases}$

can be found via stars-and-bars and has answer $\binom{n+k-1}{k-1}=\binom{n+k-1}{n} = \left(\!\!\binom{n}{k}\!\!\right)$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.