Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A $k$-term combinatorial progression of order $2$ is defined as a set of positive integers $A=\{x_1<x_2<\cdots x_k\}$ such that the set $\{x_{i+1}-x_i:1\le i\le k-1\}$ has cardinality at most $2$.

My question is given a positive integer $N$, how many $k$-term combinatorial progressions of order $2$ will exist in $\{1,2\cdots N\}$? If not a closed formula can a reasonable upper bound for this number be deduced? For example if we replace the term combinatorial progression with arithmetic progression then a reasonable upper bound is $N^2/k^2$.

Any help or ideas please.

Thanks.

share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

A recursive analysis is also possible.

Let $P_k(n)$ be the set of $k$-term combinatorial progressions of order $2$ in $[n]$, and let $p_k(n)=|P_k(n)|$. I claim that $$p_{k+1}(n+1)=p_k(n)+p_k(n-1)\tag{1}$$

for $k,n\ge 1$, with initial conditions $p_1(n)=n$ for all $n\ge 1$ and $p_k(0)=0$ for all $k\ge 1$.

Proof: Clearly $p_k(n)=0$ if $k>n$, and $p_k(k)=1$, so $(1)$ holds for $1\le n\le k$.

Let $P_k^'(n)$ be the set of progressions in $P_k(n)$ that contain $n$, and let $p_k^'(n)=|P_k^'(n)|$. Every progression in $P_{k+1}^'(n+1)$ is uniquely obtained by appending $n+1$ to a progression in $P_k^'(n)\cup P_k^'(n-1)$, so $p_{k+1}^'(n+1)=p_k^'(n)+p_k^'(n-1)$. Moreover, $$P_{k+1}(n+1)\setminus P_{k+1}^'(n+1)=P_{k+1}(n)\;,$$ so

$$\begin{align*} p_{k+1}(n+1)&=p_{k+1}(n)+p_k^'(n)+p_k^'(n-1)\\ &=p_{k+1}(n)+\Big(p_k(n)-p_k(n-1)\Big)+\Big(p_k(n-1)-p_k(n-2)\Big)\\ &=p_{k+1}(n)+p_k(n)-p_k(n-2)\tag{2}\;. \end{align*}$$

Now assume that $(1)$ holds for some $n$ and $k$; then by $(2)$ we have

$$\begin{align*} p_{k+1}(n+2)&=p_{k+1}(n+1)+p_k(n+1)-p_k(n-1)\\ &=p_k(n)+p_k(n-1)+p_k(n+1)-p_k(n-1)\\ &=p_k(n+1)+p_k(n)\;; \end{align*}$$

this completes the proof of $(1)$. $\dashv$

Next,

$$p_k(n)=(k+1)2^{k-2}+(n-2k+1)2^{k-1}\tag{3}$$ for $n\ge 2k-1$.

Proof: Let $d=n-(2k+1)$, and rewrite $(3)$ as $$p_k(2k-1+d)=(k+1+2d)2^{k-2}$$ for $k\ge 1$ and $d\ge 0$. For $k=1$ this is simply the initial condition $p_1(d+1)=d+1$, and $(1)$ then gives us $$\begin{align*} p_{k+1}(2k+1+d)&=p_k(2k+d)+p_k(2k-1+d)\\ &=\big(k+1+2(d+1)\big)2^{k-2}+(k+1+2d)2^{k-2}\\ &=(2k+4+4d)2^{k-2}\\ &=(k+2+2d)2^{k-1} \end{align*}$$ to complete the induction. $\dashv$

In fact it’s not hard to check that $(3)$ gives the correct result for $n=2k-2$ as well and exceeds the correct value by $1$ when $n=2k-3$.


I tried to see what happens when $n\le 2k$. For this it was convenient to set $a_n(k)=p_k(n+k)$. It’s not hard to see that $a_0(k)=1$ for $k\ge 1$, and if we further set $a_n(0)=1$, $(1)$ implies (after a bit of work) that $$a_n(k)=n+1+\sum_{i=1}^{k-1}a_{n-1}(k)$$ for $k>0$. By direct computation we then find that

$$\begin{align*} a_1(k)&=\binom{k+1}1\\ a_2(k)&=2\binom{k+1}0+\binom{k+1}2\\ a_3(k)&=2\binom{k+1}1+\binom{k+1}3\\ a_4(k)&=3\binom{k+1}0+2\binom{k+1}2+\binom{k+1}4\\ a_5(k)&=3\binom{k+1}1+2\binom{k+1}3+\binom{k+1}5\\ a_6(k)&=4\binom{k+1}0+3\binom{k+1}2+2\binom{k+1}4+\binom{k+1}6\;, \end{align*}$$

which leads to the obvious conjecture that

$$a_n(k)=\sum_{i=1}^{\lceil n/2\rceil}i\binom{k+1}{n+2-2i}\;.$$

This conjecture is easily proved by induction:

