A Recurrence for Counting Graphical Partitions

Tiffany M. Barnes ^{∗} Carla D. Savage ^{†} Department of Computer Science North Carolina State University Raleigh, North Carolina 27695-8206

Submitted: February 2, 1995; Accepted May 18, 1995.

Abstract In this paper, we give a recurrence to enumerate the set G(n) of partitions of a positive even integer n which are the degree sequences of simple graphs. The recurrence gives rise to an algorithm to compute the number of elements of G(n) in time O(n^{4}) using space O(n^{3}). This appears to be the first method for computing |G(n)| in time bounded by a polynomial in n, and it has enabled us to tabulate |G(n)| for even n ≤ 220.

1 Introduction

A partition of a positive integer n is a sequence of positive integers (π_{1}, π_{2}, …, π_{l}) satisfying π_{1} ≥ π_{2} ≥ … ≥ π_{l} and π_{1} + π_{2} + … + π_{l} = n. Let P (n) denote the set of all partitions of n. P (0) contains only the empty partition, λ. A partition π ∈ P (n) is graphical if it is the degree sequence of some simple undirected graph. For example, (5, 4, 4, 3, 3, 1) is the degree sequence of the graph in Figure 1(a), but (5, 4, 4, 2, 2, 1) is not graphical. Clearly, graphical partitions exist only when n is even, since the sum of the degrees of the vertices of a graph is equal to twice the number of edges. Let G(n) denote the set of graphical partitions of n. For convenience, we will call the empty partition graphical, so that |G(0)| = 1.

Several necessary and sufficient conditions to determine whether an integer sequence is graphical are surveyed in [SH]. Perhaps the best known is the following condition due to Erdös and Gallai [EG]:

∗Research supported by the National Science Foundation through the CRA Distributed Mentor Project, 1994

†Research supported in part by National Science Foundation Grant No. CCR8906500 and DIMACS

[figure] [figure] [figure]

(a) (b)

Figure 1: (a) A graph with degree sequence π = (5, 4, 4, 3, 3, 1) and (b) the Ferrars graph of π.

[Erdös - Gallai] A positive integer sequence (π_{1}, π_{2}, …, π_{l}), with π_{1} ≥ π_{2} ≥ … ≥ π_{l}, is graphical if and only if π_{1} + π_{2} + … + π_{l} is even and for 1 ≤ j ≤ l,

∑_{i=1}^{j} π_{i} ≤ j(j − 1) + ∑_{i=j+1}^{l} min{j, π_{i}}.

In Section 2, we use a lesser-known condition to devise a recurrence to enumerate G(n). As shown in Section 3, it can be used to count G(n) in time O(n^{4}) using space O(n^{3}).

Our work was motivated by the following question, originally posed by Herbert Wilf, which remains open:

[Question] What fraction of the elements of P (n) are graphic? In particular, does the ratio |G(n)|/|P (n)| approach 0 as n approaches infinity?

To even plot the ratio |G(n)|/|P (n)|, it is necessary to compute |G(n)|, which, in our initial attempts, became a computational burden well before n = 100. Using an earlier version of the recurrence, we were able to compute |G(n)| up to n = 220. These results are tabulated in Section 4. Where sufficient memory is available, computing |G(n)| up to n = 1000 should be feasible.

For a related counting problem, we note that Stanley [St] has obtained a generating function for f(n), the number of sequences (x_{1}, x_{2}, …, x_{n}) which are degree sequences of simple graphs with vertex set {v_{1}, v_{2}, …, v_{n}}. Here, x_{i} is the degree of vertex v_{i} and the degree sequence is not necessarily nonincreasing.

2 The Recurrence

For a partition π = (π_{1}, …, π_{l}), the associated Ferrars graph is an array of l rows of dots, where row i has π_{i} dots and rows are left justified (Figure 1(b).) Let π′ denote the conjugate partition π′ = (π′_{1}, …, π′_{m}) where m = π_{1} and π′_{i} is the number of dots in the i-th column of the Ferrars graph of π. The Durfee square of π is the largest square subarray of dots in the Ferrars graph of π. Let d(π) denote the size (number of rows) of the Durfee square of π. The sequence

