Contents

Let denote the number of period-

The number of balls of such a pattern **f** is equal to the average of
over . Thus

The condition that is a little bit more intricate. Since

we see that must be non-negative and also must be strictly positive whenever .
** Definition:**
An integer is a drop for the permutation
if ; moreover, we define

We can summarize this discussion so far as follows.
The number of period-**n** juggling patterns with
**b** balls is equal to the sum over all permutations
of the number of non-negative functions
on whose value-sum is **b-k**, where **k** is
the number of drops of .

A standard combinatorial idea can be used to count the number of sequences of non-negative integers with a given sum.

The number of non-negativen-tuples with sumxis

Let be the number of permutations in that have **k** drops.
By combining the earlier remark with the lemma we arrive at

In order to simplify this further we recall the idea of a
descent of a permutation and show that even though
drops and descents aren't the same thing, the number of permutations
with **k** drops is the same as the number with **k** descents.

** Definition:**
If then is a ** descent**
of if where .
The number of elements of with **k** descents is
denoted

We will write permutations as a list of **n** integers in which
the **i**-th element is , e.g.,

** Example. **
The permutation 10432 in has three descents and two
drops.

If is a permutation then it can also be written in cycle form in the usual way. In order to specify this form uniquely we write each cycle with its largest element first and arrange the cycles so that the leading elements of the cycles are in increasing order, where we include the singleton cycles.

** Definition:**
If let be the permutation that results
from writing in cycle form, as above, and
then erasing parentheses.

** Example. **
The permutation corresponding to the
sequence 16037425 has a cycle decomposition (0162)(475) that has
the canonical form (3)(6201)(765).
Therefore is 36201754.

Note that the map taking to is bijective since can be uniquely reconstructed from by inserting left parentheses before every left-to-right maximum and then inserting matching right parentheses. This permutation of is certainly bizarre at first glance, but it plays a surprisingly crucial role in various situations (see [5] or [15]).

The number of permutations of withkdescents is equal to the number withkdrops, i.e.,

** Example, again.**
The permutation has drops at
, and the permutation
has descents at .

The Eulerian numbers
play a role in a variety of combinatorial
questions beyond drops and descents ([10], [15],
[16]), although no notation seems to be standard yet.
We recall some of their basic properties.
If a permutation
has **k** descents then its reversal
has **n-k -1** descents.
Thus

Finally, the Eulerian numbers arise as coefficients of the linear relations connecting the polynomials with the polynomials .

** Worpitzky's Identity.**

This identity can by readily proved by induction using equation (2). It apparently first appeared in [20] (see also [10] and [16]); in [15] it appears as a special case of a much more general statement.

The number of period-njuggling patterns with fewer thanbballs is , i.e.,

The simplicity of the final result is surprising. The astute reader will note that we could have avoided introducing the concept of descents by proving equations (1) and (2) directly for the counting function for drops. It is a pleasant exercise to provide a direct combinatorial argument. We took the slightly longer route above because it is amusing and useful in proving the much more general result in [6].

By the theorem there are patterns of period **n**
with exactly **b** balls if cyclic shifts are counted as distinct.
Let be the number of patterns of exact period **n** with
exactly **b** balls, where cyclic shifts are not counted as distinct.
Thus is probably the number that is of most interest to a
juggler.

If **d** is a divisor of **n** then each pattern of exact
period **d** will be occur **d** times as pattern of length **n**.
Thus

For instance, there are 12 genuinely distinct patterns with period three with three balls. The reader may find it instructive to list all of them explicitly.

Several people have reproved Theorem 3 from other points of view. Richard Stanley sent us a proof using results in [15]. Jeremy Kahn sent us a bijective proof using a different labeling function for juggling patterns. Walter Stromquist sent us an interesting bijective proof that uses a very curious relabeling of site swap patterns. Adam Chalcraft ([4]) sent us a proof using ideas similar to those of Stromquist. It is striking that the result seems to be of considerable interest to a number of people.

Several of these proofs are shorter than ours, and some are much closer to being more transparent ``bijective'' proofs. However, the proof given here, in addition to using some interesting combinatorics, is the special case of the proof of the much more general result in [6]. The basic motivation of that result is to replace the set with an arbitrary poset. For some posets we can give a natural interpretation of that more general result in terms of juggling patterns in which more than one ball can be thrown at once, but we still haven't been able to give a juggling interpretation for arbitrary posets. After hearing of our results from Richard Stanley, E. Steingrímsson reproved ([17]) the general results about posets using results from his thesis. Among many other things, he generalizes the notions of descents and drops (actually, in his terminology, a mirror notion he calls ``exceedances'') to certain wreath products of symmetric groups.

** NOTE ADDED IN PROOF:** In their recent preprint, ``Juggling and
applications to **q**-analogues,'' Richard Ehrenborg and Margaret Readdy give
a **q**-analogue of our main result. In addition they generalize the ideas to
multiplex patterns (in which a hand can catch and throw more than one ball at
once) and give applications to **q**-Stirling numbers and the Poincare series of
an affine Weyl group.

Contents