C colors of objects, and S slots to put these objects in. In
how manys can I put objects into slots, without regard to order? For example,
say we have 4 colors c, m, y, k and 2 slots _ _. The number of colorings
that I want to count is:
cc cm cy ck
mc mm my mk
yc ym yy yk
kc km ky kk
mc) is equivalent to one on
the upper diagonal ( cm). So in total, there are 10 colorings:
cc cm cy ck
* mm my mk
* * yy yk
* * * kk
S to be the
number of stars. Take the number of colors C to be the number of bars. The
answer to the stars-and-basrs is the same as the coloring question.
I don't like stars and bars for this, because it seems to force an ordering of
the colors c1 < c2 < .. < cn. [which bar cooresponds to which color ]. Is
there some way to not have to do this?
Is there some other way to show the (n + k - 1)Ck without imposing this
ordering, or some other way to count this quantity?
One other way you can look at this is using multinomial expansion, but its
computation is slightly more involved. Its advantage is that it ignores
ordering of the objects, which is what you desire.
In this case, we represent each color as the polynomial 1 + x + x^2, here the
power of x represents the number of instances you are taking of that color.
So, if you take (1 + x + x^2)^4, you have found the number of ways to arrange
four colors, for different numbers of slots. If you take coefficient of x^2
from that polynomial, you get the answer to your question
Why does this set of shady manipulations not work?
answer = coeff. of x^2 in (1 + x + x^2)^4
[We can add higher powers, won't change coeff of x^2]
answer = coeff. of x^2 in (1 + x + x^2 + x^3)^4
answer = coeff. of x^2 in (1 + x + x^2 + ...)^4
answer = coeff. of x^2 in (1/(1-x))^4
Call f(x) = (1/(1-x))^4
f(x) =taylor= f(0) + f'(x) x + f''(0) x^2/2 + f'''(0) x^3 / 6 + ...
1/(1-x)^4 =taylor= ... + (1/(1-x)^4)''(0) x^2/2 + ...
so:
answer = coeff. of x^2 in ... + (1/(1-x)^4)''(0) x^2/2 + ...
(1/(1-x)^4)'' evaluated at 0 and divide
by 2. This gives:
(1/(1-x)^4)'' (0)
= (-4/(1-x)^5)' (0)
= (20/(1-x)^6) (0)
= (20/(1-0)^6)
= (20)
answer = 20/2! = 10.