\documentclass[12pt]{article}

\usepackage{amsmath}
\usepackage{amssymb}

%\usepackage[textheight=8.5in, margin=1.6in]{geometry}
\usepackage[total={6in,8in}]{geometry}

\usepackage{tikz}
\tikzstyle{ball} = [circle,shading=ball, ball color=black,
    minimum size=1mm,inner sep=1.3pt]

%\usepackage{graphicx}

\usepackage[shortlabels]{enumitem}
\usepackage{enumitem}
\setlist[enumerate]{leftmargin=*,label=(\alph*)}

\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\Span}{\mathrm{Span}}
\DeclareMathOperator{\rk}{\mathrm{rank}}
\DeclareMathOperator{\trace}{\mathrm{tr}}
\DeclareMathOperator{\im}{\mathrm{im}}
\DeclareMathOperator{\Sym}{\mathrm{Sym}}
\DeclareMathOperator{\Hom}{\mathrm{Hom}}

\newcounter{problem}
\renewcommand \thesection {\theproblem}
\newenvironment{prob}[1][]
{
  \refstepcounter{problem}\par\medskip
  \def\myArg{#1}
  \ifx\myArg\empty
    \noindent \textsc{Problem~\theproblem.} \rmfamily
  \else
    \noindent \textsc{Problem~\theproblem\ (\textnormal{#1}).} \rmfamily
  \fi
}
{
  \medskip

}

\parskip = 0.05in
\parindent = 0.0in

%\pagestyle{empty}

\begin{document}

\centerline{Math 372 Homework for Wednesday, Week 7}
\bigskip

\begin{prob}
      Let~$G=(V,E)$ be an undirected graph with vertex
      set~$V=\{v_1,\dots,v_n\}$ and edge set~$E$.  (For simplicity, we will
      assume~$G$ has no multiple edges.) A {\em divisor} on~$G$ is a
      vector~$D\in\Z^n$.  Think of the integer~$D(i)$ as a number of dollars
      assigned to vertex~$v_i$.  If~$D(i)<0$, then~$v_i$ is in debt.  A {\em
      lending move} by~$v_i$ consists of~$v_i$ giving a dollar to each of its
      neighbors and, consequently, losing~$\deg(v_i)$ dollars, itself.  (By
        definition~$v_j$ is a {\em neighbor} of~$v_i$ if~$v_iv_j$ is an edge
      of~$G$.)  A {\em borrowing move} by vertex~$v_i$ is the opposite:~$v_i$
      takes a dollar from each of its neighbors.  Say divisors~$D$ and~$D'$ are
      {\em linearly equivalent}, denoted~$D\sim D'$, if~$D'$ can be derived
      from~$D$ through a series of lending and borrowing moves.
      The {\em dollar game} on~$G$
      starts with a divisor~$D$, and the goal is to make lending and borrowing
      moves to arrive at a linearly equivalent divisor~$E$ such that~$E\geq0$, i.e., such
      that~$E(i)\geq0$ for $i=1,\dots,n$.
      \begin{enumerate}[(a)]
        \item Use the Polya counting technique to compute the number of necklaces
  	with~$4$ blue beads and~$3$ red beads.
        \item Let~$G=C_3$, the cycle graph on~$3$ vertices~$v_1,v_2,v_3$ (a
	  triangle), and
  	consider the divisor~$D=(4,0,0)$. By performing lending and borrowing
  	moves, determine all divisors~$E\geq 0$ such that~$D\sim E$. In other
  	words, find all possible winning end conditions for the dollar game
  	on~$G$ starting at~$D$.
        \item Give a combinatorial bijection between the necklaces you found
  	in~(a) and the divisors~$E$ you found in~(b).  To give a ``combinatorial
  	bijection'', you should find a natural and meaningful story that says
  	which necklace should be associated with which winning
  	divisor~$E$.  (If this is done correctly, it will generalize to
  	  necklaces with~$k$ blue beads and~$\ell$ red beads
  	  whenever~$\gcd(k,\ell)=1$.)
      \end{enumerate}
\end{prob}

\begin{prob}
      \begin{enumerate}
        \item Consider a power series of the form $f=1+2x+5x^2+3x^3+\cdots$  Since
  	you do not know all of the coefficients of $f$, you cannot compute all
  	the coefficients of $1/f$, however determine as many as possible.
        \item Let $f= x+x^2$ and $f^{-1}=\sum_{n\geq1}a_nx^n$, so that we have
	  \[
	    f(f^{-1}(x))=f^{-1}(f(x))=x.
	  \]
	 Find $a_n$ for $n=1,2,3,4$.
      \end{enumerate}
\end{prob}

\begin{prob}
  Find closed forms for the ordinary power series for the following sequences:
    \begin{enumerate}
      \item $\{\sum_{k=0}^n(k+2k^3)\}_n=\{0,3,21,78,210,\dots\}$.
      \item The odd integers, $\{1,3,5,\dots\}$.
      \item $\{1,0,1,0,1,0,\dots\}$.
      \item $\{1,0,2,0,3,0,4,0,\}$.
    \end{enumerate}
\end{prob}

\begin{prob}
  Fix $n\geq0$.  Find a closed form for the ordinary power series for the
    sequence $\{\sum_{i=0}^k(-1)^i\binom{n}{i}i\}_k$ . Compare coefficients to
     derive an identity for binomial coefficients.
\end{prob}

    \begin{prob}
      Consider the Fibonacci numbers, $F_0=0\), \(F_1=1$, and
          $F_n=F_{n-1}+F_{n-2}$ for $n\geq2$. Let $F$ be the ordinary generating
          function for the Fibonacci numbers. 
          \begin{enumerate}
            \item Use the fact that $F=x/(1-x-x^2)$ to write the multiplicative
      	inverse of $1+F$ as a power series $G$. Determine all of the
      	coefficients of $G$ explicitly.
            \item Equating the coefficient of \(x^n\) on both sides of $(1+F)G=1$
      	yields which identities among Fibonacci numbers?
          \end{enumerate}
    \end{prob}
\end{document}
