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)\).
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.
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)))))))))CSLThen 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)))CSLet 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)
24and a large one:
(cs 10 20)521472