Re: combinatorics question

From: Chas Brown (cbrown_at_cbrownsystems.com)
Date: 07/18/04 

Date: 18 Jul 2004 17:51:04 -0400

Faheem Mitha <faheem@email.unc.edu> wrote in message news:<cdcdt0$cg2$1@dizzy.math.ohio-state.edu>...
> Dear People,
>
> Consider two positive integers, $n$ and $m$, with $m \leq n$. Then I
> need to count the number of distinct ordered tuples $(n_1, \dots,
> n_m)$, such that $\sum_{i=1}^m i n_i = n$.
>
> Is a closed form expression known for this number? I'd also be happy
> with a good approximation, though here n is likely to be small (<30)
> so asymptotic expression would not be so useful.
>
> I have spent some time trying to come up with something but no
> joy. However, I am quite ignorant about combinatorics, so it may be
> easy.
>
> Please cc me at the above address on any reply. Thanks.
>
> Faheem.

You're looking at "partitions of n consisting of m parts".

I'm assuming (for the moment) that each n_i we have 0<=n_i<=n.

Consider n = 6; m = 3.

Consider the partition (3,2,1). Write it as:

***|**|*

Now consider the partition (4,0,2). Write it as:

****||**

Note that any such partition can be _uniquely_ written as a string of
(n+m)-1 = 8 symbols, n = 6 of which are "*", and (m-1) = 2 of which
are "|".

So in this example, the result is equivalent to counting the distinct
permutations of the string "******||". This is Choose(8,2) = 28 (where
Choose(a,b) = a!/((a-b)!b!)).

More generally, you want Choose((n+m-1),m-1).

If you wish to insist that each n_i obeys n_i>0, then a similar
argument can be used; write the partition (3,2,1) as "**|" + "*|" +
"|", i.e.:

**|*||

So now we want the number of all permutations of the string "***|||";
and your result is Choose(6,3) = 10; and in the general case, you want
Choose(n,m) = n!/((n-m)!m!).

Because of the behaviour of the factorial function, this can get VERY
big VERY fast for large n (for example, 30! > 2*10^32). You might want
to look at approximations of the factorial function such as Stirling's
approximation:

http://en.wikipedia.org/wiki/Stirling%27s_approximation

which you can plug into the Choose() function to get pretty good
results.

Hope that helps -

Cheers - Chas

Relevant Pages

  • Re: combinatorics question
    ... > Is a closed form expression known for this number? ... > with a good approximation, though here n is likely to be small ... Now consider the partition. ... Because of the behaviour of the factorial function, ...
    (sci.math.research)
  • Re: combinatorics question
    ... > Is a closed form expression known for this number? ... > with a good approximation, though here n is likely to be small ... It is possible that Mathematica ... or one of those fancy symbolic algebraic packages could be induced to ...
    (sci.math)
  • Re: combinatorics question
    ... > Is a closed form expression known for this number? ... > with a good approximation, though here n is likely to be small ... It is possible that Mathematica ... or one of those fancy symbolic algebraic packages could be induced to ...
    (sci.math.research)
  • Re: combinatorics question
    ... Faheem Mitha wrote: ... >Is a closed form expression known for this number? ... >with a good approximation, though here n is likely to be small ... Rob Johnson ...
    (sci.math)
  • Re: combinatorics question
    ... Faheem Mitha wrote: ... >Is a closed form expression known for this number? ... >with a good approximation, though here n is likely to be small ... Rob Johnson ...
    (sci.math.research)