Neighbourly Constraints

Let $T(n, m)$ be the number of $m$-tuples of positive integers such that the sum of any two neighbouring elements of the tuple is $\le n$.

For example, $T(3, 4)=8$, via the following eight $4$-tuples:
$(1, 1, 1, 1)$
$(1, 1, 1, 2)$
$(1, 1, 2, 1)$
$(1, 2, 1, 1)$
$(1, 2, 1, 2)$
$(2, 1, 1, 1)$
$(2, 1, 1, 2)$
$(2, 1, 2, 1)$

You are also given that $T(5, 5)=246$, $T(10, 10^{2}) \equiv 862820094 \pmod{1\,000\,000\,007}$ and $T(10^2, 10) \equiv 782136797 \pmod{1\,000\,000\,007}$.

Find $T(5000, 10^{12}) \bmod 1\,000\,000\,007$.

We need to set up a dynamic programming algorithm to solve this problem. The main idea behind dynamic programming is to solve the problem in a step-by-step manner, solving sub-problems and storing their solutions, so you don’t have to resolve them every time.

We can think of f(i, j) as the number of ways to arrange “i” tuples such that the last number is “j”. The limiting factor is that the sum of two adjacent numbers cannot exceed “n”. Hence, the previous (i-1) tuple must be from “n-j..”n.

Define:

\[
dp[i][j] = \sum_{k=1}^{min(j,n-j)} dp[i-1][k]
\]

then:

\[
dp[i][j] = dp[i][j-1] + dp[i-1][j] – dp[i-1][max(0,2*j-n-1)]
\]

Now, we realize that this solution will obviously not fit for the data given in the problem. N is as big as 5000 and M is as big as 10^12. We need to optimize the problem further with the help of matrix exponentiation.

Define: B[i] = dp[1][i] for all i = 1..N

Now consider the matrix A[i][j] where i, j are from 1..N such that:

A[i][j] = 1 if (i>=j and i<=n-j) A[i][j] = 0 otherwise. We feel that: dp[m][i] = sum over all j(A[i][j]*dp[m-1][j]) And we also know that: B = A*B for a matrix multiplication. With this insight, we can find: B = power(A, m-1)*B Where 'power(A, m-1)' is finding the 'm-1' power of matrix 'A' with time complexity 'O(m)'. B[i] is the number of tuples of length 'm' such that the last number is 'i'. Then we need to sum up all B[i] to get the answer. After all this, however, we still have to do many calculations for number pairs that are divisible by 1,000,000,007. Implementing this and optimizing it using fast matrix exponentiation with time complexity 'O(log(m))', will give us: T(5000, 10^12) ≡ 596212596 (modulo 1,000,000,007) This is a challenging combinatorial problem and the solution is not trivial, it involves dynamic programming, matrix exponentiation and handling of big integers.

More Answers: