Finding the number of sequences with $0 \leq a_m \leq 3m$

Question

Problem: Let $\alpha, \beta$ be non-negative numbers. Suppose the number of strictly increasing sequences $a_0, a_1, a_2 \cdots a_{2014}$ satisfying $0 \leq 3m$ is $2^{\alpha}(2\beta+1)$. Find $\alpha$.

My attempt:

I tried to find an explicit form for the $nth$ of the sequence using recursions.

Let $P_{n,k}$ be the number of sequences of length $n$ that end in $k$, i.e, $a_n=k$.

Then it's easy to say that the following recursions hold:

$P_{n+1, n+1}=P_{n, n}$

$P_{n+1, n+2}=P_{n, n}+P_{n, n+1}$

$P_{n+1, n+3}=P_{n, n}+P_{n, n+1}+P_{n, n+2}$

And so on.. and the last equation is,

$P_{n+1, 3n+3}=P_{n, n}+P_{n, n+1}+P_{n, n+2}+\cdots + P_{n, 3n}$

And of course, we want $P_{n+1, n+1}+ P_{n+1, n+2}+P_{n+1, n+3}+ \cdots + P_{n+1, 3n+3}$

But i can't make any more progress. So, any help will be appreciated.

Answer 1

If $P_{n,k}$ is the amount of sequences of $a_0,\ldots, a_n$ such that $a_n = k$ and for any $m$ we have $0\leq a_m \leq 3m$ then:

$$P_{n,k} = \begin{cases} 0 &\text{if } k < n\\ 1 & \text{if } k = n\\ \displaystyle\sum_{i=0}^{k-n} P_{n-1,n-1+i} & \text{if } n < k \leq 3n\\ 0 & \text{if } k > 3n \end{cases}$$

The amount of sequences of $2015$ elements such that for every element we have $0\leq a_m \leq 3m$ is exactly the amount of sequences of $2016$ elements with the same condition as before and $a_{2015} = 3\cdot 2014 + 1$, i.e. $P_{2015, 6053}$

One can work out that:

$$P_{n,n} = 1$$

$$P_{n,n+1} = \sum_{k=0}^n P_{k,k}$$

$$P_{n,n+2} = \sum_{k=0}^n P_{k,k} + \sum_{k=1}^nP_{k,k+1}$$

$$P_{n,n+3} = \sum_{k=0}^n P_{k,k} + \sum_{k=1}^nP_{k,k+1} + \sum_{k=2}^n P_{k,k+2}$$

$$P_{n,n+4} = \sum_{k=0}^n P_{k,k} + \sum_{k=1}^nP_{k,k+1} + \sum_{k=1}^n P_{k,k+2} + \sum_{k=2}^n P_{k,k+3}$$ $$\cdots$$

$$P_{n,n+m} = \sum_{t=0}^{m-1}\left(\sum_{k=\lceil t/2\rceil}^n P_{k,k+t} \right) $$

Answer 2

It seems there are $\frac 1{2\cdot 2015+1}{3\cdot 2015 \choose 2015}$ such sequences. I modeled the recurrence in Excel, finding $3,12,55,273,1428,7752$ such sequences starting at $m=1$. Looking up in OEIS finds A001764 I don't have a proof that this is correct, but it certainly seems one could make a stars and bars argument.

Answer 3

Inspired by Ross's answer, we'll prove that there is a bijection between equivalence classes of such sequences and subsets of $\{0,\ldots, 3n+2\}$ with size $n+1.$ We will first define an equivalence relation $\sim$ on $\{0,\ldots, 3n+3\}$ by saying two sets are equivalent if they are cyclic shifts of each other, i.e. $A\sim B$ if $B = A + j \mod 3n+4$ for some $j.$ The induced equivalence relation on $\{0,\ldots, 3n+2\}$ is the obvious one (if a set contains $3n+3$ then it has size $n$ after removal, so we don't care about it).

Evidently each equivalence class has size $3n+4 - (n+1) = 2n+3$ since each time we shift so one of the elements is on the $3n+3$ space, we remove one set from the equivalence class in $\{0,\ldots, 3n+3\}.$ Note that for sets $A$ of size $n+1,$ no cyclic shift of $A$ other than the trivial one will be equal to $A,$ since if $A = A + j,$ then we would have $j(n+1) \equiv 0 \mod 3n+4,$ but $n+1$ is relatively prime to $3n+4,$ so it would have to be the trivial shift.

Now there are two things to check:

1. That no two sequences satisfying the conditions lie in the same equivalence class
2. And every equivalence class contains such a sequence

For 1. We note that $a_0 = 0$ for any sequence. Suppose $a_0, \ldots, a_n$ is a valid sequence, note that the first shift giving a new subset containing $0$ is by at least $4,$ since $a_n \le 3n.$ But then the second smallest element will be at least $4,$ which is impossible. The claim follows by iterating this argument.

2. This part is harder. Let $A \subset \{0,\ldots, 3n+2\}$ be a subset of size $n+1$ containing $0.$ There are exactly $n+1$ shifts of $A$ containing $0$ (including $A$ itself).

If $A_0 = \{0 = a_0 < a_1 < \ldots < a_n\} = A,$ then define the $k^{th}$ shift $$A_{k} = \{0, a_{k+1} - a_{k}, \ldots, a_n - a_k, a_0 + (3n+4)-a_k, \ldots, a_{k-1} + 3n+4 - a_k\}.$$

Assume that for every $k,$ $A_k$ is not a valid sequence. This means that either there exists $j < k$ for which $a_j + 3n+4 - a_k > 3(n+j-k+1),$ i.e. $a_j \ge 3(j-k) + a_k,$ or there exists $i > k$ for which $a_i - a_k > 3(i-k),$ i.e. $a_i \ge 3(i-k) + 1.$

If $i$ is an index such that one of the two above conditions is met, we say $i\to k.$ In this way, we can form an infinite chain $\cdots \to i_{m} \to i_{m-1} \to \cdots \to 1,$ since everything is pointed to by something (not itself, in particular). Thus pick a cycle in this chain (minimal in the sense that it only cycles once). Then by repeatedly using the above conditions we will get $a_{i_k} \ge a_{i_k} + 1$ (we will have at least one of the second type since we come back to $i_k$), a contradiction.

To calculate $\alpha$ as wanted in the problem, do the standard floor calculation for $\binom{3n+3}{n+1}.$