1. With an unlimited supply of toothpicks of n different colors, how many different triangles can be formed on a flat surface, using three toothpicks for the sides of each triangle?
   (Reflections are considered different, but rotations are not.)

2. How many different squares?

Triangles:

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 =)