(π_{1} − π′_{1}, π_{2} − π′_{2}, …, π_{d(π)} − π′_{d(π)})

is the sequence of successive ranks of π [At]. It will be convenient to work with the negatives of the ranks, so, for 1 ≤ i ≤ d(π), let r_{i}(π) = π′_{i}−π_{i}. We call (r_{1}(π), … r_{d(π)}(π)) the sequence of successive antiranks of π.

The necessary and sufficient condition below, attributed to Nash-Williams, is proved in [RA2] and [SH].

[Nash-Williams] A partition π of an even integer is graphical if and only if for 1 ≤ j ≤ d(π),

∑_{i=1}^{j} r_{i}(π) ≥ j.

(This condition is called the Hässelbarth Criterion by the authors of [SH] since they first saw it in [Has], where it appeared without proof.) It can be shown that for 1 ≤ j ≤ d(π), the j-th Nash-Williams condition is equivalent to the j-th Erdös-Gallai condition. Furthermore, if conditions 1, 2, …, d(π) of Erdös-Gallai are satisfied, then so are the remaining Erdös-Gallai conditions [RA2].

Let P (n, k, l) be the set of partitions of n into at most l parts with largest part at most k and define G(n, k, l) to be the set of graphical partitions in P (n, k, l). Let π ∈ P (n, k, l) and let α be obtained from π by deleting the first row and column of the Ferrars graph of π. Then d(α) = d(π) − 1. Let s = r_{1}(π) = π′_{1} − π_{1}. By the Nash-Williams condition, π is graphical if and only if s > 0 and for 1 ≤ j ≤ d(α), the antiranks of α satisfy an s-variant of the Nash-Williams conditions:

s + ∑_{i=1}^{j} r_{i}(α) ≥ j.

the electronic journal of combinatorics 2 (1995), #R11 4 With this in mind, define P (n, k, l, s) for s ≥ 0 by

P (n, k, l, s) = { π ∈ P (n, k, l) | s + ∑_{i=1}^{j} r_{i}(π) ≥ j for 1 ≤ j ≤ d(π)}.

Let P (n, k, l, s) = ∅ if s < 0 and note that for s ≥ 0, P (n, k, l, s) = {λ} if P (n, k, l) = {λ}.

Lemma 1 below is a restatement of the Nash-Williams condition and Lemma 2 follows since G(n) = G(n, n, n). Lemma 1 For even n ≥ 0, G(n, k, l) = P (n, k, l, 0). Lemma 2 For even n ≥ 0, G(n) = P (n, n, n, 0).

Thus, we can compute |G(n)| by computing |P (n, k, l, s)| for appropriate values of the arguments. To this end, let P′(n, k, l) and P′(n, k, l, s), be the subsets of P (n, k, l) and P (n, k, l, s), respectively, consisting of those partitions into exactly l parts with largest part of size exactly k. Lemma 3 For n > 0 and 1 ≤ k, l, s ≤ n, |P (n, k, l, s)| − |P′(n, k, l, s)| = |P (n, k−1, l, s)| + |P (n, k, l−1, s)| − |P (n, k−1, l−1, s)|. Proof. ¿From the definitions of P and P′ we have

P (n, k, l, s) \ P′(n, k, l, s) = P (n, k − 1, l, s) ∪ P (n, k, l − 1, s).

The set on the left-hand side of this equality has size

|P (n, k, l, s)| − |P′(n, k, l, s)|

and by inclusion-exclusion, the set on the right-hand side of the equality has size

|P (n, k − 1, l, s)| + |P (n, k, l − 1, s)| − |P (n, k − 1, l, s) ∩ P (n, k, l − 1, s)|. The result follows since the intersection in the last term is P (n, k − 1, l − 1, s). □ Lemma 4 Assume n > 0, 1 ≤ k, l, ≤ n, and s ≥ 0. Then

|P′(n, k, l, s)| = |P (n − k − l + 1, k − 1, l − 1, s + l − k − 1)|.

