[Solved]: Count number of special onto functions

Problem Detail: 

We define an onto function from $[n] \times [n]$ to $[n-2] \cup \{0\}$ as follows, where $[n] = \{1,2,3,\ldots ,n\}$,

$$f : [n] \times [n] \rightarrow [n-2] \cup \{0\}.$$

1) $f(x,x) = 0$.

2) $f(x,y) = f(y,x) > 0$, for $y ≠ x$.

3) $f(x,y) \leq \max\{f(x,z),f(z,y)\}$ for all $x,y,z$ belonging to $[n]$.

How many such functions are possible for a given $n$? I have tried my best but I am not able to get any close to the solution! One may even see it as a undirected simple graph with n vertices, f(x,y) representing the edge weights. Any help is appreciated!

EDIT: i have been able to find that there are no such functions for n<3.

for n=3 we have one such function, for n=4, 13 are possible.

Asked By : Alicia

Answered By : Yuval Filmus

The parametrization you present is quite arbitrary, and the condition that the mapping be onto only serves to confuse; let's ignore it for now. Instead, given $n,c$, let us consider the number of colorings of $K_n$ using $c$ colors (in your case, $c=n-2$) such that condition (3) is satisfied: for every three vertices $i,j,k$, $$ c(i,j) \leq \max(c(i,k),c(j,k)). $$ What does this condition mean? Let's start by considering the case $c = 2$. For any triangle $i,j,k$, the only situation which is forbidden is $$ \{c(i,j),c(i,k),c(j,k)\} = \{1,1,2\}. $$

Let $G$ be the graph formed by the edges colored $1$. This condition states that if $(i,j),(i,k) \in G$ then also $(j,k) \in G$. It is not hard to prove that $G$ must be a disjoint union of cliques, and vice versa, every disjoint union of cliques satisfies the condition.

If $G$ is a disjoint union of cliques then the vertex sets of the cliques partition $[n]$; isolated vertices are considered as cliques of size $1$. Therefore the number of possible graphs (and so, possible colorings when $k = 2$) is the Bell number $B_n$.

The case of general $c$ is similar. Consider for example $c = 3$. The graph induced by edges colored $1,2$ must be a disjoint union of cliques, and within each such clique, the graph induced by edges colored $1$ must be a disjoint union of cliques. Therefore each possible coloring corresponds to a two step partition of $[n]$: first we partition $[n]$, and then we further partition each of the part. The number of such two step partitions is a so-called higher-order Bell number, the row $p = 2$ in this case. For general $c$, consult this table at row $p = c-1$.

Finally, what if we want to count the number of onto mappings? We can use the inclusion-exclusion principle. Let $X(n,C)$ denote the number of colorings using colors from $C$, and let $X(n,c) = X(n,[c])$; note that $X(n,C) = X(n,|C|)$. Also let $Y(n,C),Y(n,c)$ denote the number of onto colorings. We have

$$ Y(n,c) = Y(n,[c]) = \sum_{D \subseteq [c]} (-1)^{c-|D|} X(n,D) = \sum_{i=0}^c (-1)^{c-i} \binom{c}{i} X(n,i). $$

For example, if $n = 4$ and $c = 2$ then $$ Y(4,2) = \binom{2}{0} X(4,2) - \binom{2}{1} X(4,1) + \binom{2}{2} X(4,0) = 1 \cdot 15 - 2 \cdot 1 + 1 \cdot 0 = 13. $$

How do we compute $X(n,c)$? The page linked to above gives the following recurrence:

$$ X(n,1) = X(0,c) = 1, \quad X(n,c) = \sum_{k=1}^n \binom{n-1}{k-1} X(k,c-1) X(n-k,c). $$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12636