\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm
{\LARGE\bf Multiplicative Functions \\
\vskip .02in 
Generalized Binomial Coefficients, and\\
\vskip .1in
Generalized Catalan Numbers}
\vskip 1cm
\large
Tom Edgar\\
Department of Mathematics \\ 
Pacific Lutheran University \\ 
Tacoma, WA 98447-0003\\ 
USA\\
\href{mailto:edgartj@plu.edu}{\tt edgartj@plu.edu} \\
\ \\
Michael Z. Spivey\\
Department of Mathematics and Computer Science \\ University of Puget Sound \\ Tacoma, WA 98416-1043\\
USA\\
\href{mailto:mspivey@pugetsound.edu}{\tt mspivey@pugetsound.edu}\\
\end{center}

\vskip .2 in

\begin{abstract}
We investigate generalized binomial coefficients of multiplicative
functions. We provide a formula for these coefficients and use this
formula to prove that the coefficients are always integral if the
function is also a divisible function. Furthermore, we prove that
multiplicative and divisible functions have integral generalized
Fuss-Catalan numbers. Along the way, we include some results about
specific multiplicative functions such as $\gcd_k$ and $\phi$. We
finish by connecting these results to a classical result due to Ward.
\end{abstract}

\section{Introduction}
Let $\mathbb{N}$ be the set of positive integers. Then, given a function $f: \mathbb{N} \to \mathbb{N}$, define for nonnegative integers $n$ and $m$ the {\em generalized binomial coefficient} ${{n+m}\choose{n}}_f$ via 
\begin{equation*}
{{n+m}\choose{n}}_f = \frac{\prod_{i=1}^{n+m} f(i)}{ \left(\prod_{i=1}^{n} f(i) \right) \left(\prod_{i=1}^{m} f(i) \right)},
\end{equation*}
where an empty product is defined to be 1.

What conditions on $f$ result in the generalized binomial coefficient ${{n+m}\choose{n}}_f$ taking on only integer values?  Obviously the usual binomial coefficients, where $f(n) = n$, are integers.  Several authors have investigated this question for other functions $f$.  Knuth and Wilf~\cite{KnWi89} have proved that the generalized binomial coefficients are integers when the function $f$ is strongly divisible; i.e., when $\gcd(f(m),f(n)) = f(\gcd (m,n))$ for all $m,n$.   This includes the Fibonacci sequence, as it is strongly divisible.  Other authors (see, for example, Carmichael~\cite{Car1913}) have proved that the generalized binomial coefficients are integers for generalized Fibonacci sequences defined by $f(n+2) = a f(n+1) + b f(n)$, with $a, b$ integers and $f(1) = f(2) = 1$.  Edgar~\cite{Edg14} has also proved that Euler's $\phi$-function, Jordan's generalization of it, and Dedekind's $\psi$-function as choices for $f$ give rise to integer generalized binomial coefficients.  In fact, it turns out that these three examples can be shown to have integer generalized binomial coefficients as a consequence of a result by Ward~\cite{ward}.

A related result for the usual binomial coefficients is {\em Kummer's theorem}, which describes their prime factorization.  More specifically, Kummer's theorem states that the exponent of the largest power of a prime $p$ that divides ${{n+m}\choose{n}}$ is the number of carries when $n$ and $m$ are added in base $p$.  Knuth and Wilf~\cite{KnWi89} generalize Kummer's theorem and give an analog of it for a certain class of strongly divisible functions. 

In this paper we investigate generalized binomial coefficients formed from {\em multiplicative functions}; i.e., functions $f$ in which $f(1) = 1$ and $f(mn) = f(m) f(n)$ when $m$ and $n$ are relatively prime.

Our main theorem (Theorem \ref{multthm}) gives a formula for ${{n+m}\choose{n}}_f$ when $f$ is multiplicative.  This result has the following consequences.

\begin{enumerate}
	\item The formula is in terms of i) the values of $f$ at prime powers and ii) the carries when $n$ and $m$ are added in prime bases.  The formula thus generalizes Kummer's theorem in a different way than that of Knuth and Wilf.
	\item While multiplicative functions in general do not give rise to integral generalized binomial coefficients, our formula allows us to prove that ${{n+m}\choose{n}}_f$ is an integer when $f$ is both multiplicative and {\em divisible}, i.e., when $m|n$ implies $f(m)|f(n)$, but not necessarily strongly divisible.  This category includes completely multiplicative functions. In Section \ref{finalsec}, we prove that this result is a special case of a result of Ward's.  However, this is not obvious: Ward's result does not apply to multiplicative functions alone, nor to divisible functions alone, but it does turn out to apply to functions that are both multiplicative and divisible.

	\item Let $\gcd_k(n)$ denote the function that, for fixed $k$, yields the greatest common divisor of $n$ and $k$.  We obtain a Kummer-like result that the highest power of a prime $p$ that divides ${{n+m}\choose{n}}_{\gcd_k}$ is the number of carries in the base $p$ sum of $n$ and $m$ that occur before the $\nu_p(k)$ position, where $\nu_p(k)$ is the exponent of the highest power of $p$ that divides $k$.
	\item The formula gives a necessary and sufficient criterion for determining the values of $n$ and $m$ yielding integral generalized binomial coefficients for all multiplicative functions.
	\item We obtain an explicit formula for the generalized Fuss-Catalan number, given by $A_f(n,q,r) =\frac{f(r)}{f(nq+r)}{{nq+r}\choose{n}}_f$, in terms of the values of $f$ at prime powers and certain carries in prime bases, for $f$ multiplicative.  If $f$ is also divisible, this implies that the generalized Fuss-Catalan number is an integer for all values of $n, q$, and $r$.  Thus the generalized Catalan number, $\frac{1}{f(n+1)} {{2n}\choose{n}}_f$, is also always an integer when $f$ is multiplicative and divisible.  In addition, as Euler's $\phi$-function is both multiplicative and divisible, we obtain a positive answer to Edgar's question ~\cite{Edg14} as to whether $\frac{1}{\phi(n+1)}{{2n}\choose{n}}_\phi$ is always an integer.  
\end{enumerate}

In the final section, we investigate the slightly more general formulation due to Ward and provide formulas for the associated Fuss-Catalan numbers as discussed in (5) above. We obtain alternate formulas for generalized binomial coefficients that can be shown to be equivalent to the others we present here.  However, the general results require all base-$b$ representations of natural numbers whereas the multiplicative and divisible functions only require prime base representations.

We now define notation that will be used throughout.  Let $n,m$ and $b$ be nonnegative integers.  Then $n$ has a unique base-$b$ representation of the form $n = n_0 + n_1b + \cdots + n_k b^k$.  We express this more compactly as $(n_0, n_1, \ldots, n_k)_b$.  Similarly, $m$ has a unique base-$b$ representation $m = m_0 + m_1 b + \cdots + m_l b^l$ that we express as $(m_0, m_1, \ldots, m_l)_b$.

Define the $(b,n,m)$-{\em carry sequence}, $\epsilon^{b,n,m}$, recursively via 
\[ \epsilon^{b,n,m}_i = \left\lfloor \frac{n_i + m_i + \epsilon_{i-1}}{b} \right\rfloor, \]
where we take $\epsilon^{b,n,m}_{-1} = 0$.  (When the context is understood, we omit the superscripts.)  The base-$b$ representation of $n+m$ is then given by 
\begin{equation}
\label{carryeq}
(n+m)_i = n_i + m_i + \epsilon_{i-1} - b \epsilon_i.
\end{equation}

Since $n_i < b$ and $m_i < b$, the definition of $\epsilon^{b,n,m}_i$ implies that $\epsilon^{b,n,m}_i$ is either 0 or 1 for each $i$.  We say there is a {\em carry in the $i$th position} of the base-$b$ sum of $m$ and $n$ if $\epsilon^{b,n,m}_i = 1$.