Proof. Define a function f on P′(n, k, l) by f(π) = α, where α is obtained from π by deleting the first row and column in the Ferrars graph of π. Given the assumptions of the theorem, if P′(n, k, l) = ∅ then either (1) n < k + l − 1, in which case n − k − l + 1 < 0 or (2) n > kl, which implies n − k − l + 1 > kl − k − l + 1 = (k − 1)(l − 1). In either of these cases, P (n − k − l + 1, k − 1, l − 1) = ∅. If P′(n, k, l) contains only the partition (k, 1, …, 1), then f((k, 1, …, 1)) = λ, n − k − l + 1 = 0, and P (n − k − l + 1, k − 1, l − 1) = {λ}. Otherwise, d(α) = d(π) − 1 and α = (α_{1}, … α_{m}) where m = π′_{2} − 1, α_{i} = π_{i+1} − 1 for 1 ≤ i ≤ m and α′_{i} = π′_{i+1} − 1 for 1 ≤ i ≤ d(π) − 1. Clearly, f is a bijection between P′(n, k, l) and P (n − k − l + 1, k − 1, l − 1) Furthermore, for 1 ≤ j ≤ d(π),

s + ∑_{i=1}^{j}(π′_{i} − π_{i}) = (s + l − k) + ∑_{i=2}^{j}(π′_{i} − π_{i})
= (s + l − k) + ∑_{i=2}^{j}((π′_{i} − 1) − (π_{i} − 1))
= (s + l − k) + ∑_{i=1}^{j−1}(α′_{i} − α_{i}).

Thus

s + ∑_{i=1}^{j} r_{i}(π) ≥ j ⟺

(s + l − k − 1) + ∑_{i=1}^{j−1} r_{i}(α) ≥ j − 1.

This establishes that π ∈ P′(n, k, l, s) ⟺ α ∈ P (n−k −l+1, k −1, l−1, s+l−k −1). □

Lemma 5 P (n, k, l) = P (n, k, l, n) = P (n, k, l, s) for s ≥ n.

Proof. Note that for any π ∈ P (n, k, l) and 1 ≤ j ≤ π(d),

∑_{i=1}^{j}(π′_{i} − π_{i} − 1) ≥ ∑_{i=1}^{j} −π_{i} ≥ −n.

Thus, π ∈ P (n, k, l, n), which means P (n, k, l) ⊆ P (n, k, l, n). By definition, for t′ ≥ t ≥ 0, P (n, k, l, t) ⊆ P (n, k, l, t′), thus for any s ≥ n, P (n, k, l, n) ⊆ P (n, k, l, s). The result follows since P (n, k, l, s) ⊆ P (n, k, l). □

The resulting recurrence for counting |P (n, k, l, s)| is given in the following.

Theorem 1 |P (n, k, l, s)| is defined by:

|P (n, k, l, s)| =

if ((n < 0) or (k < 0) or (l < 0) or (s < 0))  then :  0  (1)
else if n = 0  then:  1  (2)
else if (k = 0) or (l = 0)  then:  0  (3)
else if (k > n)  then:  |P (n, n, l, s)|  (4)
else if (l > n)  then:  |P (n, k, n, s)|  (5)
else if (s > n)  then:  |P (n, k, l, n)|  (6)

else: |P (n, k − 1, l, s)| + |P (n, k, l − 1, s)| − |P (n, k − 1, l − 1, s)| (7)

+|P (n − k − l + 1, k − 1, l − 1, s + l − k − 1)|

Proof. P (n, k, l, s) was defined to be empty when s < 0. For the remaining conditions in (1) through (5) the value of |P (n, k, l, s)| is clear. Condition (6) follows from Lemma 5. For the general case (7), equate |P′(n, k, l, s)| in Lemmas 3 and 4 and then solve for |P (n, k, l, s)|. □

3 The Algorithm

