A quick question about multiplicity?

[jeebs]

This is probably a simple thing to do but it is driving me up the wall.

Say I had a box with M slots, and there are N particles inside this box, and each slot can hold, at most, 1 particle. (where N is less than or equal to M).
I am trying to calculate the multiplicity of this box system by counting the number of possibilities of distributing my N particles over these M slots.

I have tried to make a simple example, with M = 3. If I first take N=0, then there is only 1 configuration, ie. the multiplicity (lets say, P) is 1. I have drawn out little diagrams and determined that:
P(N=0) = 1
P(N=1) = 3
P(N=2) = 3
P(N=4) = 1
The total sum of these multiplicities P_t = 1+3+3+1 = 8 = 2³.

I have done the same thing for M = 2:
P(N=0) = 1
P(N=1) = 2
P(N=2) = 1
Here P_t = 1+2+1 = 4 = 2².

and M = 4:
P(N=0) = 1
P(N=1) = 4
P(N=2) = 6
P(N=3) = 4
P(N=4) = 1
Here, P_t = 1+4+6+4+1 = 16 = 2⁴.

From this I can see that P_t = 2^M, and that if N=0 or N=M, then P=1.

However, I need a general expression, since I do not want to draw out these little diagrams for higher and higher M or N. In other words, how do I find out an expression for the multiplicity P=P(N,M)?
I cannot spot a pattern just from the examples I have done. Out of M slots, how many ways are there of arranging the N particles I happen to have inside the box (N</= M) ?

Thanks.

 

[tiny-tim]

hi jeebs!

let's write out your results in a table …

1 2 1

1 3 3 1

1 4 6 4 1

…

does that remind you of anything? ​

 

[jeebs]

hi jeebs!

let's write out your results in a table …

1 2 1

1 3 3 1

1 4 6 4 1

…

does that remind you of anything? ​

it is the same sequence as pascal's triangle, right?

I don't see the connection between that and what I want to do though...? I can't really remember what pascal's triangle was supposed to be about to be honest

 

[tiny-tim]

I can't really remember what pascal's triangle was supposed to be about to be honest

The binomial theorem …

the nth row in Pascal's triangle gives the coefficients of (1 + x)ⁿ

 

[jeebs]

So, I have M slots and N particles to distribute amongst them.

M=2: 1,2,1 are the multiplicities as N increases from 0 to M. This is actually the 3rd (n=2) row in the triangle.
M=3: 1,3,3,1
M=4: 1,4,6,4,1. The nth row gives coefficients (1+x)^n.

What is x in my example? I'm sorry, I just don't get how this applies. It was a practice exam question I was attempting to do and I don't think it expected me to bring pascal's triangle into it? I haven't heard that thing mentioned in years.

 

[tiny-tim]

hi jeebs!

i was hoping you'd remember that (1 + x)ⁿ = ∑_i=0^{n n}C_i,

where ⁿC_i, = n!/i!(n-i)!, is the "choose" function, the number of ways of choosing i objects (unordered) from n.

Your original question was the number of ways of choosing N objects (unordered) from M (M slots, each of which can be either empty or full, and there have to be exactly n full … the same as having binary numbers of length M but with exactly N "1"s): ^MC_N.

The reason why (1 + x)ⁿ works is that (1 + x)ⁿ = (1 + x)(1 + x)…(1 + x), and the coefficient of xⁱ is obviously the number of ways of choosing x from exactly i of those brackets. :wink

:

 

[jeebs]

hi jeebs!

i was hoping you'd remember that (1 + x)ⁿ = ∑_i=0^{n n}C_i,

where ⁿC_i, = n!/i!(n-i)!, is the "choose" function, the number of ways of choosing i objects (unordered) from n.

Your original question was the number of ways of choosing N objects (unordered) from M (M slots, each of which can be either empty or full, and there have to be exactly n full … the same as having binary numbers of length M but with exactly N "1"s): ^MC_N.

The reason why (1 + x)ⁿ works is that (1 + x)ⁿ = (1 + x)(1 + x)…(1 + x), and the coefficient of xⁱ is obviously the number of ways of choosing x from exactly i of those brackets. :wink

:

ahh that's helpful man, thanks a lot.