Iím not sure, but I think Iíd like to break this up into three sums. One for triangles with "toothpicks all one color," another for triangles with "2 toothpicks one color, 1 toothpick another color," and a third for triangles with "all 3 toothpicks are different colors."
Ok, for triangles with toothpicks of all one color, the answer is simply n choose 1 permutations. With or without replacements doesnít matter, because you just pick one and the other two have to match. So the answer is n either way (n^1=n and n!/(n-1)!=n). Any reflections or rotations of these triangles are the same, so there are no duplicates that have to be accounted for.
Now for triangles with 2 toothpicks one color, 1 toothpick another color. The way I think about it is like this: What Iím going to do is say "first choose the color of the 2 toothpicks, then choose the color of the other toothpick, but it canít be the same color as what you first picked." In other words, "red, blue" is a valid construction (2 reds and a blue) but "red, red" is not (2 reds and a red = 3 reds which is accounted for in the first group). So this is n choose 2 without replacement. Also notice that "red, blue" is not the same as "blue, red" (2 blues and a red). So this is a permutation, not a combination. Well, n choose 2 permutations without replacement is n!/(n-2)! = n*(n-1). A reflection will not yield a unique arrangement, so there are no duplicates that need to be accounted for.
And finally we have triangles with all 3 toothpicks being different colors. So this is n choose 3 without replacement (if I allowed replacement I would get triangles that are already accounted for in the first two groups). But should it be permutations or combinations? Well, a permutation would say that "red, blue, green" = "blue, green, red" = "red, green, blue" Ö Now I have a little problem because some of those are considered different, but some are not. I suppose I could let it be permutations, but divide by 3 for repeats. Or if I looked at combinations, that would only count "red, blue, green" and none of the others. Weíll thatís good because it doesnít double count rotations but it doesnít count the one reflection that would be unique. So I could just use the combinations formula and double it. So for this group, itís either n!/(n-3)!/3 or 2*[n!/(3!(n-3)!)] which is the same thing.
So in total I have
T = n + n*(n-1) + 1/3*n*(n-1)*(n-2) = n^3 + 2n = n/3*(n^2 + 2)
The squares sound a little trickier. Iíll have to try that later =)
Posted by nikki
on 2004-09-10 14:00:07