The recurrence of Theorem 1 for computing |P (n, k, l, s)| has a straightforward implementation as a dynamic programming algorithm which fills a 4-dimensional table of entries T [a, b, c, d] = |P (a, b, c, d)| where 0 ≤ a ≤ n, 0 ≤ b ≤ k, 0 ≤ c ≤ l, and 0 ≤ d ≤ n. The table is filled in any order which guarantees that when the time comes to fill entry T [n′, k′, l′, s′], the required entries T [n′, k′ − 1, l′, s′], T [n′, k′, l′ − 1, s′], T [n′, k′ − 1, l′ − 1, s′], and T [n′ − k′ − l′ + 1, k′ − 1, l′ − 1, s′ + l′ − k′ − 1] have already been filled and can be read from the table. The table uses space O(n^{2}kl) and only constant time is required to fill in each entry. In particular, computing |G(n)| = |P (n, n, n, 0)| takes time and space O(n^{4}).

The space can be asymptotically improved as follows. For 0 ≤ c ≤ l, let T_{c} be the 3-dimensional table of entries T_{c}[a, b, d] = |P (a, b, c, d)| for 0 ≤ a ≤ n, 0 ≤ b ≤ k, and 0 ≤ d ≤ n. Then |P (n, k, l, s)| can be computed by computing successively the tables T_{0}, T_{1}, … T_{l}. Note from the recurrence of Theorem 1 that computing entries in table T_{c} requires access only to values in table T_{c} or table T_{c−1}. Thus, in computing |P (n, k, l, s)|, no more than two 3-dimensional tables need to be stored at any given time, reducing the space required to O(n^{2}k). Thus, computing |G(n)| can be done in O(n^{4}) time with O(n^{3}) space.

4 Concluding Remarks

Even with this polynomial time algorithm, computing |G(n)| for n > 200 quickly becomes impractical because of the huge space requirements. An additional burden on space is that |G(n)| gets large quickly so that some method must be used to manipulate and allocate enough storage for these large numbers. The following strategy was suggested by the referee: Select small primes p_{1} < p_{2} < … < p_{s} so that p_{1}p_{2} … p_{s} > G(n). For i = 1, …, s, use the recurrence of Theorem 1 to compute G_{i}(n) = G(n) mod (p_{i}). Then by the Chinese Remainder Theorem, G(n) can be recovered from G_{1}(n), …, G_{s}(n). If, for example, the primes can be represented with 8 bits, time O(n^{4}) will be spent computing each of s tables, but the 3-dimensional tables now need store only 8-bit integers.

For those interested in the values |G(n)|, or in the ratio |G(n)|/|P (n)| from the open question of Section 1, we include Tables 1 and 2. To the best of our knowledge, the values had previously been computed only through n = 40, as noted in [ER] in an acknowledgement to Ron Read. ¿From the data, it seems reasonable to make the conjecture that for even n ≥ 18, |G(n)|/|P (n)| is monotone decreasing, but we are not aware of any proof of this. The best results known at this time are that

\overline{lim}_{n→∞} \frac{\sqrt{n} |G(n)|}{|P (n)|} ≥ \frac{π}{\sqrt{6}}

(so the ratio cannot go to 0 faster than 1/\sqrt{n} [ER]) and that [RA1]

\overline{lim}_{n→∞} \frac{|G(n)|}{|P (n)|} ≤ .25.

Acknowledgements: Thanks to Steve Skiena for bringing this problem to our attention, to Frank Ruskey for pointing out references [SH] and [St], and to Bruce Richmond and Cecil Rousseau for sharing their work with us. A special thanks to Herbert Wilf for his help in simplifying a earlier version of our recurrence which involved a double summation. This led to asymptotic improvements in both the time and space required. We are also grateful to the referees for their insightful comments and helpful suggestions. the electronic journal of combinatorics 2 (1995), #R11 8

