COUNTIN’ LIKE THE WIND

C. CHAN, I. GESSEL, J. PROPP, V. REINER, L. ROSE, AND B. SAGAN

Dedicated to Richard P. Stanley on the occasion of his sixtieth birthday

Abstract. This work honors one of the greats of enumeration.

1. Countin’ like the wind

How many ways can one direct a graph oh, totally acyclic’lly? Yes ’n’ say that the graph can contain no self-loop to avoid triviality. If there are χ of t ways to color its nodes with at most t colors properly, then the answer my friend is χ of minus one though we must take that absolutely. [1, Corollary 1.3]

How many faces at most can there be when triangulating a sphere if we fix the dimension and number of nodes not assuming convexity? Yes ’n’ also let’s say that one need not assume PL nor shellability. The maximum’s achieved, as Motzkin would agree, on a cyclic polytope’s boundary. [2, Note added in proof, p. 135]

Date: June 23, 2004.

1991 Mathematics Subject Classification. Primary: 00B30, 01A65, Secondary: 05Axx, 05Exx.

Key words and phrases. acyclic orientation, symmetric magic squares, simplicial sphere, q-Eulerian distribution, Erdős-Moser problem, minuscule poset, selfcomplementary plane partition, reduced decomposition, vexillary, graphical degree sequence, zonotope, riffle shuffle, quasisymmetric function.

The authors thank R.P. Stanley for all of his advice, humor, patience and tolerance. Without him, this song could not have been written.

How many ways can one order one to ten so the number of descents is five, while the number of inversions is thirty-two, what a very strange thing to contrive! Yes ’n’ doesn’t this just make your poor noggin sting even cause you to break out in hives? Well the answer’s nearly free thinking q-binomially: it’s twenty-nine thousand and five. [3, Corollary 3.6 with k = r = 1]

How many folks dare to count magic squares with fourteen as their row and column sum with five rows and five columns and (just to make it hard) let’s tack on a symmetry assumption? Yes ’n’ what’s the result if you think to consult a particular generating function? One hundred seventy four million, two hundred forty eight thousand, four hundred and fifty one. [4, §5, p. 525]

How many subsets of an odd-sized set of numbers can have the same sum? Erdős and Moser puzzled long over this, and it wasn’t because they were dumb. Yes ’n’ what can we bound this number by from the insight of Bernt Lindstrom? The answer’s the largest rank size in the product of two type B minuscule posets, by gum! [5, Corollary 5.3 with k = 1 and n odd]

How many ways can a permutation bubble-sort to the identity, if the sorting is done as fast as can be and the permutation’s vexillary? Yes ’n’ let’s say that ϕ is the permutation’s code rearrangèd decreasing weakly. The answer my friend is the number of tableaux that are standard, Young, and have shape ϕ. [6, Corollary 4.2] How many ways can one tile with unit rhombs a centrally-symmetric hexagon if the tiling enjoys the symmetry of antipodal rotation? Yes ’n’ let us assume that the hexagon’s sides have lengths all of which are even. Then just square the tiling count for a half-sized hexagon known to Percy Alexander MacMahon. [7, equation (3a)]

How many sequences of integers give a graph’s vertex-degrees, if we say that the graph contains no self-loop, nor an edge appearing multiply? Yes ’n’ being concrete, let’s assume that the graph has exactly five vertices. Just count the lattice points in a certain zonotope and it’s five hundred and thirty-three. [8, Corollary 3.6]

How many ord’rings of 1 through n distributed quasi-symmetric’lly (this means by standardizing randomly chosen words whose letters have fixed probabilities) consist of increasing runs whose lengths ξ of i form a composition of n we’ll call ξ? The answer’s the ribbon Schur function indexèd by ξ, evaluated at the probabilities. [9, Theorem 3.6]

How many theses can one man inspire, before he decides to retire? Yes ’n’ how many theorems can one man prove, before he loses his groove? Yes ’n’ just how much fun can he pack in a pun, and still make up another one? The answer grows uncannily, though huge most certainly, when the man’s name is Richard P. Stanley.

2. Acknowledgments

The authors thank Bob Dylan for the original lyrics which we clearly borrow from heavily, and for the music to which this was performed at the 60th birthday conference for Richard Stanley on June 23, 2004.

References

[1] R.P. Stanley, Acyclic orientations of graphs. Discrete Math. 5 (1973), 171–178.

[2] , Cohen-Macaulay rings and constructible polytopes. Bull. Amer. Math. Soc. 81 (1975), 133–135.

[3] , Binomial posets, Möbius inversion, and permutation enumeration. J. Combinatorial Theory Ser. A 20 (1976), 336–356.

[4] , Magic labelings of graphs, symmetric magic squares, systems of parameters, and Cohen-Macaulay rings. Duke Math. J. 43 (1976), 511–531.

[5] , Weyl groups, the hard Lefschetz theorem, and the Sperner property. SIAM J. Algebraic Discrete Methods 1 (1980), 168–184.

[6] , On the number of reduced decompositions of elements of Coxeter groups. European J. Combin. 5 (1984), 359–372.

[7] , Symmetries of plane partitions. J. Combin. Theory Ser. A 43 (1986), 103–113.

[8] , A zonotope associated with graphical degree sequences. Applied geometry and discrete mathematics, 555–570, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 4, Amer. Math. Soc., Providence, RI, 1991.

[9] , Generalized riffle shuffles and quasisymmetric functions. Ann. Comb. 5 (2001), 479–491.