Counting Periodic Juggling Patterns

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

Definition: An integer is a drop for the permutation if ; moreover, we define

Write so that

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.

Lemma

The number of non-negative n-tuples with sum x is

[Proof]

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]).

Lemma

The number of permutations of with k descents is equal to the number with k drops, i.e.,

[Proof]

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.

Theorem 3

The number of period-n juggling patterns with fewer than b balls is , i.e.,

[Proof]

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.