% 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}




