🚀 go-pugleaf

Hello again,

Since my last query generated some great help, I thought I'd
post the other little problem that has come up in recent work.
I actually have, I think, a set of recurrence equations to solve
this, but I wanted to know if it is a solved problem so I can
double check my answer, and if it has a `standard' name by which
I can refer to it. I've been calling it the problem of `limited
partitions'.

It is known that the number of partitions of n into exactly k
parts is [n-1 choose k-1]. What I want to know is the partition
of n into k OR LESS parts WHERE THE MAX VALUE = m. I call this
(until someone tells me it's real name) a `limited partition'
P(n,k,m).

I've solved this by breaking it into simpler problems, i.e., we
first choose some number i (i>1, and n<im) of the k slots to get
the max value m (there are [k-(i-1) choose 1] ways to do this),
and then for each compute P'(n-im,k-i,m-1), where P'(n,k,m) =
number of partitions of n into k or less values each <= m.
P'(n,k,m) is in turn computed by choosing another j<k and
referring to a final partition, P*(n,k,m), which is the
partition of n into EXACTLY k values where each value is <= m.

In any case, I wondered if any of these were standard solved
problems so I could call them by the right names and check my
derivations (maybe they even have closed form solutions).

Thanks again,
/Keith
decker@cs.umass.edu
Cooperative Distributed Problem Solving Lab
University of Massachusetts at Amherst

P.S.  In case anyone wants to know, the application of the
result is to distributed problem solving.  Say we want to
analyze how long it will take A agents to solve n problems that
initially arrive randomly at agents (like tossing n balls into A
boxes) The termination time for the system is based on which
agent gets the *most* problems (which box gets the most balls).
The expected termination time is then the termination time if
the agent with the most balls got exactly m balls, times the
probability of that occuring, which can be deduced directly from
the above limited partition results.