Skip to main content
added 1028 characters in body
Source Link
Ira Gessel
  • 17k
  • 1
  • 58
  • 80

Here is a combinatorial proof. Let $$t(x)=p(x+1)=\sum_{k=0}^r (-1)^{r-k}\binom rk (1+x)^{\binom k2}.$$ We want to show that $t(x)$ is divisible by $x^{\left\lceil r/2\right\rceil}$.

The coefficient of $x^j$ in $t(x)$ is the number of graphs with vertex set $\{1,2,\dots, r\}$, $j$ edges, and no isolated vertices. This can be proved easily using inclusion-exclusion or properties of exponential generating functions. The coefficients of these polynomials, with this combinatorial interpretation, can be found in the OEIS as sequence A054548 or A276639.

Since a graph with $r$ vertices and no isolated vertices must have at least $\left\lceil r/2\right\rceil$ edges, $t(x)$ is divisible by $x^{\left\lceil r/2\right\rceil}$.

It's interesting to note that the cumulants of the log-normal distribution are related to the inversion enumerator for labeled trees.

Additional comment: Here's a more detailed explanation of the combinatorial interpretation. Let $$ u_n(x) = \sum_G x^{e(G)}, $$ where the sum is over all graphs $G$ with vertex set $[n]:=\{1,2,\dots,n\}$ and $e(G)$ is the number of edges of $G$, and let $$ t_n(x) = \sum_H x^{e(H)}, $$ where the sum is over all graphs $H$ with vertex set $[n]$ and no isolated vertices. Then $$u_n(x) = \sum_{k=0}^n \binom nk t_k(x)$$ since any graph with vertex set $[n]$, and with $n-k$ isolated vertices, can be specified by choosing a $k$-subset $S$ of $[n]$, constructing a graph without isolated vertices with vertex set $S$, and leaving the elements of $[n]\setminus S$ as isolated vertices. This may be inverted to give $$t_n(x) = \sum_{k=0}^n (-1)^{n-k}\binom nk u_k(x).$$

But $u_n(x) = (1+x)^{\binom n2}$, since a graph with vertex set $[n]$ may be specified by including or not including each of the $\binom n2$ possible edges. Therefore $$t_n(x) = \sum_{k=0}^n (-1)^{n-k}\binom nk (1+x)^{\binom n2}.$$

Here is a combinatorial proof. Let $$t(x)=p(x+1)=\sum_{k=0}^r (-1)^{r-k}\binom rk (1+x)^{\binom k2}.$$ We want to show that $t(x)$ is divisible by $x^{\left\lceil r/2\right\rceil}$.

The coefficient of $x^j$ in $t(x)$ is the number of graphs with vertex set $\{1,2,\dots, r\}$, $j$ edges, and no isolated vertices. This can be proved easily using inclusion-exclusion or properties of exponential generating functions. The coefficients of these polynomials, with this combinatorial interpretation, can be found in the OEIS as sequence A054548 or A276639.

Since a graph with $r$ vertices and no isolated vertices must have at least $\left\lceil r/2\right\rceil$ edges, $t(x)$ is divisible by $x^{\left\lceil r/2\right\rceil}$.

It's interesting to note that the cumulants of the log-normal distribution are related to the inversion enumerator for labeled trees.

Here is a combinatorial proof. Let $$t(x)=p(x+1)=\sum_{k=0}^r (-1)^{r-k}\binom rk (1+x)^{\binom k2}.$$ We want to show that $t(x)$ is divisible by $x^{\left\lceil r/2\right\rceil}$.

The coefficient of $x^j$ in $t(x)$ is the number of graphs with vertex set $\{1,2,\dots, r\}$, $j$ edges, and no isolated vertices. This can be proved easily using inclusion-exclusion or properties of exponential generating functions. The coefficients of these polynomials, with this combinatorial interpretation, can be found in the OEIS as sequence A054548 or A276639.

Since a graph with $r$ vertices and no isolated vertices must have at least $\left\lceil r/2\right\rceil$ edges, $t(x)$ is divisible by $x^{\left\lceil r/2\right\rceil}$.

It's interesting to note that the cumulants of the log-normal distribution are related to the inversion enumerator for labeled trees.

Additional comment: Here's a more detailed explanation of the combinatorial interpretation. Let $$ u_n(x) = \sum_G x^{e(G)}, $$ where the sum is over all graphs $G$ with vertex set $[n]:=\{1,2,\dots,n\}$ and $e(G)$ is the number of edges of $G$, and let $$ t_n(x) = \sum_H x^{e(H)}, $$ where the sum is over all graphs $H$ with vertex set $[n]$ and no isolated vertices. Then $$u_n(x) = \sum_{k=0}^n \binom nk t_k(x)$$ since any graph with vertex set $[n]$, and with $n-k$ isolated vertices, can be specified by choosing a $k$-subset $S$ of $[n]$, constructing a graph without isolated vertices with vertex set $S$, and leaving the elements of $[n]\setminus S$ as isolated vertices. This may be inverted to give $$t_n(x) = \sum_{k=0}^n (-1)^{n-k}\binom nk u_k(x).$$

But $u_n(x) = (1+x)^{\binom n2}$, since a graph with vertex set $[n]$ may be specified by including or not including each of the $\binom n2$ possible edges. Therefore $$t_n(x) = \sum_{k=0}^n (-1)^{n-k}\binom nk (1+x)^{\binom n2}.$$

Source Link
Ira Gessel
  • 17k
  • 1
  • 58
  • 80

Here is a combinatorial proof. Let $$t(x)=p(x+1)=\sum_{k=0}^r (-1)^{r-k}\binom rk (1+x)^{\binom k2}.$$ We want to show that $t(x)$ is divisible by $x^{\left\lceil r/2\right\rceil}$.

The coefficient of $x^j$ in $t(x)$ is the number of graphs with vertex set $\{1,2,\dots, r\}$, $j$ edges, and no isolated vertices. This can be proved easily using inclusion-exclusion or properties of exponential generating functions. The coefficients of these polynomials, with this combinatorial interpretation, can be found in the OEIS as sequence A054548 or A276639.

Since a graph with $r$ vertices and no isolated vertices must have at least $\left\lceil r/2\right\rceil$ edges, $t(x)$ is divisible by $x^{\left\lceil r/2\right\rceil}$.

It's interesting to note that the cumulants of the log-normal distribution are related to the inversion enumerator for labeled trees.