# Counting number of $k$-sequences

I am studying a special type of a sequence on the naturals which I am calling a weak arithmetic progression. Formally I call a k-sequence $x_1<x_2<\cdots< x_k$ a weak arithmetic progression (WAP) if $\exists d\in \mathbb{N}$ such that $x_{i+1}-x_i\in\{1,d\}$. Now given two natural numbers $n\ge k\ge 1$, I wish to count the number of WAP's of length k within $\{1,2,3\ldots, n\}$, i.e. the number of WAP's of length k where each WAP consists of elements from $\{1,2\cdots n\}$. This is how I am reasoning:

First fix a $d$. Consider any collection of $k$ numbers (as yet identified as $x_1,\cdots x_k$) and write them with spaces in the middle. We will count in how many ways we can put either $d$ or $1$ in the $k-1$ spaces or gaps between these numbers. Now if all the $k-1$ gaps between the numbers have to be filled up by $d$, then the first element of the $k$-WAP can be chosen in $n-(k-1)d$ ways. I will refer to this as $(n-(k-1)d)\tbinom{k-1}{0}$. If all but one of the gaps between the numbers have to be filled up by $d$, then there are $(n-(k-2)d-1)\tbinom{k-1}{1}$ ways, the binomial coefficient indicating where to place the number $1$ in the $k-1$ gaps. Likewise for all but $r$ gaps being filled up by $d$ there would be $(n-(k-r-1)d-r)\tbinom{k-1}{r}$ ways and so for a fixed $d$ there are $\sum_{r=0}^{k-1}(n-(k-r-1)d-r)\tbinom{k-1}{r}=(n-d(k-1))2^{k-1}+(d-1)(k-1)2^{k-2}$ $k$-WAPs. Now to get the total number of $k$-WAPs I sum over $d$ from $2$ to $n-k+1$, i.e. $\sum_{d=2}^{n-k+1}\Big ((n-d(k-1))2^{k-1}+(d-1)(k-1)2^{k-2}\Big )$ and furthermore since double counting of consecutive k-terms occurs for each $d$ in this sum, we subtract $(n-k+1)(n-k-1)$, i.e the final answer is $\sum_{d=2}^{n-k+1}\Big((n-d(k-1))2^{k-1}+(d-1)(k-1)2^{k-2}\Big )-(n-k-1)(n-k+1)$.

My questions are:

1. Is the above reasoning correct? If not, then what is the correct approach?
2. What is a good upper bound for the above sum which can be solved for $n$? I need $n$ as a function of $k$ for further study.

Thanks

-
You could test you example. For example, with $n=7$ and $k=3$ I think there are $29$ possible sequences but your expression seems to give $16+12-5=23$, though I may have made an error. –  Henry Jun 3 '12 at 12:04
Your description says nothing about what $n$ is used for. Do you suppose $x_k\leq n$? –  Marc van Leeuwen Jun 3 '12 at 14:21
I can't understand what this is about, because you use informal language for which it is not clear what it would mean exactly. Like "gaps between the numbers have to be filled up by $d$". Feel free to use informal language, but if you're describing a procedure for constructing and then counting solutions, you must make sure it is clear exactly what the procedure does, and why it constructs every possible solution exactly once. –  Marc van Leeuwen Jun 3 '12 at 14:25
I am sorry. I have tried to clarify a little. I hope its all clear now. –  Shahab Jun 3 '12 at 15:26
It's not clear yet to me what "WAP's of length k within {1,2,3…,n}" means. Does this mean that $x_k\in \{1 \cdots n \}$? –  leonbloy Jun 3 '12 at 16:08

I suspect that your approach is more or less correct, but it's difficult to me to follow. Let's simplify it a little.

Our statement, if I understand it right, is: given positive integers $(n,k,d)$, we want to count $N(n,k,d)$ the number of sequences $x_1, x_2 \cdots x_k$ with $x_{i+1}−x_i \in \{1,d\}$ and $x_k\le n$

It's simpler to work with $d_i = x_{i+1}−x_i$ ($d_i \in \{1,d\}, \sum_{i=1}^k d_i =D\le n$) (let's assume $x_0=0$) .

And it's even simpler to define $$b_i = \frac{d_i-1}{d-1}$$ so that $b_i \in \{0,1\}$, and $\sum_{i=1}^k b_i = W = \frac{D-k}{d-1} \le m = \frac{n-k}{d-1}$

So, we have reduced the problem to that of counting the number of bit strings of length $k$ that have weight (number of ones: $W=\sum_{i=1}^k b_i$) less or equal than $m = \frac{n-k}{d-1}$

This is simply $$\sum_{w=0}^{ w_M } {k \choose w} \hspace{1cm } w_M = \min\left(k,\left\lfloor \frac{n-k}{d-1} \right\rfloor\right)$$

For large $n,k$, this can be approximated by a gaussian integral.

Edited: I (wrongly) assumed that $d$ was given. If it's not, we can sum over the possible values, but letting asside the zero-weight case (unit gaps in the original statement). So, the total number of sequences would be

$$1 + \sum_{d=2}^{n-k+1} \sum_{w=1}^{ w_M } {k \choose w}$$

with $w_M$ as above. This can be polished a little but perhaps not much.

Added: A good approximation for large $n,k$ (and probably some bounds) can be obtained by swapping the sums:

Because

$$\sum_{d=2}^{n-k+1} \sum_{w=1}^{ w_M } {k \choose w} \approx \sum_{w=1}^{k} \sum_{d=2}^{(n-k)/w+1} {k \choose w} = \sum_{w=1}^{k} \frac{n-k}{w} {k \choose w} = (n-k) S_k$$

with $S_k = \sum_{w=1}^{k} \frac{1}{w} {k \choose w}$

So, if $N(n,k)$ is the total counting of sequences and we want to solve (approximate/bound) for $n$, we'd get:

$$n\approx \frac{N(n,k)-1}{S_k}+k$$

For approximations of $S_k$, see here. Plugging the most rough approximation, $S_k \approx \frac{2^{k+1}}{k}$, we get

$$n \approx 2 \, k \, N(n,k) 2^{-k}+k$$

Added: I've not proven, but I conjecture (both from the derivation and from numeric valeus) that the above expression

$$N(n,k) \approx 1 + (n-k) S_k \tag{1}$$

is actually an upper bound. One can also add a small correction term (slightly better approximation, but now it's not a strict bound) but substracting $1/2$ in the inner summation (to account for the low-rounding effect of the floor function). Then we get

$$N(n,k) \approx \frac{3}{2} + (n-k) S_k - 2^{k-1} \tag{2}$$

this improves the approximation for medium values of $k$. Here's an graph of the ratio of the exact value over the approximation (1) (blue) and (2) (green), for $n=30$.

-
We are given only (n,k) and we have to take all possible d's. –  Shahab Jun 3 '12 at 17:25
Ah, I'd missed that. Edited. –  leonbloy Jun 3 '12 at 18:03
Why do you assume $x_0=0$. What will go wrong if I don't assume that? Secondly can you tell me an upper bound for the above of the form f(n,k) where f(n,k)=0 can be solved for n? –  Shahab Jun 4 '12 at 6:43
It's practically necessary (in this approach, and, I'd bet, in most) to assume $x_0=0$, because otherwise, either the first "gap" $x_1-x_0$ is not restricted to {1,d}, either (if you choose to consider $x_2-x_1$ as the first gap) the gaps do not fully specify the realization. –  leonbloy Jun 4 '12 at 12:00
I added some approximate solution (I guess it can be worked into a bound) for $n$ –  leonbloy Jun 5 '12 at 12:01