
%degg.tex: ``All the Moments of the Vertex Degrees of Randomly Generated
%Graphs''
%
%a Plain TeX file by Doron Zeilberger (1 page)
 
%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\Tilde{\char126\relax}
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
 0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
 height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6 
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\parindent=0pt
\overfullrule=0in
%end macros
 
\bf
\centerline
{
All the Moments of the Vertex Degrees of Randomly Generated
Graphs
}
\rm
\bigskip
\centerline{ {\it 
Doron ZEILBERGER
}\footnote{$^1$}
{\eightrm  \raggedright
Department of Mathematics, Rutgers University (New Brunswick),
Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway,
NJ 08854-8019, USA.
{\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/   .}
Dec. 1, 2003.  
Exclusive to the Personal Journal of Ekhad and Zeilberger
{\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/pj.html   .}
Supported in part by the NSF. 
Version of May 9, 2005 [correcting a typo pointed out by
Mohamud Mohammed].
} 
}

Consider the set of all labelled graphs on $n$ vertices and
$m$ edges. By the handshaking lemma the average degree 
of {\it every} graph is
$2m/n$. Higher moments do depend on the graph, but
one can easily compute the 
average of the average of
${ {deg(v)} \choose {k}}$, for any $k$.
Let $N=n(n-1)/2$. The answer is
${ {n-1} \choose {k}}{ {N-k} \choose {m-k}}/{ {N} \choose {m}}$,
which equals the rational funcion (in $n$ and $m$)
${ {n-1} \choose {k}}(m-k+1)_k/(N-k+1)_k$, where as
usual $(a)_k:=a(a+1) \cdots (a+k-1)$.
Indeed, for any particular vertex $v$, the sum of
${ {deg(v)} \choose {k}}$ over all graphs with $n$ vertices
and $m$ edges
counts such graphs with a $k$-subset of $v$'s neighbors marked.
Clearly the number of these marked graphs is
${ {n-1} \choose {k}}{ {N-k} \choose {m-k}}$, (the first term
for choosing the marked neighbors and the second term for choosing the
remaining edges. From this it is easy to compute any desidred moment.

The special case $k=2$ yields a one-line proof of the result in
{\bf Ivan Gutman and Peter Paule,
 Univ. Beograd. Publ. Elek. Fak. 13 (2002), 30-35}.
[{\eighttt http://mathematika.etf.bg.ac.yu/publikacije/}].

\end