$$\begin{align*} a_{2n+1}(k)&=2n+2+\sum_{i=1}^{k-1}a_{2n}(k)\\ &=2n+2+\sum_{i=1}^{k-1}\left(\binom{i+1}n+2\binom{i+1}{n-2}+\ldots+(n+1)\binom{i+1}0\right)\\ &=\binom{k+1}{n+1}+2\binom{k+1}{n-1}+\ldots+(n+1)\binom{k+1}1\\ &=\sum_{i=1}^{n+1}i\binom{k+1}{2n+3-2i}\;, \end{align*}$$

and

$$\begin{align*} a_{2n+2}(k)&=2n+2+\sum_{i=1}^{k-1}a_{2n+1}(k)\\ &=2n+3+\sum_{i=1}^{k-1}\left(\binom{i+1}{n+1}+2\binom{i+1}{n-1}+\ldots+(n+1)\binom{i+1}1\right)\\ &=\binom{k+1}{n+2}+2\binom{k+1}{n}+\ldots+(n+1)\binom{k+1}2+(n+2)\binom{k+1}0\\ &=\sum_{i=1}^{n+2}i\binom{k+1}{2n+4-2i}\;. \end{align*}$$

Unfortunately, while this is rather pretty, it doesn’t seem to be very tractable: I’ve had no luck coming up with a closed form.

share|improve this answer
    
Can you explain the following line: "Every progression in $P'_{k+1}(n+1)$ is uniquely obtained by appending $n+1$ to a progression in $P′_k(n)\cup P′_k(n−1)$." For $k=3$, $n=7$ consider the progression $1,3,5,8$. Am I missing something here? –  Shahab May 21 '12 at 6:55
    
@Shahab: $\{1,3,5,8\}$ isn’t a progression of order $2$: the last gap is too big. –  Brian M. Scott May 21 '12 at 6:59
    
I think you misunderstand, the gaps 3-1=2, 5-3=2, 8-5=3 all belong to the set $\{2,3\}$ which has order 2. Hence it is a 4-term combinatorial progression of order 2. –  Shahab May 21 '12 at 7:33
    
@Shahab: You’re right: I was trying to find a version of André’s argument that would give more information about the cases with small $n$, and didn’t go back to check the definition carefully; he and I both oversimplified the definition to require that all gaps be either $1$ or $2$. I’ll try to make time to look at this again. –  Brian M. Scott May 21 '12 at 7:49
add comment

It is typographically easier to work with the number $m$ of "gaps." So $m=k-1$. We will assume that $N$ is larger than $2m$. We have not done the analysis for $N$ between $m+1$ and $2m$, and are not optimistic about obtaining a simple closed form for $N$ in that range.

There is precisely $1$ way to have the sum of the $m$ gaps equal to $m$. I prefer to call this $\binom{m}{0}$.

There are $\binom{m}{1}$ ways to have the sum of the $m$ gaps be equal to $m+1$, for we must choose $1$ place to put a gap of length $2$, with the rest of length $1$.

There are $\binom{m}{2}$ ways to have the sum of the gaps be equal to $m+2$, for we must choose $2$ places to put a gap of length $2$.

And so on. Finally, there are $\binom{m}{m}$ ways to have the sum of the gaps be equal to $2m$.

If the sum of the lengths of the gaps is $m$, then $x_1$ can be any of $1$ to $N-m$. If the sum of the lengths is $m+1$, then $x_1$ can be any of $1$ to $N-m+1$, and so on. So the number of $(m+1)$-term combinatorial progressions of order $2$ is $$\binom{m}{0}(N-m)+\binom{m}{1}(N-m-1)+\binom{m}{2}(N-m-2))+\cdots +\binom{m}{m}(N-2m).$$ One can find an explicit formula for the sum. The terms in $N$ have sum $N2^m$. We need to subtract $$m\binom{m}{0}+(m+1)\binom{m}{1}+(m+2)\binom{m}{2}+\cdots +2m\binom{m}{m}.$$ This sum can be broken up into two parts, $\sum_{i=0}^m m\binom{m}{i}$, which is $m2^m$, and $\sum_{i=0}^m i\binom{m}{i}$, which is not difficult, we can pick it up from the expected value of a binomial, or by symmetry. It is $m2^{m-1}$.

There is undoubtedly a nicer generating functions approach!

share|improve this answer
    
Isn't $\sum i\tbinom{m}{i}=m2^{m-1}$? Why have you written "It is $2^{m-1}$" in your second last line? Also, may I conclude that for $N>2m$, the answer is $N2^{k-1}-3(k-1)2^{k-2}$? –  Shahab May 12 '12 at 3:58
    
@Shahab: Thanks for spotting the typo. Indeed it is $m2^{m-1}$. And yes, we get, in my notation, $N2^m -(3m)2^{m-1}$, which, in terms of $k$, is what you wrote above. –  André Nicolas May 12 '12 at 4:45
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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