\begin{matrix}n & |G(n)| & |P (n)| & |G(n)|/|P (n)| \\ 2 & 1 & 2 & 0.500000 \\ 4 & 2 & 5 & 0.400000 \\ 6 & 5 & 11 & 0.454545 \\ 8 & 9 & 22 & 0.409091 \\ 10 & 17 & 42 & 0.404762 \\ 12 & 31 & 77 & 0.402597 \\ 14 & 54 & 135 & 0.400000 \\ 16 & 90 & 231 & 0.389610 \\ 18 & 151 & 385 & 0.392208 \\ 20 & 244 & 627 & 0.389155 \\ 22 & 387 & 1002 & 0.386228 \\ 24 & 607 & 1575 & 0.385397 \\ 26 & 933 & 2436 & 0.383005 \\ 28 & 1420 & 3718 & 0.381926 \\ 30 & 2136 & 5604 & 0.381156 \\ 32 & 3173 & 8349 & 0.380046 \\ 34 & 4657 & 12310 & 0.378310 \\ 36 & 6799 & 17977 & 0.378205 \\ 38 & 9803 & 26015 & 0.376821 \\ 40 & 14048 & 37338 & 0.376239 \\ 42 & 19956 & 53174 & 0.375296 \\ 44 & 28179 & 75175 & 0.374845 \\ 46 & 39467 & 105558 & 0.373889 \\ 48 & 54996 & 147273 & 0.373429 \\ 50 & 76104 & 204226 & 0.372646 \\ 52 & 104802 & 281589 & 0.372181 \\ 54 & 143481 & 386155 & 0.371563 \\ 56 & 195485 & 526823 & 0.371064 \\ 58 & 264941 & 715220 & 0.370433 \\ 60 & 357635 & 966467 & 0.370044 \\ 62 & 480408 & 1300156 & 0.369500 \\ 64 & 642723 & 1741630 & 0.369035 \\ 66 & 856398 & 2323520 & 0.368578 \\ 68 & 1136715 & 3087735 & 0.368139 \\ 70 & 1503172 & 4087968 & 0.367706 \\ 72 & 1980785 & 5392783 & 0.367303 \\ 74 & 2601057 & 7089500 & 0.366889 \\ 76 & 3404301 & 9289091 & 0.366484 \\ 78 & 4441779 & 12132164 & 0.366116 \\ 80 & 5777292 & 15796476 & 0.365733 \\ 82 & 7492373 & 20506255 & 0.365370 \\ 84 & 9688780 & 26543660 & 0.365013 \\ 86 & 12494653 & 34262962 & 0.364669 \\ 88 & 16069159 & 44108109 & 0.364313 \\ 90 & 20614755 & 56634173 & 0.363999 \\ 92 & 26377657 & 72533807 & 0.363660 \\ 94 & 33671320 & 92669720 & 0.363348 \\ 96 & 42878858 & 118114304 & 0.363028 \\ 98 & 54481054 & 150198136 & 0.362728 \\ 100 & 69065657 & 190569292 & 0.362418 \\ 102 & 87370195 & 241265379 & 0.362133 \\ 104 & 110287904 & 304801365 & 0.361835 \\ 106 & 138937246 & 384276336 & 0.361556 \\ 108 & 174675809 & 483502844 & 0.361272 \\ 110 & 219186741 & 607163746 & 0.361001 \end{matrix}

Table 1: Sizes of G(n) and P (n) and their ratio for 2 ≤ n ≤ 110. the electronic journal of combinatorics 2 (1995), #R11 9

