by mathslug » Tue Oct 16, 2007 11:28 pm
Wait a minute here...
Adam, I'm not sure if doing 1 to N combinations on the number works:
3C3 + 3C2 + 3C1 = 1 + 3 + 3 = 7
I was wondering if anyone has generalized a formula yet... I've been toying with this problem inductively for a while, and I have a method for solving it, but it feels wrong. The way I do it is the following...
Add one to start with. This is our base case where everything is different to start with. "One of each" if the number of things you're working with here is not one or less... then proceed to the next step.
Add N, where N is the number of things you are working with. This will take care of each case where you only get one kind of thing in your set. If the number of things you are working with is not 2, then proceed to the next step.
add N(N+1)/2!, i.e. sum of numbers 1 to N. This takes care of our first round of duplicate cases. If the number of things you're working with is more than 3 then continue to the next step.
add N(N+1)(N+2)/3! , and if the number of things you're working with is more than 4 then continue in likewise fashion.
I'm not sure if this method works correctly or not. I still havent proven it. I got it from careful inspection of the characteristics of each generarted set given 1-4 elements. I know it works for 1-4, but I'm hoping that someone can prove it for more than that.
For 3:
1 + N + N(N+1)/2 = 1 + 3 + 3*4/2 = 10
For 4:
1 + N + N(N+1)/2 + N(N+1)(N+2)/6 = 1 + 4 + 4*5/2 + 4*5*6/6 = 35
For 5: ?
1 + N + N(N+1)/2 + N(N+1)(N+2)/6 + N(N+1)(N+2)(N+3)/24 = 1 + 5 + 5*6/2 + 5*6*7/6 + 5*6*7*8/24 = 1+5+15+35+70 = 126?
Can anyone help? And if my method is wrong, how should I go about solving this in the future?
Zack