\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\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}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\underline{#1}}}
\usepackage{tikz}
\usetikzlibrary{arrows.meta}
\DeclareMathOperator{\trace}{tr}
\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}
\newtheorem{observation}[theorem]{Observation}
\input{butler-pics}
\begin{center}
\vskip 1cm{\LARGE\bf Enumerating Multiplex Juggling Patterns}
\vskip 1cm \large
Steve Butler\\
Department of Mathematics\\
Iowa State University\\
Ames, IA 50011\\
USA\\
\href{mailto:butler@iastate.edu}{\tt butler@iastate.edu}\\
\ \\
Jeongyoon Choi, Kimyung Kim, and Kyuhyeok Seo\\
Gyeonggi Science High School for the Gifted\\ Gyeonggi Province\\
Republic of Korea
\end{center}
\vskip .2 in
\begin{abstract}
A classic problem in the mathematics of juggling is to give a basic enumeration of the number of juggling patterns. This has been solved in the case when at most one ball is caught/thrown at a time, with the simplest proof being due to Ehrenborg and Readdy by the use of cards.
We introduce a new set of cards that can be used to count multiplex juggling patterns (when multiple balls can be caught/thrown at a time). This set of cards models the correct behavior and avoids the problems of ambiguity; on the other hand the cards are no longer independent. By use of the transfer matrix method combined with the cards we enumerate multiplex juggling patterns with exactly $b$ balls and hand capacity $\kappa$, and include data for $\kappa=2,3$, and establish some combinatorial properties of the cards.
\end{abstract}
\section{Introduction}
While mathematics and juggling have existed independently for thousands of years, it has only been in the last thirty years that the mathematics of juggling has become a subject in its own right (for a general introduction see Polster \cite{P}). Several different approaches for describing juggling patterns have been used. The best-known method is siteswap which gives information what to do with the ball that is in your hand at the given moment, in particular how ``high'' you should throw the ball (see \cite{BEGW,P}). For theoretical and enumeration purposes a more useful method is to describe patterns by the use of cards. This was first introduced in the work of Ehrenborg and Readdy \cite{ER} (see also Stadler \cite{Stadler}), and modified by Butler, Chung, Cummings and Graham \cite {BCCG}.
Juggling cards focus on the \emph{relative order} of when the balls will land should we stop juggling at a given moment. Every throw then has the affect of (possibly) changing the relative ordering of the balls. However, we can only affect the order of a ball that is thrown; the remaining balls will still have the remaining relative order to each other. As a consequence if there are $b$ balls, then there are $b+1$ different reorderings which can occur. Namely, we do not throw a ball (the ``$+1$'') or we throw a ball so that it will land in some order relative to the other $b-1$ balls (which can be done in $b$ ways). The four different cards for the case $b=3$ are shown in Figure~\ref{fig:BasicCards} (in all drawings of cards the circle at the bottom indicates the hand which either does not catch the ball at that ``beat'' or catches and throws affecting the relative ordering of the ball(s); we will always think of time moving from left to right).
\begin{figure}[htb!]
\centering
\picCa \hfil \picCb \hfil \picCc \hfil \picCd
\caption{Possible juggling cards for at most three balls.}
\label{fig:BasicCards}
\end{figure}
The advantage of working with cards is that the cards can work independently of each other. In other words, the choice of card to use at a given time is not dependent on the preceding choice of cards. In siteswap the opposite is true in that you must know all preceding throws to determine which throws are possible at a given time.
Given a set of these $n$ cards for a given $b$ we can repeat these periodically to form a pattern. Moreover, every possible juggling sequence with period $n$ and \emph{at most} $b$ balls will occur as a unique combination of these cards (see \cite{BCCG,P}). Therefore the number of different juggling sequences of period $n$ for exactly $b$ balls is given by
\[
(b+1)^n-b^n,
\]
the number of ways to arrange $n$ cards so that at least once the top ball will move down (and hence all balls will be caught). The count $(b+1)^n$ is the number of juggling sequences with at most $b$ balls.
If we want to find all of the juggling patterns of \emph{minimal} period $n$ (i.e., the shortest time interval it takes for the juggling pattern to repeat) and using exactly $b$ balls we can then use M\"obius inversion and divide out by the period to get
\[
\frac1n\sum_{d\mid n}\mu({\textstyle\frac{n}{d}})\big((b+1)^d-b^d\big),
\]
where $\mu$ is the M\"obius function (see \cite{BEGW}). We will revisit this with more detail in Section~\ref{sec:counts}. (We differentiate a juggling sequence from a juggling pattern by noting that a juggling pattern is not time dependent, i.e., if we shift time by $1$ unit it is still the same pattern, but it might not be the same sequence.)
For as long as there has been interest in the mathematics of juggling, there has been interest in extending results to multiplex juggling (where more than one ball is allowed to be caught at a time). In Ehrenborg and Readdy \cite{ER} they produced possible cards for multiplex juggling. For these cards, multiple balls could come down at a given time and would then be redistributed appropriately. While these cards can describe every juggling pattern there is the problem that uniqueness is lost (see Figure~\ref{fig:nonunique} for an example of two consecutive cards describing the same pattern but using different cards; note these cards are mirrored from the form of the cards given in Ehrenborg and Readdy \cite{ER}). So these do not form a bijection with the number of juggling sequences.
\begin{figure}[htb!]
\centering
\picERc \picERa \hfil \picERd \picERa
\caption{Ambiguity arising from using cards of Ehrenborg and Readdy \cite{ER}.}
\label{fig:nonunique}
\end{figure}
One approach is to distinguish the balls which come down. This is what was done in Butler, Chung, Cummings, and Graham \cite{BCCG}, an example of such a card is shown in Figure~\ref{fig:separate}. This avoids ambiguity that might arise but does not accurately reflect multiplex juggling in practice. Rather this reflects passing patterns with multiple jugglers involved, and each juggler catching one ball (in particular the different points that come down correspond to the different jugglers).
\begin{figure}[htb!]
\centering
\picBCCGa
\caption{An example of a card used in Butler, Chung, Cummings, and Graham \cite{BCCG}.}
\label{fig:separate}
\end{figure}
In this paper we will propose a new type of card which can be used for multiplex juggling. It avoids the ambiguity problem of Ehrenborg and Readdy and also avoids the modeling problem of Butler, Chung, Cummings, and Graham. However it does come at the cost of having a card being dependent on the \emph{previous} card which came before. In Section~\ref{sec:cards} we will introduce these cards, and in Section~\ref{sec:graph} we show how to use matrices associated with a weighted graph to count the number of periodic card sequences of length $n$. We then count the number of juggling sequences and the number of juggling patterns in Section~\ref{sec:properties} and Section~\ref{sec:counts}. In Section~\ref{sec:hand} we will consider what happens when we limit the number of balls which can be thrown. We will give some concluding remarks in Section~\ref{sec:conclusion}, including a discussion of counting crossing numbers.
We will also see that the objects generated in the process of deriving our count seem to have independent combinatorial interest. Moreover, while our main goal has been to enumerate juggling patterns, the cards themselves might be useful for the exploration of other combinatorial aspects of juggling.
Finally, we note that while there has some been interest in counting multiplex juggling patterns, prior to this paper there has been little success. Butler and Graham \cite{BG} made the most progress but their focus was on counting closed walks in a state graph and were not able to efficiently enumerate all juggling patterns.
\section{Cards for multiplex juggling}\label{sec:cards}
The way that cards describe juggling patterns is through understanding the relative order of their landing times. The ambiguity that appeared in Figure~\ref{fig:nonunique} comes from the fact that two balls are landing \emph{together} but still being kept \emph{separate} in the ordering. Since they are separate we could order them in two ways but that does not affect the pattern. This suggests the following simple fix: tracks in the cards no longer represent individual balls, but rather groups of balls which will land together. So now either the ``lowest'' group does not land, or the lowest group lands and the balls get thrown so that they are placed in a new track(s) and/or added to an existing track(s).
Before each throw we will have a composition (or ordered partition) of the number of balls $b$ on the left of the card. We will call this the \emph{arrival composition}, i.e., $(q_1,q_2,\ldots,q_k)$ which corresponds to the statement that were we to stop juggling we would first have $q_1$ balls land together at some point; then $q_2$ balls land together some time later; and so on until finally $q_k$ balls land together at the end. (Note that we do not claim that they will land one time step apart from each other; cards are keeping track of relative ordering of when things land and not the absolute times that they will land.)
After each throw we will have another composition of $b$ on the right of the card. We will call this the \emph{departure composition}, i.e., $(r_1,r_2,\ldots,r_\ell)$. The number of parts in the arrival and departure compositions need not be the same, but we must have $\ell\ge k-1$. If the bottom track of balls land, then the card indicates how the $q_1$ balls get redistributed to the departure composition. Examples of these cards are shown in Figure~\ref{fig:multicards} where the first card corresponds to going from $(2,1,1)$ back to $(2,1,1)$ and the second corresponds to going from $(2,2,1)$ to $(1,2,2)$.
\begin{figure}[H]
\centering
\begin{tabular}{c@{\qquad}c}
\picJUGA & \picJUGB\\
\begin{tikzpicture}[scale=0.4]
\fill[color=black!50!white,rounded corners] (0,0) rectangle (1,1) (0,1) rectangle (1,2);
\draw[thick,rounded corners] (0,2) rectangle (1,3) (0,1) rectangle (1,2) (0,0) rectangle (1,1) (1,0) rectangle (2,1);
\end{tikzpicture}&
\begin{tikzpicture}[scale=0.4]
\fill[color=black!50!white,rounded corners] (0,1) rectangle (1,2) (1,1) rectangle (2,2) (0,2) rectangle (1,3);
\draw[thick, rounded corners] (0,0) rectangle (1,1) (0,1) rectangle (1,2) (1,1) rectangle (2,2) (0,2) rectangle (1,3) (1,2) rectangle (2,3);
\end{tikzpicture}
\end{tabular}
\caption{Examples of cards which we use to model multiplex juggling, and corresponding embeddings.}
\label{fig:multicards}
\end{figure}
\begin{definition}
A composition $(q_1,q_2,\ldots,q_k)$ can be \emph{nontrivially embedded} into a composition $(r_1,r_2,\ldots,r_\ell)$ if there exists indices $1\le i_2< i_3<\cdots< i_k\le\ell$ so that $q_j\le r_{i_j}$ for $2\le j\le k$. Nontrivial embeddings may not be unique. A composition $(q_1,q_2,\ldots,q_k)$ can be \emph{trivially embedded} into a composition $(r_1,r_2,\ldots,r_\ell)$ if and only if $(q_1,q_2,\ldots,q_k) = (r_1,r_2,\ldots,r_\ell)$.
\end{definition}
For every nontrivial embedding of $(q_1,q_2,\ldots,q_k)$, a composition of $b$, into $(r_1,r_2,\ldots,r_\ell)$, another composition of $b$, we have a unique card for multiplex juggling where a throw occurred. As an example in Figure~\ref{fig:multicards} we have also marked underneath how $(q_1,q_2,\ldots,q_k)$ embeds into $(r_1,r_2,\ldots,r_\ell)$ by drawing the partition of $(r_1,r_2,\ldots,r_\ell)$ arranged from $r_1$ on the bottom to $r_\ell$ on the top and shading where $q_2,\ldots,q_k$ sits inside the partition. Trivial embeddings, i.e., $(q_1,q_2,\ldots,q_k)=(r_1,r_2,\ldots,r_\ell)$, correspond to no throws. All possible cards (and corresponding embeddings) for multiplex juggling for up to $b=3$ balls are shown in Figure~\ref{fig:3ballcards}.
\begin{figure}[htb!]
\centering
\begin{tabular}{|c|c|c|c|c|c|}
\hline \vphantom{-}&&&&&\\
\picJPaa&\picJPab&\picJPac&\picJPad&\picJPae&\picJPaf\\
\partpicA&\partpicB&\partpicC&\partpicD&\partpicE&\partpicF\\ \hline \vphantom{-}&&&&&\\
\picEXg&\picEXf&\picEXe&\picJPbd&\picEXa&\picEXb\\
\partpicG&\partpicH&\partpicI&\partpicJ&\partpicK&\partpicL\\ \hline \vphantom{-}&&&&&\\
\picEXc&\picEXd&\picEXh&\picJPcd&\picJPce&\picJPcf\\
\partpicM&\partpicN&\partpicO&\partpicP&\partpicQ&\partpicR\\ \hline \vphantom{-}&&&&&\\
\picJPda&\picJPdb&\picJPdc&\picJPdd&\picJPde&\picJPdf\\
\partpicS&\partpicT&\partpicU&\partpicV&\partpicW&\partpicX\\ \hline
\end{tabular}
\caption{All cards and corresponding embeddings of compositions for $b=3$ balls.}
\label{fig:3ballcards}
\end{figure}
We can now determine the number of cards involved by examining their interpretation using embeddings of compositions.
\begin{lemma}\label{lem:right}
The total number of ways that a composition $(r_1,r_2,\ldots,r_\ell)$ can have a composition embedded inside is
\[
\prod_i(r_i+1).
\]
Equivalently this is the number of cards where $(r_1,r_2,\ldots,r_\ell)$ is the departure composition.
\end{lemma}
\begin{proof}
We can think of shading the whole composition then removing parts of it as desired. In particular for every part $r_i$ the embedding can use any of $0,1,\ldots,r_i$ in that slot. In particular for the $i$th part there are $r_i+1$ choices and these can be made independently of each other. Therefore there are $(r_1+1)(r_2+1)\cdots(r_\ell+1)$ possible embeddings.
\end{proof}
\begin{lemma}\label{lem:left}
The total number of ways that a composition $(q_1,q_2,\ldots,q_k)$ can be embedded into a composition is
\[
1+\frac{q_1+2k-2}{q_1+k-1}{q_1+k-1 \choose k-1}2^{q_1-1}.
\]
Equivalently this is the number of cards where $(q_1,q_2,\ldots,q_k)$ is the arrival composition.
\end{lemma}
\begin{proof}
Suppose that a throw happens, so $q_1$ balls come down and get redistributed, possibly adding balls to existing groups to land (i.e., adding to one of the $q_i$) or creating new groups to land. Suppose that the composition we embed into has $(k-1)+\ell$ different parts, where $0\le \ell\le q_1$. This can happen in
\[
{k-1+\ell\choose \ell}{k+q_1-2\choose q_1-\ell}=\frac{\ell+k-1}{q_1+k-1}{q_1\choose \ell}{q_1+k-1\choose k-1}
\]
different ways. The ${k-1+\ell\choose \ell}$ divides the parts as coming from an existing part (e.g., $q_i$) or being newly created. For the $\ell$ new parts we first need to get a contribution of $1$ coming from $q_1$ leaving $q_1-\ell$ available to distribute among the $k-1+\ell$ different parts arbitrarily which can be done in ${k+q_1-2\choose q_1-\ell}$ ways. Finally, we can perform some simple manipulation of binomial coefficients.
Putting this together we have that the total number of ways that $(q_1,q_2,\ldots,q_k)$ can be embedded into another composition by a throw is
\begin{align*}
\sum_{\ell=0}^{q_1}\frac{\ell+k-1}{q_1+k-1}{q_1\choose \ell}{q_1+k-1\choose k-1}
&=\frac{1}{q_1+k-1}{q_1+k-1\choose k-1}\sum_{\ell=0}^{q_1}(\ell+k-1){q_1\choose \ell}\\
&=\frac{1}{q_1+k-1}{q_1+k-1\choose k-1}\bigg(\sum_{\ell=0}^{q_1}\ell{q_1\choose \ell}
+\sum_{\ell=0}^{q_1}(k-1){q_1\choose \ell}\bigg)\\
&=\frac{1}{q_1+k-1}{q_1+k-1\choose k-1}\big(q_12^{q_1-1}+(k-1)2^{q_1}\big)\\
\\
&=\frac{q_1+2k-2}{q_1+k-1}{q_1+k-1 \choose k-1}2^{q_1-1}.
\end{align*}
Combining this with the ``$+1$'' from the trivial embedding and the result follows.
\end{proof}
We can now determine the total number of cards, or equivalently the total number of embeddings possible. Starting with $b=0$ the numbers are
\[
1,
~2,
~7,
~24,
~82,
~280,
~956,
~3264,
~11144,
~38048,
~129904,
~443520,
~1514272,\ldots.
\]
This is sequence \seqnum{A003480} in the OEIS \cite{OEIS} which is initiated with $a_0=1$, $a_1=2$ and $a_2=7$ and for $b\ge 3$ we have $a_b=4a_{b-1}-2a_{b-2}$.
\begin{theorem}\label{thm:cardrecurse}
If $a_b$ is the number of possible cards used for describing multiplex juggling with $b$ balls, then $a_1=2$, $a_2=7$, and for $b\ge 3$ we have $a_b=4a_{b-1}-2a_{b-2}$.
\end{theorem}
\begin{proof}
Verification of $a_1$ and $a_2$ can be done by examining Figure~\ref{fig:3ballcards}, so it remains to establish the recursion.
We can count the number of cards by breaking our count up according to the departure composition using Lemma~\ref{lem:right}. In particular we have
\begin{equation}\label{eq:ab}
a_b=\sum_{(r_1,r_2,\ldots)\in\mathcal{R}_b}\prod_{i\ge1}(r_i+1),
\end{equation}
where $\mathcal{R}_b$ are all of the compositions of $b$.
We now further break up this count by combining the compositions according to the size of the first part which can be anything from $1$ to $b$. So we have
\begin{align*}
a_b&=\sum_{j=1}^b\bigg(\sum_{(j,r_2,\ldots)\in\mathcal{R}_b}(j+1)\prod_{i\ge 2}(r_i+1)\bigg)\\
&=\sum_{j=1}^b(j+1)\bigg(\sum_{(r_2,\ldots)\in\mathcal{R}_{b-j}}\prod_{i\ge 2}(r_i+1)\bigg)\\
&=\sum_{j=1}^b(j+1)a_{b-j},
\end{align*}
where in the last step we note that we have the form of \eqref{eq:ab}.
To finish we have
\begin{align*}
a_b-2a_{b-1}+a_{b-2}&=
\sum_{j=1}^b(j+1)a_{b-j}
-2\sum_{j=1}^{b-1}(j+1)a_{b-1-j}
+\sum_{j=1}^{b-2}(j+1)a_{b-2-j}\\
&=\sum_{k=1}^b(k+1)a_{b-k}
-2\sum_{k=2}^{b}ka_{b-k}
+\sum_{k=3}^{b}(k-1)a_{b-k}\\
&=2a_{b-1}-a_{b-2}.
\end{align*}
Here we reindex the three sums to be consistent and then note that all but the first two terms will drop out. Rearranging we conclude $a_b=4a_{b-1}-2a_{b-2}$, as desired.
\end{proof}
\section{Combining cards by taking walks in a graph}\label{sec:graph}
The advantage to using cards in order to describe juggling patterns was the ability to have the current card be chosen independently of all other cards. With these new cards for multiplex juggling we now have to be careful in that the choice of our current card is dependent on the previous card. Namely, the departure composition of the previous card must match the arrival composition of the current card. Moreover if we are forming a pattern with period $n$ we need to make sure that our last card will also be consistent with our first card (so that we can repeat the pattern).
To help achieve this we will construct a directed multi-graph $\mathcal{G}_b$ by letting the vertices of $\mathcal{G}_b$ be the compositions of $b$; and for each card we add a directed edge from the arrival composition to the departure composition.
\begin{observation}\label{obs:bijection}
There is a one-to-one correspondence between periodic sequences using $n$ cards and closed walks of length $n$ in the graph. In particular, to count the number of periodic sequences using $n$ cards it suffices to count the number of closed walks of length $n$.
\end{observation}
This follows by noting that each card is an edge and if two cards are used sequentially then the edges also occur sequentially in the graph, giving the correspondence between sequences of consecutive cards and walks in the graph. Moreover the fact that we can repeat the pattern periodically indicates that we must return to the same composition that we started with, so the walk is closed.
We now can use the transfer matrix method (see Stanley \cite[Ch.\ 4.7]{S}).
\begin{theorem}[Transfer matrix method]\label{thm:walks}
Given a directed multi-graph $\mathcal{G}$ let $A$ be the matrix with rows and columns indexed by the vertices with $A_{uv}$ equal to the number of directed arcs from $u\to v$. Then $\trace(A^n)$ equals the number of closed walks of length $n$ in the graph.
\end{theorem}
Let $A_b$ be the matrix associated with the graph $\mathcal{G}_b$. We have $A_0=(1)$, $A_1=(2)$,
\[
A_2=\begin{array}{r}(2)\\(1,1)\end{array}\left(\begin{array}{cc}
2 & 1 \\
1 & 3
\end{array}\right),\qquad
A_3=
\begin{array}{r}(3)\\(2,1)\\(1,2)\\(1,1,1)\end{array}\left(\begin{array}{cccc}
2 & 1 & 1 & 1 \\
1 & 3 & 2 & 3 \\
1 & 1 & 2 & 0 \\
0 & 1 & 1 & 4
\end{array}\right),
\]
and
\[
A_4=
\begin{array}{r}(4)\\(3,1)\\(1, 3)\\(2, 1, 1)\\(2, 2)\\(1, 2, 1)\\(1, 1, 2)\\(1, 1, 1, 1)\end{array}\left(\begin{array}{cccccccc}
2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 3 & 2 & 3 & 2 & 3 & 3 & 4 \\
1 & 1 & 2 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 4 & 1 & 3 & 3 & 6 \\
1 & 1 & 1 & 1 & 3 & 1 & 1 & 0 \\
0 & 1 & 0 & 2 & 1 & 2 & 0 & 0 \\
0 & 0 & 1 & 0 & 1 & 1 & 3 & 0 \\
0 & 0 & 0 & 1 & 0 & 1 & 1 & 5
\end{array}\right),
\]
where on the left we have marked the compositions that correspond to the vertex. For reference we also give the graphs $\mathcal{G}_0$, $\mathcal{G}_1$, $\mathcal{G}_2$, $\mathcal{G}_3$ in Figure~\ref{fig:graphs}.
\begin{figure}[H]
\centering
\begin{tabular}{c@{\qquad\qquad}c@{\qquad\qquad}c@{\qquad\qquad}c}
\begin{tikzpicture}
\node[draw, rectangle, rounded corners, inner sep=2pt] (a) at (0,0) {$\emptyset$};
\draw[-{>[scale=1.25]},thick,shorten >=2pt,shorten <=2pt, rounded corners] (a) -- (0.75,0)--(0.75,0.75) node[circle,draw,thick, fill=white, inner sep = 1pt] {\small $1$} --(0,0.75)--(a);
\end{tikzpicture}
&
\begin{tikzpicture}
\node[draw, rectangle, rounded corners, inner sep=2pt] (a) at (0,0) {$(1)$};
\draw[-{>[scale=1.25]},thick,shorten >=2pt,shorten <=2pt, rounded corners] (a) -- (0.75,0)--(0.75,0.75) node[circle,draw,thick, fill=white, inner sep = 1pt] {\small $2$} --(0,0.75)--(a);
\end{tikzpicture}
&
\begin{tikzpicture}
\node[draw, rectangle, rounded corners, inner sep=2pt] (a) at (0,0) {$(1,1)$};
\node[draw, rectangle, rounded corners, inner sep=2pt] (b) at (0,2) {$(2)$};
\draw[-{>[scale=1.25]},thick,shorten >=2pt,shorten <=2pt, rounded corners] (a) -- (0.75,0)--(0.75,-0.75) node[circle,draw,thick, fill=white, inner sep = 1pt] {\small $3$} --(0,-0.75)--(a);
\draw[-{>[scale=1.25]},thick,shorten >=2pt,shorten <=2pt, rounded corners] (b) -- (0.75,2)--(0.75,2.75) node[circle,draw,thick, fill=white, inner sep = 1pt] {\small $2$} --(0,2.75)--(b);
\draw[-{>[scale=1.25]},thick,shorten >=2pt,shorten <=2pt, rounded corners] (b) to (0.25,1) node[circle,draw,thick, fill=white, inner sep = 1pt] {\small $1$} to (a);
\draw[-{>[scale=1.25]},thick,shorten >=2pt,shorten <=2pt, rounded corners] (a) to (-0.25,1) node[circle,draw,thick, fill=white, inner sep = 1pt] {\small $1$} to (b);
\end{tikzpicture}
&
\begin{tikzpicture}
\node[draw, rectangle, rounded corners, inner sep=2pt] (a) at (0,0) {$(3)$};
\node[draw, rectangle, rounded corners, inner sep=2pt] (b) at (3,0) {$(1,2)$};
\node[draw, rectangle, rounded corners, inner sep=2pt] (c) at (3,3) {$(1,1,1)$};
\node[draw, rectangle, rounded corners, inner sep=2pt] (d) at (0,3) {$(2,1)$};
\draw[-{>[scale=1.25]},thick,shorten >=2pt,shorten <=2pt, rounded corners] (a) -- (-0.75,0)--(-0.75,-0.75) node[circle,draw,thick, fill=white, inner sep = 1pt] {\small $2$} --(0,-0.75)--(a);
\draw[-{>[scale=1.25]},thick,shorten >=2pt,shorten <=2pt, rounded corners] (d) -- (-0.75,3)--(-0.75,3.75) node[circle,draw,thick, fill=white, inner sep = 1pt] {\small $3$} --(0,3.75)--(d);
\draw[-{>[scale=1.25]},thick,shorten >=2pt,shorten <=2pt, rounded corners] (b) -- (3.75,0)--(3.75,-0.75) node[circle,draw,thick, fill=white, inner sep = 1pt] {\small $2$} --(3,-0.75)--(b);
\draw[-{>[scale=1.25]},thick,shorten >=2pt,shorten <=2pt, rounded corners] (c) -- (4,3)--(4,3.75) node[circle,draw,thick, fill=white, inner sep = 1pt] {\small $4$} --(3,3.75)--(c);
\draw[-{>[scale=1.25]},thick,shorten >=2pt,shorten <=2pt, rounded corners]
(a) to (1.5,0.3) node[circle,draw,thick, fill=white, inner sep = 1pt] {\small $1$} to (b);
\draw[-{>[scale=1.25]},thick,shorten >=2pt,shorten <=2pt, rounded corners]
(b) to (1.5,-0.3) node[circle,draw,thick, fill=white, inner sep = 1pt] {\small $1$} to (a);
\draw[-{>[scale=1.25]},thick,shorten >=2pt,shorten <=2pt, rounded corners]
(a) to (-0.3,1.5) node[circle,draw,thick, fill=white, inner sep = 1pt] {\small $1$} to (d);
\draw[-{>[scale=1.25]},thick,shorten >=2pt,shorten <=2pt, rounded corners]
(d) to (0.3,1.5) node[circle,draw,thick, fill=white, inner sep = 1pt] {\small $1$} to (a);
\draw[-{>[scale=1.25]},thick,shorten >=2pt,shorten <=2pt, rounded corners]
(a) to (1.5,1.5) node[circle,draw,thick, fill=white, inner sep = 1pt] {\small $1$} to (c);
\draw[-{>[scale=1.25]},thick,shorten >=2pt,shorten <=2pt, rounded corners]
(c) to (3,1.5) node[circle,draw,thick, fill=white, inner sep = 1pt] {\small $1$} to (b);
\draw[-{>[scale=1.25]},thick,shorten >=2pt,shorten <=2pt, rounded corners]
(d) to (1.5,3.3) node[circle,draw,thick, fill=white, inner sep = 1pt] {\small $3$} to (c);
\draw[-{>[scale=1.25]},thick,shorten >=2pt,shorten <=2pt, rounded corners]
(c) to (1.5,2.7) node[circle,draw,thick, fill=white, inner sep = 1pt] {\small $1$} to (d);
\draw[-{>[scale=1.25]},thick,shorten >=2pt,shorten <=2pt, rounded corners]
(d) to (1.5,2.1) node[circle,draw,thick, fill=white, inner sep = 1pt] {\small $2$} to (b);
\draw[-{>[scale=1.25]},thick,shorten >=2pt,shorten <=2pt, rounded corners]
(b) to (1.5,0.9) node[circle,draw,thick, fill=white, inner sep = 1pt] {\small $1$} to (d);
\end{tikzpicture}
\\
$\mathcal{G}_0$& $\mathcal{G}_1$& $\mathcal{G}_2$& $\mathcal{G}_3$
\end{tabular}
\caption{The graphs $\mathcal{G}_0$, $\mathcal{G}_1$, $\mathcal{G}_2$ and $\mathcal{G}_3$.}
\label{fig:graphs}
\end{figure}
We note that Lemma~\ref{lem:right} can be used to determine the \emph{column} sums of $A_b$, while Lemma~\ref{lem:left} can be used to determine the \emph{row} sums of $A_b$. Using Theorem~\ref{thm:walks} we also get the sum of all entries of the matrix.
\section{Counting multiplex juggling sequences}\label{sec:properties}
We can combine Observation~\ref{obs:bijection} together with Theorem~\ref{thm:walks} to find the number of periodic sequences of $n$ cards. For each sequence of cards we will get a multiplex juggling sequence. This is done by following the balls thrown in the diagram formed by placing the cards sequentially to see how many time steps in the future each ball will land. Conversely, given a juggling sequence we can determine a set of cards used by determining which groups of balls will land together after every throw \emph{and} consistently choose the same composition for balls not involved.
For a given juggling sequence there can be \emph{multiple} ways in which it can be represented using the cards. (This is different than the case where at most one ball was caught at a time.) The problem lies in what happens with balls that are never used. For instance in Figure~\ref{fig:samesiteswap} we see two distinct sets of three cards which correspond to the same juggling sequence, the difference between them being the tracks in the unused balls.
\begin{figure}[htb!]
\centering
\picWeda \picWedb \picWedc
\hfil
\picWedd \picWede \picWedf
\caption{Two distinct sets of three cards with the same juggling sequence.}
\label{fig:samesiteswap}
\end{figure}
Note that for juggling where at most one ball is caught the unused balls all have the same behavior, in our language they would correspond to lying in tracks with capacity $1$ at the top. So to count the number of juggling sequences we take the difference of the ways to place $n$ cards with $b$ tracks, $(b+1)^n$, and the ways to place $n$ cards with $b-1$ tracks, $b^n,$ (which is in bijection with the number of ways to place $n$ cards with $b$ tracks and the top track is never used). This gives $(b+1)^n-b^n$. We will do something similar with our cards that we are using for multiplex juggling.
\begin{theorem}\label{thm:siteswapcount}
Let $js_b(n)$ be the number of multiplex juggling sequences using exactly $b$ balls and with period $n$. Then
\[
js_b(n) = \trace(A_b^n)-\sum_{i=0}^{b-1}\trace(A_i^n).
\]
\end{theorem}
\begin{proof}
We proceed by induction on $b$. For the base case of $b=0$ there is one card (the empty card) and so for any length $n$ there is exactly one way to position these cards. Since $A_0=(1)$ we have $\trace(A_0^n)=1$ establishing the base case.
Now assume that it works up through $b-1$ and consider the case for $b$. First we observe
\[
\trace(A_{b}^n) = js_{b}(n)+\sum_{i=0}^{b-1}2^{b-i-1}js_i(n).
\]
This follows by noting that for every juggling sequence which uses exactly $i$ balls we can find a sequence of cards corresponding to the compositions of $i$. We can now add $b-i$ balls to the top of each card as long as we do it consistently across the different cards. Moreover the number of different options we have to place the $b-i$ balls equals the number of compositions of $b-i$ which is $2^{b-i-1}$.
Rearranging and using our induction hypothesis we have
\begin{align*}
js_b(n)
&=\trace(A_{b}^n)-\sum_{i=0}^{b-1}2^{b-i-1}js_i(n)\\
&=\trace(A_{b}^n)-\sum_{i=0}^{b-1}2^{b-i-1}\bigg(\trace(A_i^n)-\sum_{j=0}^{i-1}\trace(A_j^n)\bigg)\\
&=\trace(A_{b}^n)-\sum_{i=0}^{b-1}\trace(A_i^n)\bigg(2^{b-i-1}-\sum_{k=0}^{b-i-2}2^k\bigg)\\
&=\trace(A_{b}^n)-\sum_{i=0}^{b-1}\trace(A_i^n),
\end{align*}
establishing the result.
\end{proof}
\section{Counting multiplex juggling patterns}\label{sec:counts}
To go from counting juggling sequences of period $n$ to counting juggling patterns of minimal period $n$ we want to do two things. First we want to remove any pattern that has shorter period (suppose $d$ divides $n$, then any periodic sequence of cards of length $d$ can be repeated $n/d$ times to make a periodic sequence of cards of length $n$). Second we want to divide out by $n$ since in juggling patterns there is no set start time.
For the first issue we can use M\"obius inversion (see \cite{S}). Namely we note that if $ms_b(n)$ is the number of juggling sequences with $b$ balls and minimal period $n$, then
\[
js_b(n) = \sum_{d \mid n}ms_b(d).
\]
So if we let $\mu(\frac{n}{d})$ be the M\"obius function it follows
\[
ms_b(n) = \sum_{d \mid n}\mu({\textstyle\frac{n}{d}})js_b(d).
\]
With this in hand we can now divide out by the rotational symmetry of the starting point and determine the number of juggling patterns with $b$ balls and period $n$ which we denote $jp_b(n)$. Combining the above with Theorem~\ref{thm:siteswapcount} we get the following.
\begin{theorem}\label{thm:jpcount}
The number of multiplex juggling patterns with $b$ balls and minimal period $n$ is
\begin{equation*}
jp_b(n)=\frac1n\sum_{d\mid n}\mu({\textstyle\frac{n}{d}})\bigg(\trace(A_b^d)-\sum_{i=0}^{b-1}\trace(A_i^d)\bigg).
\end{equation*}
\end{theorem}
In Table~\ref{tab:jpcount} we give the number of minimal period juggling patterns for $b=2,3,4,5$ and period at most $15$.
\begin{table}[H]
\centering
\begin{tabular}{|l||r|r|r|r|}\hline
& $b=2$ & $b=3$ & $b=4$ & $b=5$\\ \hline\hline
$n=1$& $2$& $3$& $5$& $7$\\ \hline
$n=2$& $4$& $12$& $32$& $77$\\ \hline
$n=3$& $13$& $63$& $261$& $964$\\ \hline
$n=4$& $37$& $310$& $2089$& $12086$\\ \hline
$n=5$& $118$& $1618$& $17449$& $156975$\\ \hline
$n=6$& $356$& $8434$& $147807$& $2077448$\\ \hline
$n=7$& $1142$& $45142$& $1276577$& $27976399$\\ \hline
$n=8$& $3620$& $243998$& $11169023$& $381752857$\\ \hline
$n=9$& $11744$& $1336644$& $98872035$& $5267354817$\\ \hline
$n=10$& $38275$& $7392117$& $883717142$& $73358245986$\\ \hline
$n=11$& $126234$& $41247234$& $7964898829$& $1029873201879$\\ \hline
$n=12$& $418735$& $231856131$& $72305691686$& $14559160765380$\\ \hline
$n=13$& $1399610$& $1311820110$& $660528998007$& $207076019661773$\\ \hline
$n=14$& $4702499$& $7464002451$& $6067348742573$& $2961063646029819$\\ \hline
$n=15$& $15883190$& $42679372930$& $56002661734041$& $42542385162393167$\\ \hline
\end{tabular}
\caption{The number of multiplex juggling patterns of minimal period $n$ using $b$ balls.}
\label{tab:jpcount}
\end{table}
As a special case of Theorem~\ref{thm:jpcount} we have
\begin{equation}\label{eq:jp1}
jp_b(1)=\trace(A_b)-\sum_{i=0}^{b-1}\trace(A_i).
\end{equation}
We can also compute the number of period one multiplex juggling patterns directly.
\begin{theorem}\label{thm:jp1}
We have $jp_b(1)=p(b)$, where $p(b)$ is the number of partitions of $b$.
\end{theorem}
\begin{proof}
In order for a card to produce a valid multiplex juggling sequence of period one with $b$ balls we must have the arrival and departure compositions of the card be equal. That is $(q_1,q_2,\ldots,q_k)=(r_1,r_2,\ldots,r_k)$. Further we must have that when the $q_1$ balls get distributed some ball gets placed into the top group. This second requirement will force $q_k$ to ``embed'' into $r_{k-1}$ (otherwise it would have to embed into $r_k$ but the placement of at least one more ball in the top group then results in $q_k\ne r_k$). In particular this then forces, in turn, $q_i$ to embed in $r_{i-1}$ for $i=2,\ldots,k$. This is only possible if $q_1\ge q_2\ge\cdots\ge q_k$. Therefore our composition on the sides of the card have the unique ordering from largest to smallest element (e.g., it corresponds to a partition).
Conversely, if we start with a partition we can create a card as above by placing the partition on the sides of the card from largest to smallest; then all but the bottom group will shift down by one while the bottom group will then drop down and redistribute to fill differences as needed. An example of this is shown in Figure~\ref{fig:partition} for the partition $(3,3,2,2)$.
\end{proof}
\begin{figure}[htb!]
\centering
\picThu
\caption{Forming a period one juggling sequence from the partition $(3,3,2,2)$.}
\label{fig:partition}
\end{figure}
\begin{theorem}\label{thm:trace}
Let $p(b)$ denote the number of partitions of $b$. Then
\[
\trace(A_b)=p(b)+\sum_{i=0}^{b-1}2^{b-i-1}p(i).
\]
\end{theorem}
\begin{proof}
Updating equation \eqref{eq:jp1} using Theorem~\ref{thm:jp1} we have
\[
p(b) = \trace(A_b)-\sum_{i=0}^{b-1}\trace(A_i).
\]
We now proceed by induction. We have $\trace(A_0)=1=p(0)$ (note that the sum will be empty and not contribute), establishing the base case. Now suppose that we have established the result up through $b-1$ and consider the case for $b$. We have
\begin{align*}
\trace({A}_b)&=p(b)+\sum_{i=0}^{b-1}\trace(A_i)\\
&=p(b)+p(b-1)+2\sum_{i=0}^{b-2}\trace(A_i)\\
&=p(b)+p(b-1)+2p(b-2)+2^2\sum_{i=0}^{b-3}\trace(A_i)\\
\end{align*}
\begin{align*}
&=\cdots \\
&=p(b)+p(b-1)+2p(b-2)+2^2p(b-3)+\cdots+2^{b-1}p(0)\\
&=p(b)+\sum_{i=0}^{b-1}2^{b-i-1}p(i),
\end{align*}
establishing the result.
\end{proof}
Using this we get that the trace of $A_b$ starting with $b=0$ is
\[
1, ~2, ~5, ~11, ~24, ~50, ~104, ~212, ~431, ~870, ~1752, ~3518, ~7057, ~14138, ~28310, ~56661, \ldots.
\]
This is sequence \seqnum{A090764} in the OEIS \cite{OEIS}. The recurrence that we have derived is a variant of that given in the OEIS. We now give a different variation establishing that this is the same sequence as given in the OEIS.
\begin{theorem}
Let $\mathcal{P}(b)$ be the set of partitions of $b$, and for a partition $q$ let $o(q)$ denote the number of $1$s in the partition. Then
\[
\trace({A}_b)=\sum_{q\in \mathcal{P}(b)}2^{o(q)}.
\]
\end{theorem}
\begin{proof}
We proceed by induction on $b$. The result is easily checked for small cases, so now assume it works up through $b-1$. Then we have the following.
\begin{align*}
\sum_{q \in \mathcal{P}_b}2^{o(q)}&=
\sum_{\substack{q\in\mathcal{P}_b\\ o(q)=0}} 2^{o(q)}+\sum_{\substack{q\in\mathcal{P}_b \\ o(q)>0}}2^{o(q)}\\
&=\sum_{\substack{q\in\mathcal{P}_b\\o(q)=0}} 1+2\sum_{q\in\mathcal{P}_{b-1}}2^{o(q)}\\
&=\big(p(b)-p(b-1)\big)+2\trace(A_{b-1})\\
&=\big(p(b)-p(b-1)\big)+2 \bigg(p(b-1)+\sum_{i=0}^{b-2}2^{b-i-2}p(i)\bigg)\\
&=p(b)+\sum_{i=0}^{b-1}2^{b-i-1}p(i)\\
&=\trace(A_{b}).
\end{align*}
We first divide up our partitions on whether we include a $1$; then we note that there are $p(b)-p(b-1)$ partitions that do not include a $1$ and $p(b-1)$ partitions that do include a $1$ (i.e., taking a partition with $b-1$ we can append a $1$ to get a partition of $b$ which does include a $1$). We apply the induction hypothesis, and then apply Theorem~\ref{thm:trace} once, clean up our sum, and finally apply Theorem~\ref{thm:trace} a second time.
\end{proof}
\section{Juggling patterns with hand capacity}\label{sec:hand}
One of our basic assumptions that we have employed is that we can catch and throw any number of balls at any given step. From a practical standpoint jugglers usually limit themselves to catching and throwing at most two or three balls at a time. The approach outlined above works just as well when we introduce a capacity constraint into how many balls can land at a given time, or equivalently how many balls can be thrown at a given time.
To do this we let $A_{b,\kappa}$ be the principal submatrix of $A_b$ by taking all rows and columns indexed by compositions with all parts of size at most $\kappa$. (Since no arrival composition can have $q_1\ge\kappa$ it follows that any valid juggling sequence can be formed by cards with all parts of size at most $\kappa$.)
\begin{theorem}\label{thm:capacity}
Let $js_{b,\kappa}(n)$ be the number of multiplex juggling sequences using exactly $b$ balls, with period $n$ and all throws involve at most $\kappa$ balls. Then
\begin{equation}\label{eq:capss}
js_{b,\kappa}(n)=\trace(A_{b,\kappa}^n)-\sum_{i=\max\{0,b-\kappa\}}^{b-1}\trace(A_{i,\kappa}^n).
\end{equation}
Let $jp_{b,\kappa}(n)$ be the number of multiplex juggling patterns using exactly $b$ balls, with minimal period $n$ and all throws involve at most $\kappa$ balls. Then
\begin{equation}\label{eq:capjp}
jp_{b,\kappa}(n)=\frac1n\sum_{d\mid n}\mu({\textstyle\frac{n}{d}})\bigg(\trace(A_{b,\kappa}^d)-\sum_{i=\max\{0,b-\kappa\}}^{b-1}\trace(A_{i,\kappa}^d)\bigg).
\end{equation}
\end{theorem}
Before beginning the proof, observe if $\kappa=1$, then this reduces to the case of juggling where at most one ball can be caught at a time (i.e., $A_{b,1}=(b+1)$); and if $\kappa=\infty$ then this is equivalent to what we have already done.
\begin{proof}
We note that \eqref{eq:capjp} follows from \eqref{eq:capss} by applying M\"obius inversion. So it suffices to establish \eqref{eq:capss}.
We proceed by induction on $b$. For the base case of $b=0$ there is one card (the empty card) and the capacity places no restriction on its use, and so for any length there is exactly one way to position these cards. Since $\trace(A_0^n)=1$ this establishes the base case.
Let $r_{i,\kappa}$ be the number of compositions of $i$ with each part at most $\kappa$. By grouping based on the first part (which has size between $1$ and $\kappa$) we have
\begin{equation}\label{eq:rrecur}
r_{i,\kappa}=\sum_{j=1}^{\min\{\kappa,i\}} r_{i-j,\kappa},
\end{equation}
the $\min\{\kappa,i\}$ coming from noting that we cannot have compositions with negative parts and so we need to handle the case of small $i$.
Now assume that we have established the result up through $b-1$ and consider the case for $b$. First we observe
\[
\trace(A_{b,\kappa}^n)=js_{b,\kappa}(n)+\sum_{i=0}^{b-1}r_{b-i,\kappa}js_{i,\kappa}(n).
\]
This follows by noting that for every juggling sequence which uses exactly $i$ balls we can find a sequence of cards which uses exactly $i$ balls. We can now add $b-i$ balls to the top of each card as long as we do it consistently across the different cards. Moreover the number of different options we have to place the $b-i$ balls equals the number of compositions of $b-i$ with each part at most $\kappa$ which is $r_{b-i,\kappa}$.
We have
\begin{align}
js_{b,\kappa}(n)&=
\trace(A_{b,\kappa}^n)-\sum_{i=0}^{b-1}r_{b-i,\kappa}js_{i,\kappa}(n)\notag\\
&=\trace(A_{b,\kappa}^n)-\sum_{i=0}^{b-1}r_{b-i,\kappa}\bigg(\trace(A_{i,\kappa}^n)-\sum_{j=\max\{0,i-\kappa\}}^{i-1}\trace(A_{j,\kappa}^n)\bigg)\label{eq:induction}\\
&=\trace(A_{b,\kappa}^n)-\sum_{i=0}^{b-1}\trace(A_{i,\kappa}^n)\bigg(r_{b-i,\kappa}-\sum_{j=\max\{0,b-i-\kappa\}}^{b-i-1}r_{j,\kappa}\bigg)\label{eq:rearrange}\\
&=\trace(A_{b,\kappa}^n)-\sum_{i=\max\{0,b-\kappa\}}^{b-1}\trace(A_{i,\kappa}^n).\notag
\end{align}
The equality in \eqref{eq:induction} uses the induction hypothesis and the equality in \eqref{eq:rearrange} is due to rearranging the terms. Finally we observe that \eqref{eq:rrecur} indicates that almost all of the terms will cancel, except for the first few initial terms which can easily be checked to be one, establishing the result.
\end{proof}
For reference we have produced the number of multiplex juggling patterns for $\kappa=2$ in Table~\ref{tab:cap2} and for $\kappa=3$ in Table~\ref{tab:cap3}.
We note that we can ask similar questions about the sum of the entries in $A_{b,\kappa}$ as well as the row and column sums as we did with $A_{b}$ (i.e., Lemma~\ref{lem:right}, Lemma~\ref{lem:left} and Theorem~\ref{thm:cardrecurse}). However the counts are less clear, and have not appeared in the OEIS. As an example if we count the total number of cards when $\kappa =2$ we get the following numbers, starting with $b=0$:
\[
1,~2,~7,~17,~41,~91,~195,~403,~812,~1601,~3102,~5922,~11165,~20824,~38477,\ldots.
\]
These numbers do appear to satisfy a relatively simple relationship. In particular through $b=25$ these numbers agree with the following conjecture.
\begin{table}[H]
\centering
\begin{tabular}{|l|r|r|r|r|}\hline
$\kappa=2$ & $b=2$ & $b=3$ & $b=4$ & $b=5$\\ \hline\hline
$n=1$& $2$& $2$& $3$& $3$\\ \hline
$n=2$& $4$& $9$& $18$& $30$\\ \hline
$n=3$& $13$& $47$& $134$& $314$\\ \hline
$n=4$& $37$& $224$& $950$& $3140$\\ \hline
$n=5$& $118$& $1118$& $6938$& $31886$\\ \hline
$n=6$& $356$& $5522$& $50751$& $324909$\\ \hline
$n=7$& $1142$& $27910$& $376402$& $3341566$\\ \hline
$n=8$& $3620$& $141946$& $2813824$& $34605634$\\ \hline
$n=9$& $11744$& $730544$& $21219536$& $360849352$\\
\hline
$n=10$& $38275$& $3790391$& $161190485$& $3785776259$\\
\hline
$n=11$& $126234$& $19827570$& $1232724798$&
$39941119938$\\ \hline
$n=12$& $418735$& $104422007$& $9483975303$&
$423549648963$\\ \hline
$n=13$& $1399610$& $553339258$& $73360425430$&
$4512516867634$\\ \hline
$n=14$& $4702499$& $2947940371$& $570219618745$&
$48282551418859$\\ \hline
$n=15$& $15883190$& $15780565950$& $4451677886746$&
$518633980103198$\\ \hline
\end{tabular}
\caption{The number of multiplex juggling patterns of period $n$ using $b$ balls with capacity $\kappa=2$.}
\label{tab:cap2}
\end{table}
\begin{table}[H]
\centering
\begin{tabular}{|l|r|r|r|r|}\hline
$\kappa=3$ & $b=2$ & $b=3$ & $b=4$ & $b=5$\\ \hline\hline
$n=1$& $2$& $3$& $4$& $5$\\ \hline
$n=2$& $4$& $12$& $28$& $58$\\ \hline
$n=3$& $13$& $63$& $231$& $713$\\ \hline
$n=4$& $37$& $310$& $1840$& $8591$\\ \hline
$n=5$& $118$& $1618$& $15168$& $106073$\\ \hline
$n=6$& $356$& $8434$& $126258$& $1325570$\\ \hline
$n=7$& $1142$& $45142$& $1069002$& $16789985$\\ \hline
$n=8$& $3620$& $243998$& $9154845$& $214916096$\\ \hline
$n=9$& $11744$& $1336644$& $79252442$& $2776778019$\\
\hline
$n=10$& $38275$& $7392117$& $692290928$& $36167946945$\\
\hline
$n=11$& $126234$& $41247234$& $6095630354$&
$474470288650$\\ \hline
$n=12$& $418735$& $231856131$& $54045188641$&
$6263882726811$\\ \hline
$n=13$& $1399610$& $1311820110$& $482108239540$&
$83162406390939$\\ \hline
$n=14$& $4702499$& $7464002451$& $4323812672665$&
$1109678347266127$\\ \hline
$n=15$& $15883190$& $42679372930$& $38963338572980$&
$14873888879020290$\\ \hline
\end{tabular}
\caption{The number of multiplex juggling patterns of period $n$ using $b$ balls with capacity $\kappa=3$.}
\label{tab:cap3}
\end{table}
\vfill\eject
\begin{conjecture}
Let $a_b^{(2)}$ be the number of cards for multiplex juggling with $b$ balls and where each track has capacity at most $\kappa=2$. Then
\[
\sum_{b\ge 0}a_b^{(2)}x^b = \frac{1-x+x^2+x^3}{(1-x-x^2)^3}.
\]
\end{conjecture}
\section{Conclusion}\label{sec:conclusion}
By modifying the cards used for juggling, namely allowing a subset of the balls to be grouped together, we have found a method that works for enumerating multiplex juggling patterns. There are still a few questions that remain, particularly in understanding what happens when we limit the number of balls that can be caught at any given time.
\bigskip
Ehrenborg and Readdy \cite{ER} introduced cards for juggling and used them to study a $q$-analog of juggling by counting crossings. It is easy to count crossings on each card and then one simply adds up the crossings over all cards used to count the crossings of the pattern. We note that the matrices used here can be easily adapted to this situation. Namely for each card we count crossings (making sure to count multiplicity when balls move in groups), and then weight the card (and hence edge in the graph) by $q^k$ where $k$ is the number of crossings. Finally we can form matrices $A_b(q)$ where we add up the weights of cards connecting compositions. As an example we have
\[
A_3(q)=
\begin{array}{r}(3)\\(2,1)\\(1,2)\\(1,1,1)\end{array}\left(\begin{array}{cccc}
2 & 1 & 1 & 1 \\
1 & q+2 & q+1 & q^2+q+1 \\
1 & q & 2 & 0 \\
0 & 1 & q & q^2+q+2
\end{array}\right).
\]
We note that Theorem~\ref{thm:siteswapcount} and Theorem~\ref{thm:capacity} can be easily modified to count the number of juggling patterns with minimal period based on the number of crossings.
\bigskip
An applied mathematical juggler might also want to add the constraint that whenever multiple balls are thrown that no two balls get thrown to the same height. Our method can be readily adopted to this situation by simply removing any card which has two balls moved to the same track, which leads to modified graphs $\widehat{\mathcal{G}}_b$, and also modified matrices, $\widehat{A}_b$. For example we have
\[
\widehat{A}_2=\begin{array}{r}(2)\\(1,1)\end{array}\left(\begin{array}{cc}
1 & 1 \\
1 & 3
\end{array}\right),\qquad\text{and}\quad
\widehat{A}_3=
\begin{array}{r}(3)\\(2,1)\\(1,2)\\(1,1,1)\end{array}\left(\begin{array}{cccc}
1 & 0 & 0 & 1 \\
0 & 2 & 1 & 3 \\
1 & 1 & 2 & 0 \\
0 & 1 & 1 & 4
\end{array}\right).
\]
\bigskip
The matrices $A_b$ might also have independent interest. Let us consider the characteristic polynomial of $A_b$. If we let $P_b:=P_b(x)=\det(xI-A_b)$, then we have the following factorization (here the $f_i$ are all polynomials and the $P_b$ are found my multiplying the corresponding polynomials in the row together).
\[
\begin{array}{l@{\,=\,}llllllllllllll}
P_0&f_0^1\\
P_1&&f_1^1\\
P_2&&&f_2^1\\
P_3&f_0^1&&&f_3^1\\
P_4&f_0^2&f_1^1&&&f_4^1\\
P_5&f_0^5&f_1^2&f_2^1&&&f_5^1\\
P_6&f_0^9&f_1^5&f_2^2&f_3^1&&&f_6^1\\
P_7&f_0^{19}&f_1^9&f_2^5&f_3^2&f_4^1&&&f_7^1\\
P_8&f_0^{37}&f_1^{19}&f_2^9&f_3^5&f_4^2&f_5^1&&&f_8^1\\
P_9&f_0^{74}&f_2^{37}&f_2^{19}&f_3^9&f_4^5&f_5^2&f_6^1&&&f_9^1\\
P_{10}&f_0^{148}&f_1^{74}&f_2^{37}&f_3^{19}&f_4^9&f_5^5&f_6^2&f_7^1&&&f_{10}^1\\
P_{11}&f_0^{296}&f_1^{148}&f_2^{74}&f_3^{37}&f_4^{19}&f_5^9&f_6^5&f_7^2&f_8^1&&&f_{11}^1\\
P_{12}&f_0^{591}&f_1^{296}&f_2^{148}&f_3^{74}&f_4^{37}&f_5^{19}&f_6^9&f_7^5&f_8^2&f_9^1&&&f_{12}^1\\
P_{13}&f_0^{1183}&f_1^{591}&f_2^{296}&f_3^{148}&f_4^{74}&f_5^{37}&f_6^{19}&f_7^9&f_8^5&f_9^2&f_{10}^1&&&f_{13}^1
\end{array}
\]
The polynomials $f_i$ are given by the following (the number on the right indicates the largest root of the polynomial).
\[
\begin{array}{|r@{~=~}l@{\quad}|@{\quad}l|}\hline
f_0(x)&x-1&1.000\ldots\\\hline
f_1(x)&x-2&2.000\ldots\\\hline
f_2(x)&x^2-5x+5&3.618\ldots\\\hline
f_3(x)&x^3 - 10x^2 + 27x -20&6.124\ldots\\\hline
f_4(x)&x^5 - 20x^4 + 135x^3 - 396x^2 + 518x - 245&9.884\ldots\\\hline
f_5(x)&x^7 - 36x^6 + \cdots - 2^5{\cdot}5{\cdot}7^2
&15.382\ldots\\\hline
f_6(x)&x^{11} - 65x^{10} + \cdots - 2^5 {\cdot} 3^2 {\cdot} 5^2 {\cdot} 7^3&23.255\ldots\\\hline
f_7(x)&x^{15} - 110x^{14} + \cdots - 2^{11} {\cdot} 3^2 {\cdot} 5^3 {\cdot} 7^4&34.332\ldots\\\hline
f_8(x)&x^{22} - 185x^{21} + \cdots + 2^{10} {\cdot} 3^4 {\cdot} 5^4 {\cdot} 7^6 {\cdot} 11^2&49.689\ldots\\\hline
f_9(x)&x^{30} - 300x^{29} + \cdots + 2^{21} {\cdot} 3^5 {\cdot} 5^6 {\cdot} 7^8 {\cdot} 11^2&70.702\ldots\\\hline
f_{10}(x)&x^{42} - 481x^{41} + \cdots + 2^{21} {\cdot} 3^9 {\cdot} 5^8 {\cdot} 7^{12} {\cdot} 11^3 {\cdot} 13^2&99.127\ldots\\\hline
f_{11}(x)&x^{56} - 752x^{55} +\cdots + 2^{38} {\cdot} 3^{12} {\cdot} 5^{11} {\cdot} 7^{16} {\cdot} 11^4 {\cdot} 13^2&137.190\ldots\\\hline
f_{12}(x)&x^{77} - 1165x^{76}+\cdots - 2^{42} {\cdot} 3^{17} {\cdot} 5^{16} {\cdot} 7^{22} {\cdot} 11^9 {\cdot} 13^3&187.694\ldots\\\hline
f_{13}(x)&x^{101} - 1770x^{100} +\cdots - 2^{70} {\cdot} 3^{23} {\cdot} 5^{21} {\cdot} 7^{29} {\cdot} 11^{11} {\cdot} 13^4&254.151\ldots\\\hline
\end{array}
\]
These polynomials are important as they give the eigenvalues of the matrices which in turn determine the rate of growth of the number of juggling sequences. It should be noted that $f_1,\ldots,f_{13}$ are all irreducible.
There are several interesting things that are appearing in the characteristic polynomials.
\begin{itemize}
\item The sequence of the exponents of $f_i$ in the $P_j$ seem to follow
\[
1,~0,~0,~1,~2,~5,~9,~19,~37,~74,~148,~296,~591,~1183,\ldots.
\]
This appears to be the sequence \seqnum{A178841} in the OEIS \cite{OEIS} which counts the number of pure inverting compositions of $n$.
\item The degree of the polynomials $f_i$ follow
\[
1,~1,~2,~3,~5,~7,~11,~15,~22,~30,~42,~56,~77,~101,\ldots.
\]
This appears to be the sequence \seqnum{A000041} in the OEIS \cite{OEIS} which counts the number of partitions of $n$.
\item The second coefficients of the polynomials $f_i$ follow
\[
1,~2,~5,~10,~20,~36,~65,~110,~185,~300,~481,~752,~1165,~1770,\ldots.
\]
This appears to be the sequence \seqnum{A000712} in the OEIS \cite{OEIS} which counts the number of partitions of $n$ into parts of $2$ kinds.
\end{itemize}
We have no explanations for any of these phenomena, but given the nature of how the matrix is formed, we believe this is more than coincidence.
We look forward to more research being done into these cards, into multiplex juggling patterns, and into the matrices $A_b$.
\section{Acknowledgment}
The authors thank a referee for extensive useful suggestions on an earlier draft of this paper.
\begin{thebibliography}{99}
\bibitem{BEGW}
J. Buhler, D. Eisenbud, R. Graham, and C. Wright, Juggling drops and descents, \emph{Amer. Math. Monthly} \textbf{101} (1994), 507--519.
\bibitem{BCCG}
S. Butler, F. Chung, J. Cummings, and R. Graham, Juggling card sequences, \emph{J. Comb.} \textbf{8} (2017), 507--539.
\bibitem{BG}
S. Butler and R. Graham, Enumerating (multiplex) juggling sequences, \emph{Ann. Comb.} \textbf{13} (2010), 413--424.
\bibitem{ER}
R. Ehrenborg and M. Readdy, Juggling applications to $q$-analogues, \emph{Discrete Math.} \textbf{157} (1996), 107--125.
\bibitem{P}
B. Polster, \emph{The Mathematics of Juggling}, Springer, 2000.
\bibitem{OEIS} N.~J.~A. Sloane, \emph{The On-Line Encyclopedia of Integer
Sequences},
\url{http://oeis.org}.
\bibitem{Stadler}
J. Stadler, Juggling and vector compositions, \emph{Discrete Math.} \textbf{258} (2002), 179--191.
\bibitem{S}
R. Stanley, \emph{Enumerative Combinatorics, Volume I}, second edition, Cambridge, 2012.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2000 {\em Mathematics Subject Classification}: Primary 05A15; Secondary 00A08.
\noindent{\em Keywords}: juggling, transfer matrix method, composition, partition.
\bigskip
\hrule
\bigskip
\noindent(Concerned with sequences
\seqnum{A000041},
\seqnum{A000712},
\seqnum{A003480},
\seqnum{A090764}, and
\seqnum{A178841}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received March 13 2017;
revised versions received
March 2 2018; January 30 2019; January 31 2019.
Published in {\it Journal of Integer Sequences}, February 2 2019.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}