\begin{matrix}n & |G(n)| & |P (n)| & |G(n)|/|P (n)| \\ 112 & 274512656 & 761002156 & 0.360725 \\ 114 & 343181668 & 952050665 & 0.360466 \\ 116 & 428244215 & 1188908248 & 0.360200 \\ 118 & 533464959 & 1482074143 & 0.359945 \\ 120 & 663394137 & 1844349560 & 0.359690 \\ 122 & 823598382 & 2291320912 & 0.359443 \\ 124 & 1020807584 & 2841940500 & 0.359194 \\ 126 & 1263243192 & 3519222692 & 0.358955 \\ 128 & 1560795436 & 4351078600 & 0.358715 \\ 130 & 1925513465 & 5371315400 & 0.358481 \\ 132 & 2371901882 & 6620830889 & 0.358248 \\ 134 & 2917523822 & 8149040695 & 0.358021 \\ 136 & 3583515700 & 10015581680 & 0.357794 \\ 138 & 4395408234 & 12292341831 & 0.357573 \\ 140 & 5383833857 & 15065878135 & 0.357353 \\ 142 & 6585699894 & 18440293320 & 0.357136 \\ 144 & 8045274746 & 22540654445 & 0.356923 \\ 146 & 9815656018 & 27517052599 & 0.356711 \\ 148 & 11960467332 & 33549419497 & 0.356503 \\ 150 & 14555902348 & 40853235313 & 0.356297 \\ 152 & 17692990183 & 49686288421 & 0.356094 \\ 154 & 21480510518 & 60356673280 & 0.355893 \\ 156 & 26048320019 & 73232243759 & 0.355695 \\ 158 & 31551087790 & 88751778802 & 0.355498 \\ 160 & 38173235010 & 107438159466 & 0.355304 \\ 162 & 46134037871 & 129913904637 & 0.355112 \\ 164 & 55694314567 & 156919475295 & 0.354923 \\ 166 & 67163674478 & 189334822579 & 0.354735 \\ 168 & 80909973315 & 228204732751 & 0.354550 \\ 170 & 97368672089 & 274768617130 & 0.354366 \\ 172 & 117056456152 & 330495499613 & 0.354185 \\ 174 & 140584220188 & 397125074750 & 0.354005 \\ 176 & 168675124141 & 476715857290 & 0.353827 \\ 178 & 202182888436 & 571701605655 & 0.353651 \\ 180 & 242116891036 & 684957390936 & 0.353477 \\ 182 & 289666252014 & 819876908323 & 0.353305 \\ 184 & 346234896845 & 980462880430 & 0.353134 \\ 186 & 413474657328 & 1171432692373 & 0.352965 \\ 188 & 493331835384 & 1398341745571 & 0.352700 \\ 190 & 588093594457 & 1667727404093 & 0.352632 \\ 192 & 700451190712 & 1987276856363 & 0.352468 \\ 194 & 833561537987 & 2366022741845 & 0.352305 \\ 196 & 991134281267 & 2814570987591 & 0.352144 \\ 198 & 1177516049387 & 3345365983698 & 0.351984 \\ 200 & 1397805210533 & 3972999029388 & 0.351826 \\ 202 & 1657968320899 & 4714566886083 & 0.351669 \\ 204 & 1964994991232 & 5590088317495 & 0.351514 \\ 206 & 2327052859551 & 6622987708040 & 0.351360 \\ 208 & 2753697110356 & 7840656226137 & 0.351207 \\ 210 & 3256081386335 & 9275102575355 & 0.351056 \\ 212 & 3847232865612 & 10963707205259 & 0.350757 \\ 214 & 4542341563460 & 12950095925895 & 0.350757 \\ 216 & 5359127512113 & 15285151248481 & 0.350610 \\ 218 & 6318223879596 & 18028182516671 & 0.350464 \\ 220 & 7443670977177 & 21248279009367 & 0.350319 \end{matrix}

Table 2: Sizes of G(n) and P (n) and their ratio for 112 ≤ n ≤ 220.

References

[At] A. O. L. Atkin, “A note on ranks and conjugacy of partitions,” Quart. J. Math., Oxford Ser. (2)17 (1966) 335-338.

[EG] P. Erdös and T. Gallai, “Graphs with given degree of vertices,” Mat. Lapok 11 (1960) 264-274.

[ER] P. Erdös and L. B. Richmond, “On graphical partitions,” Combinatorica 13 (1993) 57-63.

[Has] W. Hässelbarth, “Die Verzweigtheit von Graphen”, Match. 16 (1984) 3-17.

[RA1] C. C. Rousseau and F. Ali, “On a conjecture concerning graphical partitions,” preprint, April 1994.

[RA2] C. C. Rousseau and F. Ali, “A note on graphical partitions,” preprint, April 1994.

[SH] G. Sierksma and H. Hoogeveen, “Seven criteria for integer sequences being graphic,” Journal of Graph Theory 15, No. 2 (1991) 223-231.

[St] R. P. Stanley, “A zonotope associated with graphical degree sequences,” in Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift, P. Gritznann and B. Sturmfels, eds., ACM, AMS (1991).