Ccolors of objects, and
Sslots 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, kand
_ _. The number of colorings that I want to count is:
Everything coloring on the lower diagonal (say,
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:
One can solve this using stars-and-bars. Take the number of slots
cc cm cy ck * mm my mk * * yy yk * * * kk
Sto be the number of stars. Take the number of colors
Cto 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)Ckwithout 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 + ...
0and divide by
2. This gives:
so we get the answer as
(1/(1-x)^4)'' (0) = (-4/(1-x)^5)' (0) = (20/(1-x)^6) (0) = (20/(1-0)^6) = (20)
answer = 20/2! = 10.