Constricted Arithmetic Progressions

Description of the problem

A stricly increasing sequence of integers \(0 = a_0< a_1 < \cdots < a_n\) is said to be \(m\)-constricted if \(1\leq a_{i+1}-a_i\leq m\) for every \(i=0,\ldots,n-1\). Today, I am going to count all \(m\)-constricted sequences of integers within the interval \(\[1,N\]\) for a fixed pair \((N,m)\).

A recursive solution

Let me use \(CSL(m,b,k)\) to denote the number of \(m\)-constricted sequences that start at 0 and end at \(b\) of length \(k\). I will always assume \(m\geq 1\).

The problem is equivalent to counting positive integer solutions of the equation \[ x_1 + \cdots + x_k = b \] with the constraint that \(1\leq x_i\leq m\).

We can immediately see that \(CSL(m,b,k)=0\) if \(bm\) because one cannot reach at \(b\) in 1 step of size less than or equal to \(m\) if \(b\) is greater than \(m\). Similarly, \(CSL(m,b,1)=1\) if \(b\leq m\). Finally, we also have a recursion relation: \[ CSL(m,b,k) = \sum_{i=1}^m CSL(m,b-i,k-1) \] Now, if we need to count all \(m\)-constricted sequences of length \(k\) inside \(\[1,N\]\) we need \[ CS(m,N,k) = CSL(m,N,k+1) \] As for all \(m\)-constricted sequences in \(\[1,N\]\) we get \[ CS(m,N,k) = \sum_{k=1}^{N-1} CSL(m,N,k+1) \] Notice that I only count the sequences of length greater than 1.

An implementation

Let me start by \(CSL\):

(let ((csl-table (make-hash-table :test #'equal)))
   (defun csl (m b k)
      (cond ((< b k) 0)
            ((= b k) 1)
            ((= k 1) (if (> b m) 0 1))
            (t (or (gethash (list m b k) csl-table)
                   (setf (gethash (list m b k) csl-table)
                         (loop for i from 1 to (min m (1- b)) sum (csl m (- b i) (1- k)))))))))

CSL

Then the number of all constricted sequences is given by

(defun cs (m N)
   (loop for k from 2 to N sum (csl m N k)))

CS

Let us test for a small case:

(loop for i from 2 to 6 collect (csl 3 i 2))
(cs 3 6)

(1 2 3 2 1)
24

and a large one:

(cs 10 20)

521472