help annotate
Contents Next: References Up: Juggling Drops and Descents Previous: Remarks for Jugglers

Counting Periodic Juggling Patterns

[Annotate][Shownotes]


Let denote the number of period-n juggling patterns f with . Our next goal is to calculate this number. From the juggler's point of view it might be more useful to count the number of patterns of exact period n and to count cyclic shifts of a pattern as being essentially the same as the original pattern. Later we will see that this more natural question can be answered easily once we know .
The basic idea in the determination of is to fix a permutation and count the number of patterns f such that . From the proof of the previous theorem we have the formula

Thus we must count the number of functions such that if f is defined by the above formula then and .

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

Since is a permutation of we see that this reduces to

Thus a function g determines a pattern with if the sum of its values is equal to b.

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

Write so that

Let k be the number of drops of . Then if and only if the sum of the values of G is equal to b-k.

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 2

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

Later it will be convenient to consider the number of period-n juggling patterns with fewer than b balls. If this number is denoted then, using a familiar binomial coefficient identity, we find that

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

and is called an Eulerian number.

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

A descent in is just a point in this finite sequence in which the next term is lower than the current term.

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 3

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

By relating permutations of to permutations of in the usual way, a more involved combinatorial argument shows that

Using this recursion, it is easy to tabulate Eulerian numbers.

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

By Möbius inversion we obtain the following corollary to the previous theorem.

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.



help annotate
Contents Next: References Up: Juggling Drops and Descents Previous: Remarks for Jugglers