Re: combinatorics question
From: Rob Johnson (rob_at_www-lvs0.net.ohio-state.edu)
Date: 07/18/04
- Next message: Doug Goncz : "Exhaustive Search"
- Previous message: Stein A. Stromme: "Re: combinatorics question"
- In reply to: Faheem Mitha: "combinatorics question"
- Next in thread: Chas Brown: "Re: combinatorics question"
- Messages sorted by: [ date ] [ thread ]
Date: 18 Jul 2004 07:12:11 -0400
In article <cdcdt0$cg2$1@dizzy.math.ohio-state.edu>,
Faheem Mitha <faheem@email.unc.edu> wrote:
>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.
Think of this as having m slots whose contents sum to n. Each example
of this can be represented by a sequence of m-1 "|"s and n "x"s.
For example m = 2, n = 3:
xxx| <-> (3,0)
xx|x <-> (2,1)
x|xx <-> (1,2)
|xxx <-> (0,3)
The number of such sequence of "|"s and "x"s is
(n+m-1)!
C(n+m-1,m-1) = --------
n!(m-1)!
Rob Johnson <rob@trash.whim.org>
take out the trash before replying
- Next message: Doug Goncz : "Exhaustive Search"
- Previous message: Stein A. Stromme: "Re: combinatorics question"
- In reply to: Faheem Mitha: "combinatorics question"
- Next in thread: Chas Brown: "Re: combinatorics question"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
|