Let $\kappa_b(n,m) = \sum_i \epsilon_i^{p,n,m}$, the sum of the carries in the base-$b$ sum of $n$ and $m$.

When $p$ is prime, we let $\nu_p(n)$ denote the exponent of the highest power of $p$ that divides $n$.

Finally, let $[P]$ denote the {\em Iverson bracket} for the statement $P$:
\[ [P] = \begin{cases} 1, & \text{if $P$ is true}; \\
0, & \text{otherwise}. \end{cases}
\]

\section{A formula for ${{n+m}\choose{n}}_f$ when $f$ is multiplicative}

Before we prove our main result, an expression for ${{n+m}\choose{n}}_f$ when $f$ is multiplicative, we prove a couple of lemmas we will need.  The first gives two equivalent expressions for the existence of a carry in the $i$th position when $m$ and $n$ are added in base $p$ with $p$ prime.

\begin{lemma}
Let $p$ be prime and $n$ and $m$ be two nonnegative integers.
\label{carrylem}
\begin{align*}
\epsilon^{p,n,m}_r &= [ (n+m) \bmod p^{r+1} < n \bmod p^{r+1} ] \\
&= \left\lfloor \frac{n+m}{p^{r+1}} \right\rfloor - \left\lfloor \frac{n}{p^{r+1}} \right\rfloor - \left\lfloor \frac{m}{p^{r+1}} \right\rfloor.
\end{align*}
\end{lemma}
\begin{proof}
For the first equality, we have, by \eqref{carryeq},
\begin{align*}
(n+m) \bmod p^{r+1} - n \bmod p^{r+1} &= \sum_{i=0}^r \left((n+m)_i p^i - n_i p^i \right) \\
&= \sum_{i=0}^r \left( m_i p^i + p^i \epsilon_{i-1}  - p^{i+1}\epsilon_i  \right) \\
&= \sum_{i=0}^r m_i p^i - p^{r+1} \epsilon_r  \\
&= m \bmod p^{r+1} - p^{r+1} \epsilon_r . 
\end{align*}
This last expression is negative precisely when $\epsilon_r = 1$.

For the second equality, the proof is similar.  Let $((n+m)_0, (n+m)_1, \ldots, (n+m)_{t_p})_p$ be the base-$p$ representation of $n+m$.  We have, again by \eqref{carryeq},
\begin{align*}
\left\lfloor \frac{n+m}{p^{r+1}} \right\rfloor - \left\lfloor \frac{n}{p^{r+1}} \right\rfloor - \left\lfloor \frac{m}{p^{r+1}} \right\rfloor &= \sum_{i=r+1}^{t_p} \left( (n+m)_i p^{i-(r+1)} - n_i p^{i-(r+1)} - m_i p^{i-(r+1)} \right) \\
&= \sum_{i=r+1}^{t_p} \left( p^{i-(r+1)} \epsilon_{i-1} - p^{i-(r+1)+1} \epsilon_i \right)\\
&= \epsilon_r - p^{t_p-r} \epsilon_{t_p} \\
&= \epsilon_r,
\end{align*}
as $\epsilon_{t_p} = 0$ (otherwise, $n+m$ would have, in its base-$p$ representation, a digit in the $t_p+1$ position).
\end{proof}


The second lemma we need is the following.
\begin{lemma}
\label{highpowlem}
There are $\lfloor n/p^r \rfloor - \lfloor n/p^{r+1} \rfloor$ elements of $\{1, 2, \ldots, n\}$ for which $p^r$ is the highest power of $p$ occurring in that element's prime factorization. 
\end{lemma}
\begin{proof}
The number of elements of $\{1, 2, \ldots, n\}$ for which $p^r$ is the highest power of $p$ occurring in that element's prime factorization is the number of integers in $\{1, 2, \ldots n\}$ that are divisible by $p^r$ but not by $p^{r+1}$.  This is exactly $\lfloor n/p^r \rfloor - \lfloor n/p^{r+1} \rfloor$.
\end{proof}

With Lemmas~\ref{carrylem} and \ref{highpowlem} in hand we are ready to prove our main result.  
\begin{theorem}
\label{multthm}
Let $f: \mathbb{N} \to \mathbb{N}$ be a multiplicative function. Then 
\begin{align*}
{{n+m}\choose{n}}_f &= \prod_{p} \left( \prod_{i\geq 1} f(p^i)^{\epsilon^p_{i-1} - \epsilon^p_i} \right) \\
&= \prod_{p} \left( \prod_{i \geq 0} \left( \frac{f(p^{i+1})}{f(p^i)}\right)^{\epsilon^p_i } \right).
\end{align*}
\end{theorem}
\begin{proof}
First, we have, since $f$ is multiplicative,
\[\prod_{k=1}^n f(k) = \prod_{k=1}^n f\left(\prod_{p|k} p^{\nu_p(k)} \right) = \prod_{k=1}^n \left(\prod_{p|k} f(p^{\nu_p(k)}) \right).\]


Swapping the order of the products and using Lemma~\ref{highpowlem} to count the number of times $p^i$ occurs as the highest power, we obtain
\begin{align*}
\prod_{k=1}^n f(k) = \prod_{k=1}^n \left(\prod_{p|k} f(p^{\nu_p(k)}) \right) &= \prod_{p}\left(\prod_{i \geq 1} f(p^i)^{\lfloor n/p^i \rfloor - \lfloor n/p^{i+1} \rfloor } \right).
\end{align*}

