% A LaTeX file for a 10 page document % This is the final version - to appear in El. J. C. \documentstyle[11pt]{article} \textwidth 6.0in \textheight 8.0in \oddsidemargin 0.25in \topmargin 0.0in \pagestyle{myheadings} \markright{\sc the electronic journal of combinatorics 2 (1995), \#R11\hfill} \thispagestyle{empty} \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \newtheorem{corollary}{Corollary} \newtheorem{definition}{Definition} \title {A Recurrence for Counting Graphical Partitions } \author{ Tiffany M. Barnes \thanks{ Research supported by the National Science Foundation through the CRA Distributed Mentor Project, 1994}\\ Carla D. Savage \thanks{Research supported in part by National Science Foundation Grant No. CCR8906500 and DIMACS} \\ {\em Department of Computer Science}\\ {\em North Carolina State University}\\ {\em Raleigh, North Carolina 27695-8206}\\ \\ Submitted: February 2, 1995; Accepted May 18, 1995.\\ } \date{} \begin{document} \maketitle \baselineskip 18pt \begin{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 \leq 220$. %We have also tablulated the ratio |G(n)|/|P(n)| in this range, where %$P(n)$ is the set of all partitions of $n$. It is an open question %whether this ratio goes to zero. \end{abstract} \section{Introduction} A {\em partition} of a positive integer $n$ is a sequence of positive integers $(\pi_1, \pi_2, \ldots, \pi_l)$ satisfying $\pi_1 \geq \pi_2 \geq \ldots \geq \pi_l$ and $\pi_1 + \pi_2 + \ldots + \pi_l =n$. Let $P(n)$ denote the set of all partitions of $n$. $P(0)$ contains only the empty partition, $\lambda$. A partition $\pi \in P(n)$ is {\em 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\"{o}s and Gallai [EG]: \vspace{.2in} \noindent {\bf [Erd\"{o}s - Gallai]} A positive integer sequence $(\pi_1, \pi_2, \ldots , \pi_l)$, with $\pi_1 \geq \pi_2 \geq \ldots \geq \pi_l$, is graphical if and only if $\pi_1 + \pi_2 + \ldots + \pi_l $ is even and for $1 \leq j \leq l$, \[ \sum_{i=1}^{j}\pi_i \ \leq \ j(j-1) + \sum_{i=j+1}^{l}\min\{j,\pi_i\}. \] \vspace{.1in} \noindent 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: \vspace{.2in} \noindent {\bf [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? \vspace{.2in} \begin{figure} \setlength{\unitlength}{0.012500in}% % \begingroup\makeatletter\ifx\SetFigFont\undefined % extract first six characters in \fmtname \def\x#1#2#3#4#5#6#7\relax{\def\x{#1#2#3#4#5#6}}% \expandafter\x\fmtname xxxxxx\relax \def\y{splain}% \ifx\x\y % LaTeX or SliTeX? \gdef\SetFigFont#1#2#3{% \ifnum #1<17\tiny\else \ifnum #1<20\small\else \ifnum #1<24\normalsize\else \ifnum #1<29\large\else \ifnum #1<34\Large\else \ifnum #1<41\LARGE\else \huge\fi\fi\fi\fi\fi\fi \csname #3\endcsname}% \else \gdef\SetFigFont#1#2#3{\begingroup \count@#1\relax \ifnum 25<\count@\count@25\fi \def\x{\endgroup\@setsize\SetFigFont{#2pt}}% \expandafter\x \csname \romannumeral\the\count@ pt\expandafter\endcsname \csname @\romannumeral\the\count@ pt\endcsname \csname #3\endcsname}% \fi \fi\endgroup \begin{picture}(410,145)(115,640) \thinlines \put(180,780){\circle*{10}} \put(180,740){\circle*{10}} \put(180,700){\circle*{10}} \put(160,700){\circle*{10}} \put(120,680){\circle*{10}} \put(240,680){\circle*{10}} \put(360,780){\circle*{10}} \put(400,780){\circle*{10}} \put(440,780){\circle*{10}} \put(480,780){\circle*{10}} \put(520,780){\circle*{10}} \put(360,760){\circle*{10}} \put(400,760){\circle*{10}} \put(440,760){\circle*{10}} \put(480,760){\circle*{10}} \put(360,740){\circle*{10}} \put(400,740){\circle*{10}} \put(440,740){\circle*{10}} \put(480,740){\circle*{10}} \put(360,720){\circle*{10}} \put(400,720){\circle*{10}} \put(440,720){\circle*{10}} \put(360,700){\circle*{10}} \put(400,700){\circle*{10}} \put(440,700){\circle*{10}} \put(360,680){\circle*{10}} \special{ps: gsave 0 0 0 setrgbcolor}\put(180,780){\line(-2,-3){ 66.154}} \put(115,680){\line( 1, 0){125}} \put(240,680){\line(-3, 5){ 60}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(180,780){\line( 0,-1){ 40}} \put(180,740){\line( 0,-1){ 40}} \put(180,700){\line( 3,-1){ 60}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(180,695){\line(-4,-1){ 64.706}} \put(115,680){\line( 1, 0){ 5}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(180,740){\line(-3,-5){ 24.265}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(180,740){\line( 1,-1){ 60}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(180,740){\line(-1,-1){ 60}} \special{ps: grestore}\put(165,640){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{rm}\special{ps: gsave 0 0 0 setrgbcolor}(a)\special{ps: grestore}}}} \put(430,640){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{rm}\special{ps: gsave 0 0 0 setrgbcolor}(b)\special{ps: grestore}}}} \end{picture} \vspace{.2in} \caption{ (a) A graph with degree sequence $\pi = (5,4,4,3,3,1)$ and (b) the Ferrars graph of $\pi$.} \end{figure} 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, \ldots, x_n)$ which are degree sequences of simple graphs with vertex set $\{v_1,v_2,\ldots, v_n\}$. Here, $x_i$ is the degree of vertex $v_i$ and the degree sequence is not necessarily nonincreasing. \section{The Recurrence} For a partition $\pi = (\pi_1, \ldots , \pi_l)$, the associated {\em Ferrars graph} is an array of $l$ rows of dots, where row $i$ has $\pi_i$ dots and rows are left justified (Figure 1(b).) Let $\pi'$ denote the conjugate partition $\pi' = (\pi'_1, \ldots , \pi'_m)$ where $m=\pi_1$ and $\pi'_i$ is the number of dots in the $i$-th column of the Ferrars graph of $\pi$. The {\em Durfee square} of $\pi$ is the largest square subarray of dots in the Ferrars graph of $\pi$. Let $d(\pi)$ denote the size (number of rows) of the Durfee square of $\pi$. The sequence \[ (\pi_1-\pi_1',\ \ \pi_2-\pi_2', \ \ldots,\ \pi_{d(\pi)} -\pi_{d(\pi)}') \] is the sequence of {\em successive ranks} of $\pi$ [At]. It will be convenient to work with the negatives of the ranks, so, for $1 \leq i \leq d(\pi)$, let $r_i(\pi) = \pi_i'-\pi_i$. We call $(r_1(\pi), \ldots r_{d(\pi)} (\pi))$ the sequence of successive {\em antiranks} of $\pi$. The necessary and sufficient condition below, attributed to Nash-Williams, is proved in [RA2] and [SH]. \vspace{.2in} \noindent {\bf [Nash-Williams]} A partition $\pi$ of an even integer is graphical if and only if for $1 \leq j \leq d(\pi)$, \[ \sum_{i=1} ^{j} r_i(\pi) \geq j. \] \vspace{.1in} \noindent (This condition is called the {\em H\"{a}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 \leq j \leq d(\pi)$, the $j$-th Nash-Williams condition is equivalent to the $j$-th Erd\"{o}s-Gallai condition. Furthermore, if conditions $1,2, \ldots, d(\pi)$ of Erd\"{o}s-Gallai are satisfied, then so are the remaining Erd\"{o}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 $\pi \in P(n,k,l)$ and let $\alpha$ be obtained from $\pi$ by deleting the first row and column of the Ferrars graph of $\pi$. Then $d(\alpha)=d(\pi)-1$. Let $s= r_1(\pi) =\pi_1'-\pi_1$. By the Nash-Williams condition, $\pi$ is graphical if and only if $s>0$ and for $1 \leq j \leq d(\alpha)$, the antiranks of $\alpha$ satisfy an $s$-variant of the Nash-Williams conditions: \[ s \ + \ \sum_{i=1} ^{j} r_i(\alpha) \geq j. \] With this in mind, define $P(n,k,l,s)$ for $s \geq 0$ by \[ P(n,k,l,s) = \{\ \pi \in P(n,k,l)\ \ |\ \ s\ +\ \sum_{i=1}^{j}r_i(\pi) \ \geq\ j \ \ \mbox{for} \ \ 1 \leq j \leq d(\pi) \}. \] Let $P(n,k,l,s) = \emptyset$ if $s<0$ and note that for $s \geq 0$, $P(n,k,l,s) = \{\lambda\}$ if $P(n,k,l) = \{\lambda\}$. Lemma 1 below is a restatement of the Nash-Williams condition and Lemma 2 follows since $G(n) =G(n,n,n)$. \begin{lemma} For even $n \geq 0$, $G(n,k,l)=P(n,k,l,0)$. \end{lemma} \begin{lemma} For even $n \geq 0$, $G(n) = P(n,n,n,0)$. \end{lemma} 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 {\em exactly} $l$ parts with largest part of size {\em exactly} $k$. \begin{lemma} For $n>0$ and $1 \leq k,l,s \leq 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)|. \] \end{lemma} \noindent {\bf Proof.} From the definitions of $P$ and $P'$ we have \[ P(n,k,l,s)\ \setminus \ P'(n,k,l,s)\ =\ P(n,k-1,l,s) \ \cup \ 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) \ \cap \ P(n,k,l-1,s)|. \] The result follows since the intersection in the last term is $P(n,k-1,l-1,s)$. $\Box$ \begin{lemma} Assume $n>0$, $1 \leq k,l, \leq n$, and $s \geq 0$. Then \[ |P'(n,k,l,s)|\ =\ |P(n-k-l+1,\ \ k-1,\ \ l-1,\ \ s+l-k-1)|. \] \end{lemma} \noindent {\bf Proof.} Define a function $f$ on $P'(n,k,l)$ by $f(\pi)= \alpha$, where $\alpha$ is obtained from $\pi$ by deleting the first row and column in the Ferrars graph of $\pi$. Given the assumptions of the theorem, if $P'(n,k,l)=\emptyset$ 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)= \emptyset$. If $P'(n,k,l)$ contains only the partition $(k,1,\ldots,1)$, then $f((k,1,\ldots, 1)) = \lambda$, $n-k-l+1 = 0$, and $P(n-k-l+1,k-1,l-1)= \{\lambda\}$. Otherwise, $d(\alpha) = d(\pi) -1$ and $\alpha = (\alpha_1, \ldots \alpha_{m})$ where $m=\pi'_2 -1$, $\alpha_i = \pi_{i+1}-1$ for $1\leq i \leq m$ and $\alpha'_i = \pi'_{i+1}-1$ for $1 \leq i \leq d(\pi)-1$. Clearly, $f$ is a bijection between $P'(n,k,l)$ and $P(n-k-l+1,\ k-1,\ l-1)$ Furthermore, for $1 \leq j \leq d(\pi)$, \begin{eqnarray*} s+ \sum_{i=1}^{j}(\pi'_i - \pi_i ) & = & (s +l-k) + \sum_{i=2}^{j}(\pi'_i - \pi_i )\\ & = & (s +l-k) + \sum_{i=2}^{j}((\pi'_i-1) - (\pi_i-1) )\\ & = & (s +l-k) + \sum_{i=1}^{j-1}(\alpha_i' - \alpha_i). \end{eqnarray*} Thus \[ s\ +\ \sum_{i=1}^{j}r_i(\pi) \ \geq \ j \Longleftrightarrow \] \[ (s + l - k - 1)\ +\ \sum_{i=1}^{j-1}r_i(\alpha) \ \geq \ j-1. \] This establishes that $\pi \in P'(n,k,l,s) \Longleftrightarrow \alpha \in P(n-k-l+1,\ k-1,\ l-1,\ s+l-k-1)$. $\Box$ \begin{lemma} $P(n,k,l)=P(n,k,l,n)=P(n,k,l,s)$ for $s \geq n$. \end{lemma} \noindent {\bf Proof.} Note that for any $\pi \in P(n,k,l)$ and $1 \leq j \leq \pi(d)$, \[ \sum_{i=1}^{j}(\pi'_i - \pi_i -1)\ \geq \ \sum_{i=1}^{j} - \pi_i \ \geq \ -n. \] Thus, $\pi \in P(n,k,l,n)$, which means $P(n,k,l) \subseteq P(n,k,l,n)$. By definition, for $t' \geq t \geq 0$, $P(n,k,l,t) \subseteq P(n,k,l,t')$, thus for any $s \geq n$, $P(n,k,l,n) \subseteq P(n,k,l,s)$. The result follows since $P(n,k,l,s) \subseteq P(n,k,l)$. $\Box$ \vspace{.2in} The resulting recurrence for counting $|P(n,k,l,s)|$ is given in the following. \begin{theorem} $|P(n,k,l,s)|$ is defined by: \begin{tabbing} xxxxx\=xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx\=xxxxxxxxxx\=xxxxxxxxxxxxxxxxxxx\= \kill $|P(n,k,l,s)| = $ \\ \> if\ $((n<0)$ or $(k<0)$ \ or \ $(l<0)$ \ or \ $(s<0))$ \> then : \> 0 \>{\em (1)} \\ \> else if\ $n=0$ \> then: \> 1 \> {\em (2)} \\ \>else if\ $(k=0)$ or $(l=0)$ \> then: \> 0 \> {\em (3)} \\ \>else if\ $(k>n)$ \> then: \> $|P(n,n,l,s)|$ \> {\em (4)}\\ \>else if\ $(l>n)$ \> then: \> $|P(n,k,n,s)|$ \> {\em (5)}\\ \>else if\ $(s>n)$ \> then: \> $|P(n,k,l,n)|$ \> {\em (6)}\\ \>else: $|P(n,k-1,l,s)| + |P(n,k,l-1,s)| - |P(n,k-1,l-1,s)|$ \>\>\> {\em (7)} \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $ + |P(n-k-l+1,\ k-1,\ l-1,\ s+l-k-1)|$ \end{tabbing} \end{theorem} \noindent {\em 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)|$. $\Box$ \section{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 \leq a \leq n$,\ $0 \leq b \leq k$,\ $0 \leq c \leq l$,\ and $0 \leq d \leq 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^2kl)$ 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 \leq c \leq l$, let $T_c$ be the 3-dimensional table of entries $T_c[a,b,d] = |P(a,b,c,d)|$ for $0 \leq a \leq n$,\ $0 \leq b \leq k$, and $0 \leq d \leq n$. Then $|P(n,k,l,s)|$ can be computed by computing successively the tables $T_0$, $T_1, \ldots 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^2k)$. Thus, computing $|G(n)|$ can be done in $O(n^4)$ time with $O(n^3)$ space. \section{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 < \ldots < p_s$ so that $p_1 p_2 \ldots p_s > G(n)$. For $i = 1, \ldots, s$, use the recurrence of Theorem 1 to compute $G_i(n) = G(n) \bmod (p_i)$. Then by the Chinese Remainder Theorem, $G(n)$ can be recovered from $G_1(n), \ldots, 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 \geq 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 \rightarrow \infty} \frac{\sqrt{n}\ |G(n)|}{|P(n)|} \ \geq \ \frac{\pi}{\sqrt{6}} \] (so the ratio cannot go to 0 faster than $1/\sqrt{n}$ [ER]) and that [RA1] \[ \overline{\lim}_{n \rightarrow \infty}\frac{|G(n)|}{|P(n)|}\ \leq \ .25. \] \bigskip \noindent {\bf 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. \begin{table} {\scriptsize \begin{tabular}{|l||l|l|l|} \hline $n$ & $|G(n)|$ & $|P(n)|$ & $|G(n)|/|P(n)|$ \\ \hline \hline 2 & 1 & 2 & 0.500000\\ \hline 4 & 2 & 5 & 0.400000\\ \hline 6 & 5 & 11 & 0.454545\\ \hline 8 & 9 & 22 & 0.409091\\ \hline 10 & 17 & 42 & 0.404762\\ \hline 12 & 31 & 77 & 0.402597\\ \hline 14 & 54 & 135 & 0.400000\\ \hline 16 & 90 & 231 & 0.389610\\ \hline 18 & 151 &385 & 0.392208\\ \hline 20 & 244 & 627 & 0.389155\\ \hline 22 & 387 & 1002 & 0.386228\\ \hline 24 & 607 & 1575 & 0.385397\\ \hline 26 & 933 & 2436 & 0.383005\\ \hline 28 & 1420 & 3718 & 0.381926\\ \hline 30 & 2136 & 5604 & 0.381156\\ \hline 32 & 3173 & 8349 & 0.380046\\ \hline 34 & 4657 & 12310 & 0.378310\\ \hline 36 & 6799 & 17977 & 0.378205\\ \hline 38 & 9803 & 26015 & 0.376821\\ \hline 40 & 14048 & 37338 & 0.376239\\ \hline 42 & 19956 & 53174 & 0.375296\\ \hline 44 & 28179 & 75175 & 0.374845\\ \hline 46 & 39467 & 105558 & 0.373889\\ \hline 48 & 54996 & 147273 & 0.373429\\ \hline 50 & 76104 & 204226 & 0.372646\\ \hline 52 & 104802 & 281589 & 0.372181\\ \hline 54 & 143481 & 386155 & 0.371563\\ \hline 56 & 195485 & 526823 & 0.371064\\ \hline 58 & 264941 & 715220 & 0.370433\\ \hline 60 & 357635 & 966467 & 0.370044\\ \hline 62 & 480408 & 1300156 & 0.369500\\ \hline 64 & 642723 & 1741630 & 0.369035\\ \hline 66 & 856398 & 2323520 & 0.368578\\ \hline 68 & 1136715 & 3087735 & 0.368139\\ \hline 70 & 1503172 & 4087968 & 0.367706\\ \hline 72 & 1980785 & 5392783 & 0.367303\\ \hline 74 & 2601057 & 7089500 & 0.366889\\ \hline 76 & 3404301 & 9289091 & 0.366484\\ \hline 78 & 4441779 & 12132164 & 0.366116\\ \hline 80 & 5777292 & 15796476 & 0.365733\\ \hline 82 & 7492373 & 20506255 & 0.365370\\ \hline 84 & 9688780 & 26543660 & 0.365013\\ \hline 86 & 12494653 & 34262962 & 0.364669\\ \hline 88 & 16069159 & 44108109 & 0.364313\\ \hline 90 & 20614755 & 56634173 & 0.363999\\ \hline 92 & 26377657 & 72533807 & 0.363660\\ \hline 94 & 33671320 & 92669720 & 0.363348\\ \hline 96 & 42878858 & 118114304 & 0.363028\\ \hline 98 & 54481054 & 150198136 & 0.362728\\ \hline 100 & 69065657 & 190569292 & 0.362418\\ \hline 102 & 87370195 & 241265379 & 0.362133\\ \hline 104 & 110287904 & 304801365 & 0.361835\\ \hline 106 & 138937246 & 384276336 & 0.361556\\ \hline 108 & 174675809 & 483502844 & 0.361272\\ \hline 110 & 219186741 & 607163746 & 0.361001\\ \hline \end{tabular} \caption{Sizes of $G(n)$ and $P(n)$ and their ratio for $2 \leq n \leq 110$.} } \end{table} \begin{table} {\scriptsize \begin{tabular}{|l||l|l|l|} \hline $n$ & $|G(n)|$ & $|P(n)|$ & $|G(n)|/|P(n)|$ \\ \hline \hline 112 & 274512656 & 761002156 & 0.360725\\ \hline 114 & 343181668 & 952050665 & 0.360466\\ \hline 116 & 428244215 & 1188908248 & 0.360200\\ \hline 118 & 533464959 & 1482074143 & 0.359945\\ \hline 120 & 663394137 & 1844349560 & 0.359690\\ \hline 122 & 823598382 & 2291320912 & 0.359443\\ \hline 124 & 1020807584 & 2841940500 & 0.359194\\ \hline 126 & 1263243192 & 3519222692 & 0.358955\\ \hline 128 & 1560795436 & 4351078600 & 0.358715\\ \hline 130 & 1925513465 & 5371315400 & 0.358481\\ \hline 132 & 2371901882 & 6620830889 & 0.358248\\ \hline 134 & 2917523822 & 8149040695 & 0.358021\\ \hline 136 & 3583515700 & 10015581680 & 0.357794\\ \hline 138 & 4395408234 & 12292341831 & 0.357573\\ \hline 140 & 5383833857 & 15065878135 & 0.357353\\ \hline 142 & 6585699894 & 18440293320 & 0.357136\\ \hline 144 & 8045274746 & 22540654445 & 0.356923\\ \hline 146 & 9815656018 & 27517052599 & 0.356711\\ \hline 148 & 11960467332 & 33549419497 & 0.356503\\ \hline 150 & 14555902348 & 40853235313 & 0.356297\\ \hline 152 & 17692990183 & 49686288421 & 0.356094\\ \hline 154 & 21480510518 & 60356673280 & 0.355893\\ \hline 156 & 26048320019 & 73232243759 & 0.355695\\ \hline 158 & 31551087790 & 88751778802 & 0.355498\\ \hline 160 & 38173235010 & 107438159466 & 0.355304\\ \hline 162 & 46134037871 & 129913904637 & 0.355112 \\ \hline 164 & 55694314567 & 156919475295 & 0.354923 \\ \hline 166 & 67163674478 & 189334822579 & 0.354735 \\ \hline 168 & 80909973315 & 228204732751 & 0.354550 \\ \hline 170 & 97368672089 & 274768617130 & 0.354366 \\ \hline 172 & 117056456152 & 330495499613 & 0.354185 \\ \hline 174 & 140584220188 & 397125074750 & 0.354005 \\ \hline 176 & 168675124141 & 476715857290 & 0.353827 \\ \hline 178 & 202182888436 & 571701605655 & 0.353651 \\ \hline 180 & 242116891036 & 684957390936 & 0.353477 \\ \hline 182 & 289666252014 & 819876908323 & 0.353305 \\ \hline 184 & 346234896845 & 980462880430 & 0.353134 \\ \hline 186 & 413474657328 & 1171432692373 & 0.352965 \\ \hline 188 & 493331835384 & 1398341745571 & 0.352700 \\ \hline 190 & 588093594457 & 1667727404093 & 0.352632 \\ \hline 192 & 700451190712 & 1987276856363 & 0.352468 \\ \hline 194 & 833561537987 & 2366022741845 & 0.352305 \\ \hline 196 & 991134281267 & 2814570987591 & 0.352144 \\ \hline 198 & 1177516049387 & 3345365983698 & 0.351984 \\ \hline 200 & 1397805210533 & 3972999029388 & 0.351826 \\ \hline 202 & 1657968320899 & 4714566886083 & 0.351669 \\ \hline 204 & 1964994991232 & 5590088317495 & 0.351514 \\ \hline 206 & 2327052859551 & 6622987708040 & 0.351360 \\ \hline 208 & 2753697110356 & 7840656226137 & 0.351207 \\ \hline 210 & 3256081386335 & 9275102575355 & 0.351056 \\ \hline 212 & 3847232865612 & 10963707205259 & 0.350757 \\ \hline 214 & 4542341563460 & 12950095925895 & 0.350757 \\ \hline 216 & 5359127512113 & 15285151248481 & 0.350610 \\ \hline 218 & 6318223879596 & 18028182516671 & 0.350464 \\ \hline 220 & 7443670977177 & 21248279009367 & 0.350319 \\ \hline \end{tabular} \caption{Sizes of $G(n)$ and $P(n)$ and their ratio for $112 \leq n \leq 220$.} } \end{table} \begin{thebibliography}{DuSaWo} \bibitem[At]{At} A. O. L. Atkin, ``A note on ranks and conjugacy of partitions,'' {\em Quart. J. Math., Oxford Ser. (2)}{\bf 17} (1966) 335-338. \bibitem[EG]{EG} P. Erd\"{o}s and T. Gallai, ``Graphs with given degree of vertices,'' {\em Mat. Lapok} {\bf 11} (1960) 264-274. \bibitem[ER]{ER} P. Erd\"{o}s and L. B. Richmond, ``On graphical partitions,'' {\em Combinatorica} {\bf 13} (1993) 57-63. %\bibitem[Hal]{Hal} Marshall Hall? \bibitem[Has]{Has} W. H\"{a}sselbarth, ``Die Verzweigtheit von Graphen'', {\em Match.} {\bf 16} (1984) 3-17. \bibitem[RA1]{RA1} C. C. Rousseau and F. Ali, ``On a conjecture concerning graphical partitions,'' preprint, April 1994. \bibitem[RA2]{RA2} C. C. Rousseau and F. Ali, ``A note on graphical partitions,'' preprint, April 1994. \bibitem[SH]{SH} G. Sierksma and H. Hoogeveen, ``Seven criteria for integer sequences being graphic,'' {\em Journal of Graph Theory} {\bf 15}, No. 2 (1991) 223-231. \bibitem[St]{St} R. P. Stanley, ``A zonotope associated with graphical degree sequences,'' in {\em Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift,} P. Gritznann and B. Sturmfels, eds., ACM, AMS (1991). %\bibitem[VS]{VS} V. E. Vickers and J. Silverman, %``A technique for generating specialized Gray codes,'' %{\em IEEE Transactions on Computers} {\bf C-29} (1980) 329-331. \end{thebibliography} \end{document}