3
$\begingroup$

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$:

enter image description here

(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).

enter image description here

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$.

  1. Or is there any other way to add constraints to make this problem is explicitly solvable?
$\endgroup$
13
  • 1
    $\begingroup$ I think you can turn this into a question about integer partitions with at most n parts, and parts of size at most L. Number of satisfied equations can be determined by part multiplicity. So your question reduces to understanding some statistic on integer partitions, more or less. $\endgroup$ Commented Aug 18, 2023 at 11:35
  • $\begingroup$ I don't think I understand this problem. When $N=6$, why can't you take all the $x_i$'s to be equal? $\endgroup$ Commented Aug 18, 2023 at 14:33
  • $\begingroup$ @RichardStanley Sorry! I made a mistake. It is indeed all $x_i$ equal in the case of $N=6$. I will revise it now. $\endgroup$
    – tony
    Commented Aug 18, 2023 at 14:34
  • 1
    $\begingroup$ Why not $\binom{L}{4}4!$ for $N=0$? $\endgroup$
    – RobPratt
    Commented Aug 18, 2023 at 15:41
  • 3
    $\begingroup$ @chloe Partitions of $n$ with at most $k$ parts of size at most $L$ are counted by a coefficient of the appropriate $q$-binomial coefficient, see mathworld.wolfram.com/q-BinomialCoefficient.html. $\endgroup$ Commented Aug 18, 2023 at 19:21

1 Answer 1

2
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ Thank you very much for your answer. I understand it now. But my purpose is to obtain the closed form of the possible values of 'the number of satisfied equations', and their corresponding 'number of suitable variable assignment', since I need them for further analysis. Thus I am wondering if it would be possible to have closed form of them or bounds of them, in some special cases (if it is not possible to obtain in general)? Thank you again! $\endgroup$
    – tony
    Commented Aug 22, 2023 at 17:44
  • $\begingroup$ The claim in this answer implies that every $N$ upto at least $\frac{(n-1)^2}4$ (or so) is achievable. Perhaps, this result can be further improved. I do not see an easy way to tightly bound the corresponding number of solutions though. $\endgroup$ Commented Aug 22, 2023 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.