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?

Squares:

Again, I am going to this of this in chunks. I’ll just use letters a, b, c, d to help me describe certain color arrangements. So aaaa means all 4 toothpicks the same color. aaab is 3 of one color, one of another. aabb 2 of one color, 2 of another. aabc is 2 of one color, 1 of another, and the last is yet another color. And then we have abcd, where all 4 are different. So that’s 5 groups.

Similar to my triangle solution, I have this so far:
aaaa: n (reflections are not different)
aaab: n*(n-1) (reflections are not different)
abcd: 2*[n!/(4!(n-4)!)] = 1/12*n*(n-1)*(n-2)*(n-3) (the "times 2" is because reflections are different)

Now the aabb and aabc arrangements are a little different. I have to ask myself a couple questions to make sure I don’t miss anything.

First, does the instruction "pick 2 toothpicks the same color, and 2 toothpicks another color" yield only one result? The answer is No. aabb could also appear as abab, which is a different solution. So that yields 2 results.

Second, are the reflections of aabb or abab different from the original arrangement? The answers are no and no.

Similarly, my third question is, does the instruction "pick 2 toothpicks the same color, the 3rd a different color, and the last yet another color" yield only one result? Again, the answer is No. aabc could appear as abac, which is a different solution. Again, this yields 2 results.

And finally, are the reflections of aabc or abac different from the original arrangement? The answers are yes and no.

Ok, so let’s turn this information into some formulas.

aabb: recalling how I explained the color choosing method from the Triangles solution, notice here that "red, blue" is the same thing as "blue, red." Either way I will end up with 2 reds and 2 blues. Again, you don’t want to pick "red, red" because that is already accounted for in the aaaa group. So this is n choose 2 combinations without replacement, which is n!/(2!(n-2)!) = 1/2*n*(n-1). Since we said that abab is a different solution to "choose 2 blues and 2 reds," we should multiply this by 2. Remember, no reflections should be accounted for, so the formula for this group is actually 2*1/2*n*(n-1) = n*(n-1)

aabc: This one’s crazy! Ok, here is the clearest way for me to think about it. Again with the color choosing method, let’s say that the first color is for the "2 toothpicks," followed by the other two colors. So "red, blue, green" means 2 reds, a blue and a green. This does not determine any order. So 2 reds, a blue and a green could be RRBG, RRGB, RGRB. Those are the only unique possibilities. Also notice that "red, green, blue" is the same as "red, blue, green." But "green, red, blue" is NOT the same, since that has TWO greens, a red and a blue. So how to sort out the permutation vs. combination question. Hmmmm.

Well, if I thought about this like n choose 3 combinations without replacement the formula would be n!/(3!(n-3)!). But that would mean that if we have a square made up of red(s), green(s), and blue(s), this arrangement will only be counted once. But we know that it matters if the 2 toothpicks are both red, green, or blue, so I could take this combination formula and multiply it by 3. That would account for aabc, bbac, and ccab. Also, remember we determined that choosing 2a’s, 1b and 1c actually yields 3 results (aabc, aacb, and abac). So we multiply the formula by 3 again. So we get 3*3*n!/(3!(n-3)!) = 3/2*n*(n-1)*(n-2).

If that doesn’t sit well with you, then think about n choose 3 permutations without replacement. Back to my very specific color choosing method, remember that the first color is for the "2 toothpicks." In the permutation mind set, this means that "red, blue, green" and "green, red, blue" are counted differently, which is a good thing. But "red, blue, green" and "red, green, blue" are also counted differently, which is not good. Why? Because I’m planning on multiplying everything by 3 since, again, choosing 2a’s, 1b and 1c actually yields 3 results (aabc, aacb, and abac). But choosing 2a’s, 1 c and 1 b (which is counted differently) yields the same 3 results (aacb, aabc, acab). So I have to also divide by 2 to account for the duplicates. So the formula is 3/2*n!/(n-3)! = 3/2*n*(n-1)*(n-2).

Oy! I hope I made some sense in there. I apologize for flipping back and forth between abc and red green blue stuff. Anyways, here is the final formula:

S = (aaaa) + (aaab) + (aabb) + (aabc) + (abcd)
S = [n]+[n(n-1)]+[n(n-1)]+[3/2*n(n-1)(n-2)]+[1/12*n(n-1)(n-2)(n-3)]
S = [n]+[n^2-n]+[n^2-n]+[3/2(n^3-3n^2+2n)]+[1/12(n^4-6n^3+11n^2-6n)]
Ok, I won’t bore you with simplifying any more. If I messed up, someone will tell me =)
S = 1/12*[n^4 + 12n^3 – 37n^2 + 18n]