Math Tutoring Service

See my Mathematics Tutoring Service on Thumbtack

More on Ordering a Multiset

I posed problem A3, to find a formula for the k-th largest element of an n-element multiset A. I found a very interesting formula that is unknown to several famous combinatorists, including Donald Knuth, and I have submitted a problem to the MAA Monthly Problems section which asks for the solution that I found, a linear combination of certain symmetric functions. However, Knuth told me that there is a simpler known formula of a different type. Knuth's formula is

min(maxk)

where (maxk) is a set of C(n,k) numbers, each of which is the maximum of a different subset of A of size k.

Pretty cute!

No comments: