Enumerating possible number of satisfied linear equations

Question

Consider a system of linear equations of variable $x=(x_1,\cdots,x_n)$ where each $x_i\in\{ 0,1,\cdots,L-1 \}$. Clearly, there are $\frac{n(n-1)}{2}$ number of equations in the system.

$$x_i-x_j=0, \ \forall i,j \in \{1,\cdots,n\}, i<j$$

My question. For general $n$, what are the possible numbers of satisfied equations for $x\in\{ 0,1,\cdots,L-1 \}^n$? And, for each possible number, which equations can be satisfied?

Example. When $n=4$. The possible number $N$ of satisfied equations can be $N=0,1,2,3,6$.

(1) $N=0$. This means no equation is satisfied, i.e. $x_1,\cdots,x_4$ take $4$ different values, thus the number of configurations of $(x_1,\cdots,x_4)$ is $A(L,4)$, where $A(L,4)=C(L,4)\times 4!$.

(2) $N=1$. This mean only one equation is satisfied, then the number of configurations is $A(L,3)\times C(4,2)$. Specifically, since we constraint certain $x_i=x_j$, there are $3$ distinct values. Thus there are $A(L,3)$ ways to choose $3$ ordered distinct values from $\{1,\cdots,n\}$. Moreover, there are $C(4,2)$ ways to choose $(i,j)$ such that $x_i=x_j$. Thus overall, there are $A(L,3)\times C(4,2)$ configurations. We could also interprete this as the following graph, where each node represent a $x_i$ and two nodes $(i,j)$ are connected means that $x_i=x_j$:

(3) $N=2$. This means two equations are satisfied, then the number of configurations is $A(L,2)\times C(4,3)+A(L,2)\times C(4,2)$. See the second graph in the case $N=2$.

(4) $N=3$. This means $3$ equations are satisfied. $A(L,2)\times C(4,1)$. We could also think in the way of connecting nodes as follows: given $4$ nodes. We connect $3$ edges since $N=3$, and there are $3$ ways to connect them as follows (the blue solid lines).

The second and third one does not give any configuration, since for example, $E_1$ and $E_2$ means the $x_i$ associated with the connected three nodes are equal, then the dashed red line must exist as well.

(5) $N=4$. This means $4$ equations are satisfied. There is no configuration corresponding to this case, since if there are $4$ equations satisfied, we must have additional equation to be satisfied as well.

(6) $N=5$. This means $5$ equations are satisfied. There is no configuration corresponding to this case.

(7) $N=6$. This means $6$ equations are satisfied which means all $x_i$ are equal. Thus there is $A(L,1)$ configurations.

From this simple example, it seems that this problem can be transferred as:

Given $n$ nodes. How to connect $N$ edges such that in the graph there is no three-vertex induced path (otherwise there must exist another edge to connect the two end points of the chain). For each way, there will be $A(L,\text{Num of connected components})\times C(n,\text{isolated nodes})$ configurations.

It seems this problem seems quickly unfeasible when $n$ grows larger.. (not sure)

If this problem is hard,

1. could we expect that considering some special graph structure such that the problem can be solved?** i.e. consider

$$a_{ij}(x_i-x_j)=0, \ \forall i,j \in \{1,\cdots,n\}, i<j$$ where $a_{ij}$ are elements of adjacency matrix of the graph.

[Update: If consider triangle-free graphs, for example, complete bipartite graph (with $m,n$ nodes), then the number of $a_{ij}(x_i-x_j)=0$ can be $0,1,\cdots,mn$.

2. Or is there any other way to add constraints to make this problem is explicitly solvable?

Answer 1

First off, there are quite a few errors in the question presentation as mentioned in the comments.

An integer $N$ can represent the number of satisfied equations iff it can be written as $$N = \binom{m_1}2 + \binom{m_2}2 + \dots + \binom{m_k}2$$ with positive integers $m_i$ satisfying $$m_1 + m_2 + \dots + m_k = n$$ for some integer $L\geq k\geq 1$. The number of suitable variable assignments equals $$\sum_{m_1,\dots,m_k} \binom{L}{k} \binom{n}{m_1,m_2,\dots,m_k},$$ where the sum is taken over tuples $m_1,\dots,m_k$ satisfying the above two equalities. The last formula can also be rewritten in terms of partitions of $n$: $$\sum_{1q_1 + 2q_2 + \dots = n\atop q_1\binom{1}2 + q_2\binom{2}2 + \dots = N} \binom{L}{q_1 + q_2 + \dots}\frac{n!}{1!^{q_1}q_1!2!^{q_2}q_2!\cdots}.$$

Here is Sage code implementing this formula and as an example computing all suitable $N$ for $n=4$, $L=6$ and a variable $L$.