Therefore,
\begin{align*}
{{n+m}\choose{n}}_f &= \prod_{p}\left(\prod_{i \geq 1} f(p^i)^{\lfloor (n+m)/p^i \rfloor - \lfloor n/p^i \rfloor  - \lfloor m/p^i \rfloor - \left(\lfloor (n+m)/p^{i+1} \rfloor - \lfloor n/p^{i+1} \rfloor - \lfloor (m/p^{i+1} \rfloor \right) } \right) \\
&= \prod_{p} \left( \prod_{i \geq 1} f(p^i)^{\epsilon^p_{i-1} - \epsilon^p_i} \right),
\end{align*}
where the second equality follows from Lemma~\ref{carrylem}.

In addition, $\epsilon^p_i$ occurs twice in the inner product of this expression: once as the power on $f(p^{i+1})$ and once as the negative power on $f(p^i)$.  Thus we also have 
\[{{n+m}\choose{n}}_f = \prod_{p} \left( \prod_{i \geq 0}\left( \frac{f(p^{i+1})}{f(p^i)}\right)^{\epsilon^p_i } \right).\]
\end{proof}


\section{Some integrality conditions for ${{n+m}\choose{n}}_f$ when $f$ is multiplicative}

In this section we discuss some conditions on a multiplicative function $f$ that imply ${{n+m}\choose{n}}_f$ is an integer for all values of $n$ and $m$.  We also give a condition on $n$ and $m$ under which ${{n+m}\choose{n}}_f$ is an integer for all multiplicative functions $f$.

Our first condition is a straightforward consequence of Theorem~\ref{multthm}.
\begin{corollary}
\label{dividescor}
If $f: \mathbb{N} \to \mathbb{N}$ is multiplicative and $f(p^r) | f(p^{r+1})$ for all primes $p$ and nonnegative integers $r$ then ${{n+m}\choose{n}}_f$ is an integer for all $m,n$.  In this case we have 
\[ {{n+m}\choose{n}}_f = \prod_{p \leq n+m} \left( \prod_{i \geq 0} g_p(i)^{\epsilon^p_i} \right),\]
where $g_p(r) = f(p^{r+1})/f(p^r)$.
\end{corollary}

Our second result shows that, for a multiplicative function, $f$, the condition on $f$ in Corollary~\ref{dividescor} is equivalent to $f$ being divisible.  
\begin{theorem}
\label{divseqthm}
Let $f: \mathbb{N} \to \mathbb{N}$ be a multiplicative function.  Then $f$ satisfies $f(p^r) | f(p^{r+1})$ for all primes $p$ and nonnegative integers $r$ iff $f$ is divisible.
\end{theorem}
\begin{proof}
First, suppose $f$ satisfies $f(p^r) | f(p^{r+1})$ for all $p$ and $r$.  This implies that if $s < r$ then $f(p^s) | f(p^r)$.  Suppose $m|n$.    We have that $f(m) = \prod_{p|m} f(p^{\nu_p(m)})$ and $f(n) = \prod_{p|n} f(p^{\nu_p(n)})$.  For any prime $p$, the fact that $m|n$ implies that $p^{\nu_p(m)} | p^{\nu_p(n)}$, and so $\nu_p(m) \leq \nu_p(n)$.  Thus $f(p^{\nu_p(m)}) | f(p^{\nu_p(n)})$, and so $f(m)|f(n)$.  Therefore, $f$ is a divisible function.

Next, suppose $f(m) | f(n)$ for all $m$ and $n$ such that $m|n$.  Let $m = p^r$ and $n = p^{r+1}$.  Then $f(p^r) | f(p^{r+1})$.
\end{proof}


Theorem~\ref{divseqthm} allows us to express Corollary~\ref{dividescor} in a more compact form.
\begin{corollary}
\label{divseqcor}
If $f: \mathbb{N} \to \mathbb{N}$ is multiplicative and divisible, then ${{n+m}\choose{n}}_f$ is an integer for all $m,n$. 
\end{corollary}

In Appendix \ref{appsequences}, we provide a list of functions (sequences) that are both multiplicative and divisible.

We look at two particularly important functions from this list: Euler's totient function and the $\gcd_k(n)$ function.  The fact that the totienomial coefficient ${{n+m}\choose{n}}_\phi$ is an integer was proved by Edgar~\cite{Edg14}; this also follows from the main theorem in Ward~\cite{ward}. With Corollary~\ref{dividescor}, we obtain this result plus the following formula.
\begin{corollary}
\label{totcor}
The totienomial coefficient ${{n+m}\choose{n}}_\phi$ is an integer for all $n,m$.  Moreover,
\[ {{n+m}\choose{n}}_\phi = \prod_{p \leq n+m} (p-1)^{\epsilon^p_0} p^{\kappa_p(n,m) - \epsilon^p_0}.\]
\end{corollary}
\begin{proof}
It is well-known that $\phi$ is multiplicative with $\phi(p^r) = p^{r-1} (p-1)$. Thus 
\[ \frac{\phi(p^{r+1})}{\phi(p^r)} = \begin{cases} p-1, & r = 0; \\ p, & r \geq 1. \end{cases}\]
The result then follows from Corollary~\ref{dividescor}.
\end{proof}

Using Corollary~\ref{dividescor}, we get a Kummer-like theorem for the $\gcd_k$ function, where $\gcd_k(n)$ is, for fixed $k$, the greatest common divisor of $k$ and $n$.
\begin{corollary}
\label{gcdcor}
We have that ${{n+m}\choose{n}}_{\gcd_k}$ is an integer for all $n, m$.  Moreover, the exponent of the largest power of a prime $p$ that divides ${{n+m}\choose{n}}_{\gcd_k}$ is the number of carries in the base $p$ sum of $n$ and $m$ that occur before the $\nu_p(k)$ position; i.e., \[ {{n+m}\choose{n}}_{\gcd_k} = \prod_{p} \left( \prod_{i=0}^{\nu_p(k)-1} p^{\epsilon^p_i} \right).\]
\end{corollary}
\begin{proof}
We have that $\gcd_k(p^r q^s) = p^{\min\{r, \nu_p(k)\} } q^{\min\{s, \nu_q(k)\} } = \gcd_k (p^r) \gcd_k(q^s)$.  It follows that $\gcd_k(n)$ is multiplicative.
 
In addition, \[ \frac{\gcd_k(p^{r+1})}{\gcd_k(p^r)} = \frac{p^{\min\{r+1, \nu_p(k)\}}}{p^{\min\{r, \nu_p(k)\}}} = \begin{cases} p, & r < \nu_p(k); \\ 1, & r \geq \nu_p(k). \end{cases}\]
The result then follows from Corollary~\ref{dividescor}.  
\end{proof}

An important class of multiplicative functions that are divisible is the class of {\em completely multiplicative} functions, which are functions satisfying $f(mn)=f(m)f(n)$ for all $m$ and $n$.  
\begin{corollary}
\label{compmult}
If $f: \mathbb{N} \to \mathbb{N}$ is completely multiplicative, then ${{n+m}\choose{n}}_f$ is an integer for all $n,m$.
\end{corollary}
\begin{proof}
If $f$ is completely multiplicative, then $f(p^{r+1})/f(p^r) = (f(p))^{r+1}/(f(p))^r =  f(p)$.  By Corollary~\ref{dividescor}, then, ${{n+m}\choose{n}}_f$ is an integer for all $m,n$, with
\[ {{n+m}\choose{n}}_f = \prod_{p \leq n+m} f(p)^{\kappa_p(n,m)}.\]
\end{proof}
Some functions that are completely multiplicative include the identity function and sequence \seqnum{A003958} in the On-Line Encyclopedia of Integer Sequences (OEIS)~\cite{OEIS15}. In particular, if we let $f(n) = n$ in Corollary~\ref{compmult}, then we quickly obtain Kummer's theorem.
\begin{corollary}[Kummer]
\label{Kummercor}
For any $n, m \in \mathbb{N}$, the exponent of the largest power of $p$ dividing ${{n+m}\choose{n}}$ is the number of carries occurring in the base-$p$ sum of $n$ and $m$; i.e., \[ \nu_p \left( {{n+m}\choose{n}} \right) = \kappa_p(n,m).\]
\end{corollary}

\begin{proof}
This statement is exactly the statement given in Corollary~\ref{compmult} since $f(p)=p$ for all $p$.
\end{proof}

\begin{corollary}
The totienomial coefficients and classical binomial coefficients are related by the following equation:
\[{{n+m}\choose{n}}_\phi={{n+m}\choose{n}}\cdot\prod_{p\leq n+m}\left(\frac{p-1}{p}\right)^{\epsilon_0^{p,n,m}}.\]
\end{corollary}

\begin{proof}
Combining Corollary~\ref{Kummercor} with Corollary~\ref{totcor} gives this result.
\end{proof}

The results thus far in this section provide conditions such that, given $f$, ${{n+m}\choose{n}}_f$ is an integer for all values of $n$ and $m$.  Our next result describes a necessary and sufficient condition such that, given $n$ and $m$, ${{n+m}\choose{n}}_f$ is an integer for all multiplicative functions $f$.
\begin{corollary}
\label{necsufcor}
Let $n$ and $m$ be nonnegative integers.  Then ${{n+m}\choose{n}}_f$ is an integer for all multiplicative functions $f: \mathbb{N} \to \mathbb{N}$ if and only if for all $p \leq n+m$ there exists an $s_p \geq 0$ such that $\epsilon^p_i = 1$ for all $i < s_p$ and $\epsilon^p_i = 0$ for all $i \geq s_p$.  
\end{corollary}
\begin{proof}
We prove the contrapositive of the statement.  If ${{n+m}\choose{n}}_f$ is not an integer, then Theorem~\ref{multthm} implies that there must be some prime $p$ and some $i \geq 1$ such that $\epsilon^p_{i-1} = 0$ but $\epsilon^p_i = 1$.  This is precisely the situation ruled out by the condition in the corollary.

Now, suppose there exists some prime $p$ and some $i$ such that $\epsilon^p_{i-1} = 0$ and $\epsilon^p_i = 1$.  Since multiplicative functions are determined by their values at prime powers, let $f$ be the multiplicative function defined, for primes $q$, by \[ f(q^j) = \begin{cases} 2, & q = p, j = i; \\ 1, & q \neq p \text{ or } j \neq i. \end{cases} \]
By Theorem~\ref{multthm}, ${{n+m}\choose{n}}_f = 1/2$.
\end{proof}


Figure~\ref{triangfig} contains a graph of the first 90 rows (starting at row 0) of a triangular array.  The row $n + m$, column $n$ entries that are shaded are those such that ${{n+m}\choose{n}}_f$ is an integer for all multiplicative functions $f$ (using the condition from Corollary~\ref{necsufcor}).  These entries are more concentrated on the sides of the triangle, which is not surprising, but there are some entries close to the middle of the triangle even fairly far down.

\begin{figure}[!ht]
  \centering
     \includegraphics[width=5.6in, bb=0 -1 314 277]{triangularpic.eps}
  \caption{Triangle of values of $n$ and $m$ such that ${{n+m}\choose{n}}_f$ is always an integer when $f$ is multiplicative.}
  \label{triangfig}
\end{figure}

Looking carefully at this triangle, the following are apparent.

\begin{corollary}
Let $f$ be a multiplicative function and $n$ be a nonnegative integer. Then 
\begin{enumerate}
\item
${{n}\choose{0}}_f$ and ${{n}\choose{1}}_f$ are always integers.
\item
${{n}\choose{2}}_f$ is an integer if and only if $n\equiv 2\pmod{4}$ or $n\equiv 3 \pmod{4}$.
\end{enumerate}

\begin{proof}
Part 1 is immediate from the definition and the facts that the empty product is 1 and $f(1)=1$ for multiplicative functions. 
For part 2, we note that if $n$ is equivalent to $2$ or $3$ mod $4$ then $n=(0,1,\ldots n_k)_2$ or $n=(1,1,\ldots, n_k)_2$ and so $n-2=(0,0,\ldots, n_k)_2$ or $n-2=(1,0,\ldots n_k)_2$. In either case, $\epsilon_i^{2,n-2,2}=0$ for all $i$. Now, for any prime $p>2$ we have $2=(2)_p$; consequently, for $i>0$, we see that $\epsilon_i^{p,n-2,2} = 1$ only if $\epsilon_{i-1}^{p,n-2,2}=1$. Conversely, if $n$ is equivalent to $0$ or $1$ mod $4$, then $(n-2)_2=(0,1,\ldots, n_k)_2$ or $(n-2)_2=(1,1,\ldots, n_k)_2$. As such, $\epsilon_0^{2,n-2,2}=0$ and $\epsilon_1^{2,n-2,2}=1$. The result follows by Corollary \ref{necsufcor}.
\end{proof}

\end{corollary}

\bigskip

\section{Generalized Catalan and Fuss-Catalan numbers when $f$ is multiplicative}

The Fuss-Catalan number $A(n,q,r)$ is given by $A(n,q,r) = \frac{r}{nq+r} {{nq+r}\choose{n}}$.  When $q = 2$ and $r = 1$, we have $A(n,2,1) = \frac{1}{2n+1} {{2n+1}\choose{n}} = \frac{1}{n+1} {{2n}\choose{n}} = C(n)$, the usual $n$th Catalan number.  (Here we use the absorption identity for the binomial coefficients.)

For a function $f: \mathbb{N} \to \mathbb{N}$ and $n,q,r \geq 0$, we define  the {\em $f$-Fuss-Catalan number $A_f(n,q,r)$} via 
\[ A_f(n,q,r) = \frac{f(r)}{f(nq+r)} {{nq+r}\choose{n}}_f .\]

In this section we find a formula for $A_f(n,q,r)$, when $f$ is multiplicative, analogous to Theorem~\ref{multthm}.  We then use this formula to obtain a Kummer-like theorem for Fuss-Catalan numbers.  We also prove that when $f$ is multiplicative and divisible, $A_f(n,q,r)$ is an integer for all $n \geq 0$.  In addition, we give the versions of all of these results for the usual Catalan numbers.  Since Euler's $\phi$-function is both multiplicative and divisible, we also answer in the affirmative a question of Edgar~\cite{Edg14} as to whether $C_\phi(n)$ is an integer for all $n \geq 0$.  

\begin{theorem}
\label{FussCatthm}
If $f: \mathbb{N} \to \mathbb{N}$ is multiplicative, then the $f$-Fuss-Catalan number given by $\displaystyle A_f(n,q,r) = \frac{f(r)}{f(nq+r)} {{nq+r}\choose{n}}_f$ satisifies
\[ A_f(n,q,r) = A(n) B(n) D(n),\]
where 
$$\begin{aligned}
A(n) &= \prod_{p |n, \nu_p(nq) \geq \nu_p(r)} \left( \prod_{i \geq 0} \left(\frac{f(p^{i+1})}{f(p^i)}\right)^{\epsilon^{p,n,n(q-1)+r}_i} \right), \\
\\
B(n) &= \prod_{p |n, \nu_p(nq) < \nu_p(r)} \left( \frac{f(p^{\nu_p(r)})}{f(p^{\nu_p(nq)})}\prod_{i \geq 0} \left(\frac{f(p^{i+1})}{f(p^i)}\right)^{\epsilon^{p,n,n(q-1)+r}_i} \right), \\
\\
D(n) &= \prod_{p \nmid n} \left( f(p^{\nu_p(r)})\prod_{i \geq 0} \left(\frac{f(p^{i+1})}{f(p^i)}\right)^{\epsilon^{p,n-1,n(q-1)+r}_i} \right).
\end{aligned}$$
\end{theorem}

\begin{proof}
By Theorem~\ref{multthm}, and the fact that $f$ is multiplicative, we have
$$\begin{aligned}
\frac{f(r)}{f(nq+r)}{{nq+r}\choose{n}}_f & =  \prod_p \frac{ f(p^{\nu_p(r)})}{ f(p^{\nu_p(nq+r)})}\left( \prod_{i \geq 0} \left( \frac{f(p^{i+1})}{f(p^i)}\right)^{\epsilon^{p,n,n(q-1)+r}_i} \right).
\end{aligned}$$

We now break the primes into three cases, corresponding to the three factors $A(n)$, $B(n)$, and $D(n)$ in the theorem statement.
\begin{enumerate}

\item Suppose $p$ is a prime that divides $n$ such that that $\nu_p(nq) \geq \nu_p(r)$.  Since $p$ divides $n$, $p$ divides $nq$.  Since $\nu_p(nq) \geq \nu_p(r)$, $\nu_p(nq+r) = \nu_p(r)$.  The contribution to the value of $A_f(n,q,r)$ for a prime $p$ in this case, then, is \[ \prod_{i \geq 0} \left(\frac{f(p^{i+1})}{f(p^i)}\right)^{\epsilon^{p,n,n(q-1)+r}_i}. \]

\item Suppose $p$ is a prime that divides $n$ such that $\nu_p(nq) < \nu_p(r)$. Since $p$ divides $n$, we know $p$ divides $nq$. The fact that $\nu_p(nq) < \nu_p(r)$ implies that $p$ also divides $r$ and $nq+r$, and consequently that $\nu_p(nq+r)=\nu_p(nq)$. The contribution to the value of $A_f(n,q,r)$ for a prime $p$ in this case is \[  \frac{f(p^{\nu_p(r)})}{f(p^{\nu_p(nq)})}\prod_{i \geq 0} \left(\frac{f(p^{i+1})}{f(p^i)}\right)^{\epsilon^{p,n,n(q-1)+r}_i}. \]

\item Suppose $p$ is a prime that does not divide $n$.  In this case it helps to express $A_f(n,q,r)$ as 
\begin{align*}
\frac{f(r)}{f(nq+r)}{{nq+r}\choose{n}}_f &=  \frac{f(r)}{f(nq+r)} \frac{f(nq+r) \cdots f(n(q-1)+r+1)}{f(n) \cdots f(1)} \\
&=  \frac{f(r)}{f(n)} \frac{f(nq+r-1) \cdots f(n(q-1)+r+1)}{f(n-1) \cdots f(1)} \\
&= \frac{f(r)}{f(n)} {{nq+r-1}\choose{n-1}}_f \\
&= \prod_p \frac{ f(p^{\nu_p(r)})}{ f(p^{\nu_p(n)})}\left( \prod_{i \geq 0} \left( \frac{f(p^{i+1})}{f(p^i)}\right)^{\epsilon^{p,n-1,n(q-1)+r}_i} \right).
\end{align*}
Since $p$ does not divide $n$, $\nu_p(n) = 0$.  Thus the contribution to $A_f(n,q,r)$ for a prime in this case is 
\[ f(p^{\nu_p(r)}) \left( \prod_{i \geq 0} \left( \frac{f(p^{i+1})}{f(p^i)}\right)^{\epsilon^{p,n-1,n(q-1)+r}_i} \right).\]

\end{enumerate}

\end{proof}

If we let $f(n) = n$ in Theorem~\ref{FussCatthm}, then we obtain a Kummer-like theorem for the Fuss-Catalan numbers.  
\begin{corollary}
\label{KummerFussCatcor}
The exponent of the largest power of a prime $p$ dividing $A(n,q,r)$ is given by the following:  \[ \nu_p \left( A(n,q,r) \right) = \begin{cases} \kappa_p(n,n(q-1)+r), & p | n, \, \nu_p(nq) \geq \nu_p(r); \\ \nu_p(r) - \nu_p(nq) + \kappa_p(n,n(q-1)+r), & p | n, \, \nu_p(nq) < \nu_p(r); \\ \nu_p(r) + \kappa_p(n-1,n(q-1)+r), & p \nmid n. \end{cases}\]
\end{corollary}
\begin{proof}
Let $f$ be the identity function; i.e., $f(n) = n$.  Again, the identity function is clearly multiplicative.  Applying Theorem~\ref{FussCatthm} to the case of a prime $p$ that divides $n$ and satisfies $\nu_p(nq) \geq \nu_p(r)$, we obtain the following contribution to $A(n,q,r)$ from $p$:

\begin{align*}
\prod_{i \geq 0} \left(\frac{f(p^{i+1})}{f(p^i)}\right)^{\epsilon^{p,n,n(q-1)+r}_i} = \prod_{i \geq 0} p^{\epsilon^{p,n,n(q-1)+r}_i} = p^{\sum_{i \geq 0} \epsilon^{p,n,n(q-1)+r}_i} = p^{\kappa_p(n,n(q-1)+r)}.
\end{align*}
The proofs of the other two cases are similar.
\end{proof}

Theorem~\ref{FussCatthm} also implies that $A_f(n,q,r)$ is an integer when $f$ is multiplicative and divisible.
\begin{corollary}
\label{multdivFussCatcor}
If $f: \mathbb{N} \to \mathbb{N}$ is both multiplicative and divisible, then $A_f(n,q,r)$ is an integer for all $n$.  In this case we have
\[ A_f(n,q,r) = A(n) B(n) D(n),\]
where
\begin{align*}
A(n) &= \prod_{p |n, \nu_p(nq) \geq \nu_p(r)} \left( \prod_{i \geq 0} g_p(i)^{\epsilon^{p,n,n(q-1)+r}_i} \right), \\
B(n) &= \prod_{p |n, \nu_p(nq) < \nu_p(r)} \left( \frac{f(p^{\nu_p(r)})}{f(p^{\nu_p(nq)})}\prod_{i \geq 0} g_p(i)^{\epsilon^{p,n,n(q-1)+r}_i} \right), \\
D(n) &= \prod_{p \nmid n} \left( f(p^{\nu_p(r)})\prod_{i \geq 0} g_p(i)^{\epsilon^{p,n-1,n(q-1)+r}_i} \right), \\
g_p(i) &= f(p^{i+1})/f(p^i).
\end{align*}

\end{corollary}
\begin{proof}
Since $f$ is divisible, $f(p^i)$ divides $f(p^{i+1})$.  In addition, since $\nu_p(nq) < \nu_p(r)$ then $f(p^{\nu_p(nq)})$ divides $f(p^{\nu_p(r)})$.  The result then follows from Theorem~\ref{FussCatthm}.
\end{proof}

\bigskip

The next few corollaries are the versions of Theorem~\ref{FussCatthm} and Corollaries~\ref{KummerFussCatcor} and \ref{multdivFussCatcor} for the usual Catalan numbers.

\begin{corollary}
\label{Catcor}
If $f: \mathbb{N} \to \mathbb{N}$ is multiplicative, then the $f$-Catalan number, given by $\displaystyle C_f(n) = \frac{1}{f(n+1)} {{2n}\choose{n}}_f$, satisfies
\[ C_f(n) = A(n) D(n),\]
where 

\begin{tabular}{ccc}
$\displaystyle A(n) = \prod_{p |n} \left( \prod_{i \geq 0} \left(\frac{f(p^{i+1})}{f(p^i)}\right)^{\epsilon^{p,n,n}_i} \right)$  & \hspace*{.03in} and \hspace*{.03in} &
$\displaystyle D(n) = \prod_{p \nmid n} \left( \prod_{i \geq 0} \left(\frac{f(p^{i+1})}{f(p^i)}\right)^{\epsilon^{p,n-1,n+1}_i} \right).$
\end{tabular}
\end{corollary}
\begin{proof}
The usual Catalan number is the case $q = 2$, $r = 1$, of the more general Fuss-Catalan number.  In this case, $\nu_p(r) = 0$ for all primes $p$.  Thus in Theorem~\ref{FussCatthm} we have $B(n) = 1$.  In addition, if $p$ divides $n$, then the base-$p$ representation of $n$ has a 0 in the ones place.  Thus $\epsilon_i^{p,n,n+1} = \epsilon_i^{p,n,n}$ in this case.  The rest of the result follows directly from Theorem~\ref{FussCatthm}.
\end{proof}

We also have a Kummer-like theorem for the Catalan numbers.  
\begin{corollary}
\label{KummerCatcor}
If a prime $p$ divides $n$, the exponent of the largest power of $p$ dividing $C(n)$ is the number of carries occurring in the base-$p$ sum of $n$ with itself. Otherwise, the exponent of the largest power of $p$ dividing $C(n)$ is the number of carries occurring in the base-$p$ sum of $n-1$ and $n+1$.  In other words, \[ \nu_p \left( C(n) \right) = \begin{cases} \kappa_p(n,n), & p | n; \\ \kappa_p(n-1,n+1), & p \nmid n. \end{cases}\]
\end{corollary}
\begin{proof}
This follows from Corollary~\ref{KummerFussCatcor}, with $q = 2$, $r = 1$.  As in the proof of Corollary~\ref{Catcor}, $\nu_p(r) = 0$ for all primes $p$, and so the case $\nu_p(nq) < \nu_p(r)$ does not occur.  Also as in the proof of Corollary~\ref{Catcor}, if $p|n$ then $\epsilon_i^{p,n,n+1} = \epsilon_i^{p,n,n}$ for all $i$.  Thus $\kappa_p(n,n+1) = \kappa_p(n,n)$.
\end{proof}

Finally, Corollary~\ref{multdivFussCatcor} implies that $C_f(n)$ is an integer when $f$ is multiplicative and divisible.
\begin{corollary}
\label{multdivCatcor}
If $f: \mathbb{N} \to \mathbb{N}$ is both multiplicative and divisible, then $C_f(n)$ is an integer for all $n$.  In this case we have
\[ C_f(n) = A(n) D(n),\]
where
\begin{center}
\begin{tabular}{ccc}
$\displaystyle A(n) = \prod_{p |n} \left( \prod_{i \geq 0} g_p(i)^{\epsilon^{p,n,n}_i} \right)$ & and &
$\displaystyle D(n) = \prod_{p \nmid n} \left( \prod_{i \geq 0} g_p(i)^{\epsilon^{p,n-1,n+1}_i} \right)$
\end{tabular}
\end{center}
with $g_p(i) = f(p^{i+1})/f(p^i)$.
\end{corollary}
Since Euler's $\phi$-function is both multiplicative and divisible, Corollary~\ref{multdivCatcor} answers in the affirmative a question of Edgar~\cite{Edg14} as to whether $C_\phi(n)$ is an integer for all $n \geq 0$.

\section{Ward's divisor functions}
\label{finalsec}

As mentioned in the introduction, Ward \cite{ward} proves that a larger class of functions have integer generalized binomial coefficients. We introduce that class of sequences here and obtain formulas for the associated Fuss-Catalan numbers, which also turn out to be integers. This class of sequences includes the multiplicative and divisible functions, but the formulas in this section require knowledge of carries in every base less than or equal to $n+m$ instead of only those arising in prime base arithmetic. Consequently, the formulas here are not as precise as the ones previously established.

For any sequence of integers $\mathbf{s}=(s_1,s_2,s_3,\ldots)$ define the function $f_\mathbf{s}:\mathbb{N}\to\mathbb{N}$ by 
\begin{equation}
\label{conditionward}
f_\mathbf{s}(n)=\prod_{d|n} s_d,
\end{equation}
where the product is over all divisors of $n$. 

\begin{theorem}[Ward]
\label{thmward}
Let $\mathbf{s}$ be a sequence of nonzero integers with associated function $f_\mathbf{s}$. For any nonnegative integers $n$ and $m$ we have
\begin{equation}
\label{wardeqn}
{{n+m}\choose{n}}_{f_\mathbf{s}}=\prod_{b> 1}s_b^{\epsilon_0^{b}},
\end{equation}
where $\epsilon_0^b=\epsilon_0^{b,n,m}$ is the carry in the ones position. 
\end{theorem}

\begin{proof}
Fix $b>1$. Then, the number of times that $s_b$ appears in $\prod_{i=1}^{k}f(k)$ is equal to the number of integers in $\{1,\ldots,k\}$ divisible by $b$, which is given by $\left\lfloor\frac{k}{b}\right\rfloor$. Hence, the number of times $s_b$ appears in the quotient
\[{{n+m}\choose{n}}_f = \frac{\prod_{i=1}^{n+m} f(i)}{ \left(\prod_{i=1}^{n} f(i) \right) \left(\prod_{i=1}^{m} f(i) \right)}\]
is given by $\left\lfloor\frac{n+m}{b}\right\rfloor-\left\lfloor\frac{n}{b}\right\rfloor-\left\lfloor\frac{m}{b}\right\rfloor$. Finally, a proof identical to the one given in Lemma \ref{carrylem} shows that $\epsilon_0^{b,n,m}=\left\lfloor\frac{n+m}{b}\right\rfloor-\left\lfloor\frac{n}{b}\right\rfloor-\left\lfloor\frac{m}{b}\right\rfloor$.
\end{proof}

In particular, since carries are always $0$ or $1$, this theorem implies that such functions $f_\mathbf{s}$ always have integral generalized binomial coefficients. As previously mentioned, this characterization requires arithmetic in all bases whereas our results in previous sections only require arithmetic in prime bases. 

\begin{remark}
\label{alternatedef}
Dyer \cite{dyer} suggests using equation \eqref{wardeqn} as a definition of generalized binomial coefficients. Doing so would allow one to define such coefficients for sequences in an arbitrary ring, as well as allow for $f(k)=0$ for some values of $k$. 
\end{remark}

\begin{theorem}
Let $f$ be a multiplicative and divisible function.  Then there exists an integer sequence $\mathbf{s}$ such that $f(n)=\prod_{d|n} s_d$ for all $n$.
\end{theorem}

\begin{proof}
Since $f$ is multiplicative, we must have $f(1)=1$, so we let $s_1=1$. Then for $i>1$, we define $\mathbf{s}$ as follows:
\[
s_i=\begin{cases} \frac{f(p^r)}{f(p^{r-1})}, & \mbox{ if $i=p^r$ ($r>0$) for $p$ prime;}\\
1, & \mbox{otherwise.}\end{cases}
\]
Since $f$ is divisible, $s_i$ is an integer for all $i$. Next, by definition we get $f(p^r)=\frac{f(p^r)}{f(p^{r-1})}\cdot\frac{f(p^{r-1})}{f(p^{r-2})}\cdots\frac{f(p)}{1}=\prod_{i=1}^rs_{p^i}=\prod_{d|p^r}s_d$. Then, since $f$ is multiplicative and $s_i=1$ when $i$ is not a prime power, we get that $f(n)=\prod_{d|n}s_d$ as required.
\end{proof}

We note that there are multiplicative sequences for which no integer sequence exists satisfying Condition \eqref{conditionward}.  In addition, there are divisible sequences for which no integer sequence exists satisfying Condition \eqref{conditionward}.  Moreover, there are sequences satisfying Condition \eqref{conditionward} that are not multiplicative and divisible; Ball, et al. \cite{edgarMAA} describe a few examples of such sequences, and some are listed in the appendix.

Similar to previous sections, we use Theorem \ref{thmward} to demonstrate that the associated Fuss-Catalan numbers are integers. Before doing this, we have the following lemma.

\begin{lemma}
\label{fussarithmetic}
Let $n,r,q,b$ be integers with $n\geq 0$, $r\geq 0$, $q>0$, and $b>1$. If $b$ divides $(nq+r)$ and $b$ does not divide $r$, then $\epsilon_0^{b,n(q-1)+r,n}=1$.
\end{lemma}

\begin{proof}
We have that $n=(n_0,n_1,\ldots,n_k)_b$, $nq+r=(m_0,m_1,\ldots,m_l)_b$, and $n(q-1)+r=(l_0,l_1,\ldots, l_t)_b$. Since $b$ divides $nq+r$, we have $m_0=0$, and we know that $n_0+l_0=m_0\pmod{b}$. Suppose, for the sake of contradiction, that $\epsilon_0^{b,n(q-1)+r,n}=0$; this implies that $n_0=0$ and $l_0=0$. Thus, $b$ divides $n$ and $b$ divides $n(q-1)+r$. In turn, we conclude that $b$ divides $n(q-1)$. The previous two statements imply that $b$ divides $r$, contradicting our main assumptions. Therefore, $\epsilon_0^{b,n(q-1)+r,n}=1$ as required.
\end{proof}

The integrality of $f_\mathbf{s}$-Fuss-Catalan numbers is now immediate from Theorem \ref{thmward}.

\begin{theorem}
\label{FC}
Let $\mathbf{s}$ be a sequence of nonzero integers with associated function $f_\mathbf{s}$. Then $A_{f_\mathbf{s}}(n,q,r)$ is an integer for all $n$.  In particular we have
\[ A_{f_\mathbf{s}}(n,q,r) = G(n)H(n)J(n), \]
with
\begin{center}
\begin{tabular}{ccccc}
$\displaystyle G(n) = \prod_{\substack{b>1\\ b|r\\ b\ \nmid\ nq+r}}s_b^{1+\epsilon_0^{b}},$  &\hspace{.3in} &
$\displaystyle H(n) = \prod_{\substack{b>1\\ b\ \nmid\ r\\ b\ \nmid\ nq+r}}s_b^{\epsilon_0^{b}},$ & \hspace{.3in}&
$\displaystyle J(n)  =\prod_{\substack{b>1\\ b\mid r\\ b\mid nq+r}}s_b^{\epsilon_0^{b}},$
\end{tabular}
\end{center}
where $\epsilon_0^b=\epsilon_0^{b,n(q-1)+r,n}$.
\end{theorem}

\begin{proof}
When $q=0$, the result is true by Theorem \ref{thmward}. Now by definition of $f_\mathbf{s}$ and Theorem \ref{thmward} we get
\[ A_{f_\mathbf{s}}(n,q,r) = \frac{f_\mathbf{s}(r)}{f_\mathbf{s}(nq+r)} {{nq+r}\choose{n}}_{f_{\mathbf{s}}} =\frac{\prod_{d|r} s_d}{\prod_{d|nq+r} s_d}\cdot \prod_{b> 1}s_b^{\epsilon_0^{b,n(q-1)+r,n}}.\]
If either $d| r$ and $d|nq+r$ or $d\nmid r$ and $d\nmid nq+r$ then there is no contribution of $s_d$ from the first fraction. On the other hand, if $d|r$ and $d\nmid nq+r$, then we have a total of $1+\epsilon_0^{d,n(q-1)+r,n}$ occurrences of $s_d$ in the product (not in the denominator). Finally, if $d\nmid r$ and $d|nq+r$, then by Lemma \ref{fussarithmetic}, we have $\epsilon_0^{d,n(q-1)+r,n}=1$ and so there is an occurrence of $s_d$ in both the numerator and the denominator, which cancel out.
\end{proof}

In a similar fashion to Remark \ref{alternatedef}, we could take the characterization in Theorem \ref{FC} as the definition of the $f_\mathbf{s}$-Fuss-Catalan numbers.

\appendix
\section{Sequences with integer generalized binomial coefficients}
\label{appsequences}

The Online Encyclopedia of Integer sequences (OEIS) contains a wealth of examples of multiplicative and divisible sequences that we consider in this paper as well as many examples of sequences satisfying the property of Ward described in Section \ref{finalsec}. In this appendix, we include a list of relevant examples of sequences. Moreover, every collection of generalized binomial coefficients can be interpreted as a triangle, read by rows, where entry $k$ in row $n$ is given by ${{n}\choose{k}}_f$. After the tables, we also describe a method for efficiently generating the triangle of generalized binomial coefficients efficiently. 

The following table lists interesting examples of multiplicative and divisible sequences along with the OEIS number. Additionally, we have provided the listing of the associated generalized binomial coefficients (typically read as a triangle by rows).

{\footnotesize
\begin{center}
\renewcommand\arraystretch{1.4}
\begin{tabular}{p{3in}|p{.55in}|p{.75in}}
Name, Description, or \newline Formula & OEIS\newline Entry & Generalized \newline binomial \newline coefficients\\
\hline
Euler totient function ($\phi$) & \seqnum{A000010} & \seqnum{A238453}\\
Identity function & \seqnum{A000027} & \seqnum{A007318}\\
Squares & \seqnum{A000290} & \seqnum{A008459}\\
Cubes & \seqnum{A000578} & \seqnum{A181543}\\
Dedekind psi function & \seqnum{A001615} & \seqnum{A238498}\\
$f(n)=n\phi(n)$ & \seqnum{A002618} & \seqnum{A255914}\\
Completely multiplicative, with $f(p) = p-1$ & \seqnum{A003958} & \\
Completely multiplicative with $f(p_k) = p_k\cdot(k+1)$ & \seqnum{A003961} &\\
If $n = \prod p_k^{e_k}$ then $a(n) = \prod (p_k-1)^{e_k}$, $a(1) = 1$ & \seqnum{A003958} & \\
If $n = \prod p_k^{e_k}$ then $a(n) = \prod (p_k+1)^{e_k}$, $a(1) = 1$ & \seqnum{A003959} & \\
Radical (largest squarefree number dividing $n$) & \seqnum{A007947} & \seqnum{A048804}\\
$n$ divided by the radical & \seqnum{A003557} & \seqnum{A246465}\\
Largest square dividing $n$ & \seqnum{A008833} & \\
Number of solutions to $x^2 = 0 \pmod{n}$ & \seqnum{A000188} & \\
Number of solutions to $x^2 = 1 \pmod{n}$ & \seqnum{A060594} & \\
$f(n) = n$ if $n$ is odd, $f(n) = 2n$ if $n$ is even & \seqnum{A022998} & \\
$f(n) = n$ if n odd, $n/2$ if n even & \seqnum{A026741} & \seqnum{A214281}\\
Unitary divisor function & \seqnum{A034444} &  \\
Number of squares dividing $n$ & \seqnum{A046951}  & \\
Unitary totient function & \seqnum{A047994} & \\
\end{tabular}
\end{center}

\begin{center}
\renewcommand\arraystretch{1.4}
\begin{tabular}{p{3in}|p{.55in}|p{.75in}}
Name, Description, or \newline Formula & OEIS\newline Entry & Generalized \newline binomial \newline coefficients\\
\hline
Unitary Jordan function $J_2^*(n)$ & \seqnum{A191414} & \\
$f(n) = n \prod_{p|n} p$ & \seqnum{A064549} & \\
Multiplicative, with $f(p^k) = p-1$ & \seqnum{A173557} & \seqnum{A239702}\\
Jordan function ($J_2$) & \seqnum{A007434} & \seqnum{A238688}\\
Jordan function ($J_3$) & \seqnum{A059376} & \seqnum{A238743} \\ 
Jordan function ($J_4$) & \seqnum{A059377} & \seqnum{A238754}\\
Jordan function ($J_5$) & \seqnum{A059378} & \seqnum{A239633}\\
Jordan function ($J_6$) & \seqnum{A069091} & \seqnum{A255915}\\
Jordan function ($J_7$) & \seqnum{A069092} & \\
Jordan function ($J_8$) & \seqnum{A069093} & \\
Jordan function ($J_9$) & \seqnum{A069094} & \\
Jordan function ($J_{10}$) & \seqnum{A069095} & \\
$\gcd_2(n)$ & \seqnum{A000034} & \\
$\gcd_3(n)$ & \seqnum{A109007} & \\
$\gcd_4(n)$ & \seqnum{A109008} & \\
$\gcd_5(n)$ & \seqnum{A109009} & \\
$\gcd_6(n)$ & \seqnum{A089128} & \\
$\gcd_7(n)$ & \seqnum{A109010} & \\
$\gcd_8(n)$ & \seqnum{A109011} & \\
Highest power of 2 dividing $n$ & \seqnum{A006519} &  \seqnum{A082907}\\
Highest power of 3 dividing $n$ & \seqnum{A038500} & \seqnum{A242849}\\
Highest power of 5 dividing $n$ & \seqnum{A060904} &  \seqnum{A254609}\\
Highest power of 7 dividing $n$ &  & \\
Highest power of 11 dividing $n$ &  &  \\
Odd part of $n$ & \seqnum{A000265} & \\
Remove 3's from $n$ & \seqnum{A038502} &\\
Largest divisor of $n$ not divisible by 5 & \seqnum{A132739} &\\
Largest divisor of $n$ not divisible by 7 & \seqnum{A242603} &\\
Replace primes factor of n by 2: $a(n)=2^{\Omega(n)}$ & \seqnum{A061142} &\\
Completely multiplicative with $f(p)=p\#$ & \seqnum{A108951} &\\
\end{tabular}
\end{center}
}

The following table lists sequences that have integral generalized binomial coefficients by Theorem \ref{thmward} but that are not multiplicative and divisible. Again we include their OEIS entry and triangle of associated coefficients.

{\footnotesize
\begin{center}
\renewcommand\arraystretch{1.4}

\begin{tabular}{p{3in}|p{.55in}|p{.75in}}
Name, Description, or \newline Formula & OEIS\newline Entry & Generalized \newline binomial \newline coefficients\\

\hline
Fibonacci numbers & \seqnum{A000045} & \seqnum{A010048} \\
Pell numbers & \seqnum{A000129} & \seqnum{A099927}\\ 
Highest power of 4 dividing $n$ & \seqnum{A234957} & \seqnum{A243756}\\
Highest power of 6 dividing $n$ & \seqnum{A234959} & \seqnum{A254730}\\
Highest power of 8 dividing $n$ &  & \\
Highest power of 9 dividing $n$ &  & \\
Remove factors of 2 and 3 not contributing to 6 & \seqnum{A214681} & \\
Remove factors of 2 not contributing to 4 & \seqnum{A214682} & \\
Remove factors of 2, 3, 5 not contributing to 30 & \seqnum{A214685} & \\
Denominators of even Bernoulli numbers & \seqnum{A002445} & \\
Denominators of Bernoulli numbers (variant) & \seqnum{A141056} &\\
\end{tabular}
\end{center}
}

\vspace{.2in}

We note that generating the triangle of generalized binomial coefficients using the definition is inefficient. However, it turns out that there is a relatively simple recurrence relation that all generalized binomial coefficients satisfy (similar to Pascal's identity for classical binomial coefficients).

\begin{theorem}
\label{recurrelation}
\label{recurrence}
Let $f:\mathbb{N}\to\mathbb{N}$ be a nonzero integer sequence, and let $m, n\in\mathbb{N}$ with $n\leq m$. Then
$$
{{m}\choose{n}}_f=\frac{nf(m)}{mf(n)}{{m-1}\choose{n-1}}_f+\frac{(m-n)f(m)}{mf({m-n})}{{m-1}\choose{n}}_f.$$
\end{theorem}

\begin{proof}
This follows by definition since the right hand side is given by
$$\frac{nf(m)\prod_{i=1}^{m-1}f(i)}{mf(n)\left(\prod_{i=1}^{n-1}f(i)\right)\left(\prod_{i=1}^{m-n}f(i)\right)}+\frac{(m-n)f(m)\prod_{i=1}^{m-1}f(i)}{mf(m-n)\left(\prod_{i=1}^{n}f(i)\right)\left(\prod_{i=1}^{m-n-1}f(i)\right)}$$
which simplifies to 
$$\frac{n\prod_{i=1}^{m}f(i)}{m\left(\prod_{i=1}^{n}f(i)\right)\left(\prod_{i=1}^{m-n}f(i)\right)}+\frac{(m-n)\prod_{i=1}^{m}f(i)}{m\left(\prod_{i=1}^{n}f(i)\right)\left(\prod_{i=1}^{m-n}f(i)\right)}.$$
The result now follows since $\frac{n}{m}+\frac{m-n}{m}=1$.
\end{proof}

We note that the previous theorem is true for all integer sequences (not only those considered in this paper). However, the results are typically not integral. Moreover, this theorem cannot be used to prove integrality of the coefficients because the expressions $\frac{nf(m)}{mf(n)}$ and $\frac{(m-n)f(m)}{mf(m-n)}$ are rarely integral. Using this theorem does allow for efficient computation of the triangle of generalized binomial coefficients, though.

Finally, the result in the previous theorem may be concisely given by the relation
$$\frac{m}{f(m)}{{m}\choose{n}}_f=\frac{n}{f(n)}{{m-1}\choose{n-1}}_f+\frac{m-n}{f(m-n)}{{m-1}\choose{n}}_f.$$

\bibliographystyle{plain}
\begin{thebibliography}{1}

\bibitem{edgarMAA}
Tyler Ball, Tom Edgar, and Daniel Juda,
\newblock Dominance orders, generalized binomial coefficients, and {K}ummer's
  theorem,
\newblock {\em Math. Mag.}, {\bf 87} (2014), 135--143.

\bibitem{Car1913}
R.~D. Carmichael,
\newblock On the numerical factors of the arithmetic forms $\alpha^n \pm
  \beta^n$,
\newblock {\em Ann. of Math.}, {\bf 15} (1913-1914), 30--48.

\bibitem{dyer}
Matthew J. Dyer,
\newblock Rank two detection of singularities of {S}chubert varieties, preprint, 2001.
\newblock Available at \url{http://www.nd.edu/\textasciitilde dyer/papers/ranktwo.pdf}.

\bibitem{Edg14}
Tom Edgar,
\newblock Totienomial coefficients,
\newblock {\em Integers}, {\bf 14} (2014), Paper A62.

\bibitem{KnWi89}
Donald~E. Knuth and Herbert~S. Wilf,
\newblock The power of a prime that divides a generalized binomial coefficient,
\newblock {\em J. Reine Angew. Math.}, {\bf 396} (1989), 212--219.

\bibitem{OEIS15}
The OEIS Foundation~Inc.,
\newblock {\em The On-Line Encyclopedia of Integer Sequences},  \\
\newblock \url{http://oeis.org}.

\bibitem{ward}
Morgan Ward,
\newblock A note on divisibility sequences,
\newblock {\em Bull. Amer. Math. Soc.}, {\bf 45} (1939), 334--336.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}: Primary 11B65; Secondary 05A10, 11A05.

\noindent \emph{Keywords:} multiplicative function, divisible function,
generalized binomial coefficient, Kummer's theorem, Fuss-Catalan
number.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000010},
\seqnum{A000027},
\seqnum{A000034},
\seqnum{A000045},
\seqnum{A000129},
\seqnum{A000188},
\seqnum{A000265},
\seqnum{A000290},
\seqnum{A000578},
\seqnum{A001615},
\seqnum{A002445},
\seqnum{A002618},
\seqnum{A003557},
\seqnum{A003958},
\seqnum{A003959},
\seqnum{A003961},
\seqnum{A006519},
\seqnum{A007318},
\seqnum{A007434},
\seqnum{A007947},
\seqnum{A008459},
\seqnum{A008833},
\seqnum{A010048},
\seqnum{A022998},
\seqnum{A026741},
\seqnum{A034444},
\seqnum{A038500},
\seqnum{A038502},
\seqnum{A046951},
\seqnum{A047994},
\seqnum{A048804},
\seqnum{A059376},
\seqnum{A059377},
\seqnum{A059378},
\seqnum{A060594},
\seqnum{A060904},
\seqnum{A061142},
\seqnum{A064549},
\seqnum{A069091},
\seqnum{A069092},
\seqnum{A069093},
\seqnum{A069094},
\seqnum{A069095},
\seqnum{A082907},
\seqnum{A089128},
\seqnum{A099927},
\seqnum{A108951},
\seqnum{A109007},
\seqnum{A109008},
\seqnum{A109009},
\seqnum{A109010},
\seqnum{A109011},
\seqnum{A132739},
\seqnum{A141056},
\seqnum{A173557},
\seqnum{A181543},
\seqnum{A191414},
\seqnum{A214281},
\seqnum{A214681},
\seqnum{A214682},
\seqnum{A214685},
\seqnum{A234957},
\seqnum{A234959},
\seqnum{A238453},
\seqnum{A238498},
\seqnum{A238688},
\seqnum{A238743},
\seqnum{A238754},
\seqnum{A239633},
\seqnum{A239702},
\seqnum{A242603},
\seqnum{A242849},
\seqnum{A243756},
\seqnum{A246465},
\seqnum{A254609},
\seqnum{A254730},
\seqnum{A255914},
\seqnum{A255915}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received September 17 2015;
revised versions received  December 10 2015; December 17 2015.
Published in {\it Journal of Integer Sequences}, December 18 2015.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}