---
abstract: 'Set-coloring a graph means giving each vertex a subset of a fixed color set so that no two adjacent subsets have the same cardinality. When the graph is complete one gets a new distribution problem with an interesting generating function. We explore examples and generalizations.'
address: |
    Department of Mathematical Sciences\
    Binghamton University (SUNY)\
    Binghamton, NY 13902-6000\
    U.S.A.
author:
- Thomas Zaslavsky
date: '5 July 2006; first version 25 June 2006. This version '
title: 'A new distribution problem of balls into urns, and how to color a graph by different-sized sets'
---

Balls into urns {#balls-into-urns .unnumbered}
---------------

We have $n$ labelled urns and an unlimited supply of balls of $k$ different colors. Into each urn we want to put balls, no two the same color, so that the number of colors in every urn is different. Balls of the same color are indistinguishable and we don’t care if several are in an urn. How many ways are there to do this? (The reader will note the classical terminology. Our question appears to be new but it could as easily have been posed a hundred years ago.) Call the answer ${\chi^{\mathrm{set}}}_n(k)$. We form the exponential generating function, $${\mathbf X}(t) := \sum_{n=0}^\infty {\chi^{\mathrm{set}}}_n(k) \frac{t^n}{n!} \ ,$$ taking ${\chi^{\mathrm{set}}}_0(k) = 1$ in accordance with generally accepted counting principles. Then we have the generating function formula $${\label{E:urns}{}}
{\mathbf X}(t) = \prod_{j=0}^k \Big[ 1 + \binom{k}{j} t \Big] .$$ For the easy proof, think about how we would choose the sets of colors for the urns. We pick a subset of $n$ integers, $\{j_1<j_2<\cdots j_n\} \subseteq \{0,1,\ldots,k\}$, and assign each integer to a different urn; then we choose a $j_i$-element subset of $[k] := \{1,2,\ldots,k\}$ for the $i$th urn. The number of ways to do this is $$\sum_{S\subseteq[k]: |S|=n} n! \, \prod_{j\in S} \binom{k}{j}.$$ Forming the exponential generating function, the rest is obvious.

There are several interesting features to the question and its answer. First of all, as far as I know the question is a new distribution problem. Second, the sequence ${\chi^{\mathrm{set}}}_0(k), {\chi^{\mathrm{set}}}_1(k), \ldots, {\chi^{\mathrm{set}}}_{k+1}(k)$, besides (obviously) being increasing, is logarithmically concave, because the zeros of its generating function are all negative real numbers. Third, the theorem generalizes to graphs and can be proved by means of Möbius inversion over the lattice of connected partitions of the vertex set, just as one proves the Möbius-function formula for the chromatic polynomial. Fourth, and the graphical extension generalize to formulas in which the binomial coefficients are replaced by arbitrary quantities. Finally, this way of putting balls into urns, and its graphical generalization, are really a problem of coloring gain graphs by sets, which suggests a new kind of gain-graph coloring; we discuss this briefly at the end.

Some elementary notation: ${\mathbb{N}}$ denotes the set of nonnegative integers and $[n] := \{1,2,\ldots,n\}$ for $n\geq0$; $[0]$ is the empty set. Furthermore, ${\mathcal{P}}_k$ denotes the power set of $[k]$.

To set the stage for the graph theory, first we generalize Equation . Let $\alpha := (\alpha_j)_0^\infty$ be a sequence of numbers, polynomials, power series, or any quantities for which the following expressions and generating functions, including those in Equation , are defined. Let $\beta_r := \sum_{j=0}^\infty \alpha_j^r$. Let $\chi_n(\alpha)$ := the sum of $\prod_1^n \alpha_{f(i)}$ over all injective functions $f : [n] \to {\mathbb{N}}$. Then, generalizing , and with a similar proof, we have $${\label{E:gf}{}}
{\mathbf X}_a(t) := \sum_{n=0} \chi_n(\alpha) \frac{t^n}{n!} =  \prod_{j=0}^\infty \big[ 1 + \alpha_j t \big] .$$ As with the set-coloring numbers, if $\alpha$ is nonnegative and is a finite sequence $(\alpha_j)_{j=0}^k$, then the sequence $(\chi_n(\alpha))$ is logarithmically concave. We can even closely approximate the index $m$ of the largest $\chi_n(\alpha)$. Darroch’s Theorem 3 [@Darroch] says that $m$ is one of the two nearest integers to $$M := k+1 - \sum_{j=0}^k \frac{1}{1+\alpha_j} ,$$ and $m=M$ if $M$ is an integer.[^1]

A combinatorial problem that falls under Equation is filling urns from the equivalence classes of a partition. We have a finite set ${\mathcal{S}}$ with a partition that has $k+1$ blocks ${\mathcal{S}}_0, {\mathcal{S}}_1,\ldots, {\mathcal{S}}_k$. We want the number of ways to put one ball into each of $n$ labelled urns with no two from the same block. Call this number $\chi_n(\pi)$. The generating function is with $\alpha_j = |{\mathcal{S}}_j|$. It is clear that $\chi_n(\pi)$ increases with its maximum at $n=k$. As an example let ${\mathcal{S}}=$ the lattice of flats of a rank-$k$ matroid, two flats being equivalent if they have the same rank; then $\alpha_j = W_j$, the number of flats of rank $j$ (the Whitney number of the second kind). In particular, if ${\mathcal{S}}=$ the lattice of subspaces of the finite vector space ${\operatorname{GF}}(q)^k$, the rule being that each urn gets a vector space of a different dimension, then $${\mathbf X}_{\mathcal{S}}(t) = \prod_{j=0}^k \left( 1 + {{\begin{bmatrix}}k\\ j {\end{bmatrix}}} t \right),$$ where ${{\begin{bmatrix}}k\\ j {\end{bmatrix}}}$ is the Gaussian coefficient. For a similar example where the $\alpha_j$ are (the absolute values of) the Whitney numbers of the first kind, take ${\mathcal{S}}$ to be the broken circuit complex of the matroid.

Graphs {#graphs .unnumbered}
------

In the graphical generalization we have ${\Delta}$, a graph on vertex set $V=[n]$. $\Pi({\Delta})$ is the set of *connected partitions* of ${\Delta}$, that is, partitions $\pi$ of $V$ such that each block $B \in \pi$ induces a connected subgraph. The set $\Pi({\Delta})$, ordered by refinement, is a geometric lattice with bottom element $\hat0$, the partition in which every block is a singleton. A *set $k$-coloring* of ${\Delta}$ is a function $c: V \to {\mathcal{P}}_k$ that assigns to each vertex a subset of $[k]$, and it is *proper* if no two adjacent vertices have colors (that is, sets) of the same cardinality. We define the *set-coloring function* ${\chi^{\mathrm{set}}}_{\Delta}(k)$ to be the number of proper set $k$-colorings of ${\Delta}$. This quantity is positive just when the chromatic number of ${\Delta}$ does not exceed $k+1$.

The *extended Franel numbers* are $${\mathrm{Fr}}(k,r) := \sum_{j=0}^k \binom{k}{j}^r$$ for $k, r \geq 0$. (The Franel numbers themselves are the case $r=3$ [@OEIS Sequence A000172]. There is a nice table of small values of the extended numbers at [@BinomMW]. There are closed-form expressions when $r \leq 2$ but not otherwise.) The set-coloring function satisfies $${\label{E:set-coloring}{}}
{\chi^{\mathrm{set}}}_{\Delta}(k) = \sum_{\pi\in\Pi({\Delta})} \mu(\hat0,\pi) \prod_{B\in\pi} {\mathrm{Fr}}(k,|B|)$$ where $\mu$ is the Möbius function of $\Pi({\Delta})$.

It is amusing to see the high-powered machinery involved in deriving from . We outline the method. Obviously, ${\chi^{\mathrm{set}}}_{K_n}(k) = {\chi^{\mathrm{set}}}_n(k)$. In we substitute the known value $\mu(\hat0,\pi) = \prod_{B\in\pi} [ -(-1)^{|B|}(|B|-1)! ]$. Then we apply the exponential formula to the exponential generating function, substituting $y = -\binom{k}{j}t$ in $\log(1-y) = -\sum_{n=1}^\infty y^n/n$ and finding that the exponential and the logarithm cancel.

Rather than proving Equation itself, we generalize still further; the proof is no harder. Define $$\chi_{\Delta}(\alpha) := \sum_f  \prod_{i=1}^n \alpha_{f(i)},$$ summed over all functions $f: V \to {\mathbb{N}}$ such that $f(i) \neq f(j)$ if $i$ and $j$ are adjacent; that is, over all proper ${\mathbb{N}}$-colorings of ${\Delta}$. One could think of $f$ as a proper ${\mathbb{N}}$-coloring weighted by $\prod \alpha_{f(i)}$. (Again, we assume $\alpha$ has whatever properties are required to make the various sums and products in the theorem and its proof meaningful. A sequence that is finitely nonzero will satisfy this requirement.)

[\[T:graph-labels\]]{} We have $$\chi_{\Delta}(\alpha) = \sum_{\pi\in\Pi({\Delta})} \mu(\hat0,\pi) \prod_{B\in\pi} \beta_{|B|}.$$

To derive Equation we set $\alpha_j = \binom{k}{j}$. It is easy to see that the left-hand side of the theorem equals ${\chi^{\mathrm{set}}}_{\Delta}(k)$.

The method of proof is the standard one by Möbius inversion. For $\pi\in\Pi({\Delta})$ define $$g(\pi) = \sum_f \prod_1^n \alpha_{f(i)},$$ summed over functions $f: V \to {\mathbb{N}}$ that are constant on blocks of $\pi$, and $$h(\pi) = \sum_f \prod_1^n \alpha_{f(i)},$$ summed over every such function whose values differ on blocks $B, B' \in \pi$ that are joined by one or more edges. It is clear that $$g(\pi') = \sum_{\pi\geq\pi'} h(\pi)$$ for every $\pi'\in \Pi({\Delta})$, $\pi$ also ranging in $\Pi({\Delta})$. By Möbius inversion, $${\label{E:mu}{}}
h(\pi') = \sum_{\pi\geq\pi'} \mu(\pi',\pi) g(\pi).$$ Set $\pi' = \hat0$ and observe that $h(\hat0) = \chi_{\Delta}(\alpha)$.

To complete the proof we need a direct calculation of $g(\pi)$. We may choose $f_B \in {\mathbb{N}}$ for each block of $\pi$ and define $f(i)=f_B$ for every $i\in B$; then $$g(\pi) = \prod_{B\in\pi} \sum_{j=0}^\infty \alpha_j^{|B|} = \prod_{B\in\pi} \beta_{|B|}.$$ Combining with Equation , we have the theorem.

As with our original balls-into-urns problem, there is a combinatorial special case where we color ${\Delta}$ from a set ${\mathcal{S}}$ with a partition $\pi$, so that no two adjacent vertices have equivalent colors. We call this *coloring from a partitioned set* and denote the number of ways to do it by $\chi_{\Delta}(\pi)$.

  ----- ----- --- --- ---- ----- ------- --------- ----------- --------------- --
         $k$    0   1    2     3       4         5           6               7 
    $n$                                                                        
      0         1   1    1     1       1         1           1               1 
      1         1   2    4     8      16        32          64             128 
      2         0   2   10    44     186       772        3172           12952 
      3         0   0   12   144    1428     13080      115104          989184 
      4         0   0    0   216    6144    139800     2821464        53500944 
      5         0   0    0     0   11520    780000    41472000      1870310400 
      6         0   0    0     0       0   1800000   293544000     37139820480 
      7         0   0    0     0       0         0   816480000    325275955200 
      8         0   0    0     0       0         0           0   1067311728000 
      9         0   0    0     0       0         0           0               0 
  ----- ----- --- --- ---- ----- ------- --------- ----------- --------------- --

  : Values of ${\chi^{\mathrm{set}}}_n(k)$ for small $n$ and $k$.

[\[Tb:urns\]]{}

Examples {#examples .unnumbered}
--------

The table shows some low values of ${\chi^{\mathrm{set}}}_n(k)$, and the list below has formulas for special cases. We also calculate two graphical set-chromatic functions. A trivial one is ${\chi^{\mathrm{set}}}_{\Delta}(k)$ for $\bar K_n$, the graph with no edges, since ${\chi^{\mathrm{set}}}_{\Delta}$ is multiplicative over connected components, and it is not hard (if tedious) to do graphs of order at most $3$, such as the $3$-vertex path $P_3$. Here are some examples: $$\begin{aligned}
{\chi^{\mathrm{set}}}_0(k) &= 1, \\
{\chi^{\mathrm{set}}}_1(k) &= 2^k, \\
{\chi^{\mathrm{set}}}_2(k) &= 2^{2k} - \binom{2k}{k}, \\
{\chi^{\mathrm{set}}}_3(k) &= 2^{3k} - 3\cdot2^k\binom{2k}{k} + 2\cdot{\mathrm{Fr}}(k,3) , \\
{\chi^{\mathrm{set}}}_n(k) &= 0 \text{ when } k < n-1, \\
{\chi^{\mathrm{set}}}_n(n-1) &= n! \, \binom n0 \binom n1 \cdots \binom nn , \\
{\chi^{\mathrm{set}}}_{P_3}(k) &= 2^{3k} - 2\cdot2^k\binom{2k}{k} + {\mathrm{Fr}}(k,3), \\
{\chi^{\mathrm{set}}}_{\bar K_n}(k) &= 2^{nk}.\end{aligned}$$ The table entries for $n>3$ were obtained from the preceding formulas and, with the help of Maple, from the generating function .

The table shows that the values of ${\chi^{\mathrm{set}}}_2(k)$ match the number of rooted, $k$-edge plane maps with two faces [@OEIS Sequence A068551]. The two sequences have the same formula. It would be interesting to find a bijection. A casual search of [@OEIS] did not reveal any other known sequences in the table that were not obvious.

Gain graphs {#gain-graphs .unnumbered}
-----------

Set coloring began with an idea about gain graph coloring when the gains are permutations of a finite set.

Take a graph ${\Gamma}$, which may have loops and parallel edges, and assign to each oriented edge $e_{ij}$ an element ${\varphi}(e_{ij})$ of the symmetric group ${\mathfrak S}_k$ acting on $[k]$, in such a way that reorienting the edge to the reverse direction inverts the group element; symbolically, ${\varphi}(e_{ji}) = {\varphi}(e_{ij}){^{-1}}$. We call ${\varphi}$ a *gain function* on ${\Gamma}$, and $({\Gamma},{\varphi})$ is a *permutation gain graph* with ${\mathfrak S}_k$ as its *gain group*. A *proper set coloring* of $({\Gamma},{\varphi})$ is an assignment of a subset $S_i \subseteq [k]$ to each vertex $i$ so that for every oriented edge $e_{ij}$, $S_j \neq S_i {\varphi}(e_{ij})$. One way to form a permutation gain graph is to begin with a simple graph ${\Delta}$ on vertex set $[n]$ and replace each edge ${ij}$ by $k!$ edges $(g,{ij})$, each labelled by a different element $g$ of the gain group ${\mathfrak S}_k$. (Then the notations $(g,{ij})$ and $(g{^{-1}},{ji})$ denote the same edge.) We call this the *${\mathfrak S}_k$-expansion* of ${\Delta}$ and write it ${\mathfrak S}_k{\Delta}$. Now a proper set coloring of ${\mathfrak S}_k{\Delta}$ is precisely a proper set coloring of ${\Delta}$ as we first defined it: an assignment to each vertex of a subset of $[k]$ so that no two adjacent vertices have sets of the same size. Thus I came to think of set-coloring a graph.

Our calculations show that the number of proper set colorings of a graph ${\Delta}$, or equivalently of its ${\mathfrak S}_k$-expansion, is exponential in $k$. There is a standard notion of coloring of a gain graph with gain group ${\mathfrak G}$, in which the colors belong to a group ${\mathfrak H}={\mathfrak G}\times{\mathbb{Z}}_k$ and there is a chromatic function, a polynomial in $|{\mathfrak H}|$, that generalizes the chromatic polynomial of an ordinary graph and has many of the same properties, in particular satisfying the deletion-contraction law $\chi_\Phi(y) = \chi_{\Phi\setminus e}(y) - \chi_{\Phi/e}(y)$ for nonloops $e$ [@BG3]. The set-coloring function ${\chi^{\mathrm{set}}}_{\Delta}(k)$ is not a polynomial in $k$, of course, but also is not a polynomial function of $k! = |{\mathfrak S}_k|$ (see the small examples) and does not obey deletion-contraction for nonloops, not even with coefficients depending on $k$, as I found by computations with very small graphs. A calculation with ${\Delta}= K_3$ convinced me the set-coloring function cannot obey deletion-contraction even if restricted to edges that are neither loops nor isthmi; but a second example would have to be computed to get a firm conclusion. However, going to gain graphs changes the picture: then there is a simple deletion-contraction law. This indicates that the natural domain for studying set coloring and coloring from a partition is that of gain graphs. I will develop this thought elsewhere.

[9]{}

J. N. Darroch, On the distribution of the number of successes in independent trials. *Ann. Math. Stat.* 35 (1964), 1317–1321.

N. J. A. Sloane, *The On-Line Encyclopedia of Integer Sequences*. World-Wide Web URL http://www.research.att.com/njas/sequences/

Eric W. Weisstein, Binomial sums. *MathWorld—A Wolfram Web Resource*. World-Wide Web URL http://mathworld.wolfram.com/BinomialSums.html Thomas Zaslavsky, Biased graphs. III.  Chromatic and dichromatic invariants. *J. Combin. Theory Ser. B* [**64**]{} (1995), 17–88.

[^1]: I thank Herb Wilf for telling me of Darroch’s theorem and reminding me about logarithmic concavity.
