>>1767
I think we basically need to prove the attached image. It seems to work in general but I'm too much of a brainlet to think about how you could prove this. Probably by induction somehow would work.

>>1769
You can actually change the summation bound to k=0..n and still have it work. But induction seems trickier since trying to induct on n changes the inner expression which depends on n in addition to k.

>>1769
It took me a while but I think I get it now: you've generalised it as x^n. x^n is equal to the attached image. Alright! But yeah, still needs proof.

>>1771
Yeah that's what I meant. Sorry if it was unclear. I've tried the induction approach and I don't think it's the right way to go about it. I can't find any way to get it in the right form.

>>1771
I've got a hunch that you might be able to approach this via a combinatoric proof, specifically putting it in a form similar to that of "principle of inclusion exclusion".

Let x be the number of bins and n be the number of balls. Then the number of ways to put x balls into n bins is x^n.

We can try to count this in a different way: Form all bin-ball pairings (there are x*n) of these, and we pick n of these. This is (x*n C n). Now out of these there is a problem: not every ball among the pairings may a unique bin. Particularly,

1) Some pairings are invalid (ball 1 + bin 1 & ball 1 + bin 2) is invalid because ball can only go in 1 bin
2) Some balls may not appear in our chosen pairings

These are in a sense "complementary" issues. If we have a duplicate like (ball 1 + bin 1 & ball 1 + bin 2) there must necessarily be some other ball that is not chosen (because we choose n total pairings and we have n total balls).

Here's where things get sketchy and I'm not sure. It appears if we just solve the issue of "some balls not appearing in our chosen pairings" then we get the right answer directly.

We do that via principle of inclusion exclusion: we subtract out pairings in which at least one ball doesn't appear. If ball 1 doesn't appear then there are (n - k C n) possible pairings we could have chosen. Similarly if ball 2 doesn't appear, etc. so we have total of n * (n - k C n) things to subtract if one ball doesn't appear. But if just subtract this out we'll have undercounted the number of ways in which 2 balls don't appear, so we add back in (n C 2) * (n - 2k C n), and so on (this is standard application of principle of inclusion-exclusion. Reply back if this part isn't clear and I'll try to clarify).

That explains each term in the sum.

Now the only question remaining for me is why we don't have to address the issue of some pairings being invalid (ball 1 + bin 1 & ball 1 + bin 2 being chosen).

I feel this is because if such a scenario occurs we can come up with a scheme to give the ball's duplicate bin to the ball that did not have a bin (remember that they are complementary). This part isn't watertight to me.

>>1773
Sorry for the triple post but I think I got it. The reason is that every invalid pairing corresponds to at least one ball being left out and vice-versa (the complementary thing I mentioned). So thus subtracting out all the invalid pairings is all you need to do.

Also to expand on the inclusion-exclusion stuff in case it wasn't clear, we want to subtract out "# of ways at least one ball is left out" which is "# of ways ball 1 is left out" union "# of ways ball 2 is left out" ... union "# of ways ball n is left out" which by inclusion exclusion is "# ways ball 1 left out" + "# of ways ball 2 left out" + ... "# of ways ball n left out" - (# ways ball 1 and ball 2 left out) - ... - (# of ways ball n -1 and n - 2 left out) + "# of ways ball 1 and 2 and 3 left out" + ... and so on (basically just think of a venn diagram).

Thank you for sharing the problem OP, it was interesting to think about.

>>1774
I don't have time to read what you typed up for now but just want to say that I just found out that "Combinatorial" is a kind of vague word used to describe a field of Maths. This is actually "Expressing Polynomials in terms of Combinations".

>>1774
>So thus subtracting out all the invalid pairings is all you need to do.
I at least understand this part of what you're saying. The whole reason I stumbled upon this to begin with was that I was watching a TV Show with my sister. There are 11 men and 11 women. How many possible (heterosexual) pairings are there? My first thought was to solve the problem with combinations so I did 22 choose 2. Seemed simple enough, I mean, there's 22 people in the house in total so 22 choose 2 should suffice for the calculation but it doesn't because it also includes all the possible homosexual pairings. My moment of genius was to realise that you could just take away all the possible male-male pairings (11 choose 2) and then take away all the possible female-female pairings (11 choose 2 again). What I didn't expect was to get the final answer of 11^2.

(11*2) Choose 2 - 2*(11 Choose 2) = 11^2

Do you think you can use your ball-bin explanation and apply that to the scenario of x^2 in terms of combinations? Maybe if I saw it in application, I'd understand it better.

>>1774
Also, since I originally stumbled upon this dilemma when trying to calculate the total number of possible pairings amongst a species consisting of two sexes, rather than balls and bins, do you think you could apply it to the scenario of a race with three sexes (but only a trio with one of each of the three sexes can produce a child)?

Or, if sticking to balls and bins, could you draw pictures too?

>>1777
Not sure if I understand what you're getting at, but combinatorics is a field of math and I'd certainly put this in that category.

>My moment of genius was to realise that you could just take away all the possible male-male pairings
Yeah exactly! And your example actually *is* inclusion-exclusion applied to the case of n = 2 I think (expand out the summation and you should find that the terms match up)!

>do you think you could apply it to the scenario of a race with three sexes (but only a trio with one of each of the three sexes can produce a child)?
I'm not sure I understand what you meant. I'll give a concrete example for x = 3 bins and n = 4 balls though (so the number of ways to assign them is 3^4 = 81) (in your example I think this might correspond to each bin being one of the three genders). Also I'll stick to balls and bins if that's ok with you since that's a bit easier to visualize for me.

So we know that the number of ways to put 4 balls into 3 bins (with each ball going in only one bin and every ball going in some bin) is 3^4 (3 choices for the first ball * 3 choices for second ball * 3 choices for third ball * 3 choices for fourth ball). Now let's count this a different way. Form all possible ball/bin pairings:

ball 1 - bin 1
ball 1 - bin 2
ball 1 - bin 3
ball 2 - bin 1
ball 2 - bin 2
ball 2 - bin 3
ball 3 - bin 1
ball 3 - bin 2
ball 3 - bin 3
ball 4 - bin 1
ball 4 - bin 2
ball 4 - bin 3


There are 4*3 of these. Out of these, we pick 4 such pairings. There are (4*3 C 4) = 495 ways to do this.

Now every valid way to put the balls into the bins is included as part of this 495, but we've also included some invalid ways to do it (namely cases such as picking "ball 1 - bin 1" and "ball 1 - bin 2" and "ball 4 - bin 1") are illegal since we want each ball to land in only one bin. Particularly, we wanted each ball going in only one bin and every ball going in some bin, so the pairings we picked can be illegal if there is some ball going in more than 1 bin, or some ball that hasn't been picked at all.

The key insight is that the two illegal conditions are actually the same: because there are n balls and we've picked n pairings, if you pick a duplicate ball that means there must be some other ball that hans't been included in our pairing, and vice-versa. Or in other words, if a pairing is illegal because it has some ball going to multiple bins, it is also illegal for the reason that there is some ball that has not been included. So all we need to do is subtract out from 495 the number of pairings where at least one ball has not been included.

Now we apply the inclusion-exclusion principle to find the number of pairings where at least one ball has not been included. The number of pairings where at least one ball has not been included is the union of the pairings where ball 1 is not included, ball 2 is not included, ball 3 is not included, and ball 4 is not included.


By the inclusion-exclusion principle we have that

|A ∪ B ∪ C ∪ D| = |A| + |B| + |C| + |D| - |A ∩ B| - |A ∩ C| - |A ∩ D| - |B ∩ C| - |B ∩ D| - |C ∩ D| + |A ∩ B ∩ C| + |A ∩ B ∩ D| + |B ∩ C ∩ D| + |A ∩ C ∩ D| (where |A| the number of elements in the set A).

(Note that the above is just an extension of the simpler case |A ∪ B| = |A| + |B| - |A ∩ B| which should become clear if you stare at the venn diagram. Then you can extend it to 3 sets, and then 4).

Applied to our particular case, A is the set of all pairings where ball 1 is not included, B is the set of all pairings where ball 2 is not included, ..., D is the set of all pairings where ball 4 is not included. The number of pairings where ball 1 is not included is (12 - 3 C 4) (because we are excluded all pairings with ball 1, and there are 3 of those). Same for ball 2 .. ball 4. So the first term to subtract out is 4 * (12-3 C 4) = 9C4.

Now we add back in the number of pairings where ball 1 and ball 2 are both not included. This leaves (12-6 C 4). Same for all possible 2 ball combos. How many such two ball combos are there? 4 C 2 of course! So we add back in (4 C 2) * (12-6 C 4).

Then we subtract out the number of pairings where ball 1 and ball 2 and ball 3 are not included. This leaves (12-9 C 4). Same for all possible 3 ball combos. There are (4 C 3) such combos, so we subtract out (4 C 3) * (12-9 C 4).

So in total we have:

495 - 4 * (12-3 C 4) + (4 C 2) * (12-6 C 4) - (4 C 3) * (12-9 C 4) = 81.

Which is what we expected.

>>1779
>>1779
I'm still in the process of trying to understand this post but for the time being, I have another question:
Is there any significance in applying calculus here? I've got x^3 expressed in terms of combinations and I've got x^2 in terms of combinations so it's not too crazy to triple the x^2 one (i.e. 3x^2) and announce one sum of combinations to be the derivative of the other. Does that yield anything interesting?

Also, with this ball and bin analogy, am I understanding you correctly when it's possible for one bin to have two balls?

>>1780
>it's possible for one bin to have two balls?
Yes two different balls can go in the same bin, but a single ball can go in only one bin and every ball must go in some bin

> derivative of the other. Does that yield anything interesting?
No I don't think so since nCr doesn't make sense for non-integers. It's also pretty contrived so I don't think there's any direct interpretation. You can make 1 = 1 turn into some complicated looking thing by stringing together identities but it doesn't necessarily mean it'll have a direct interpretation.

I cannot believe I made this thread a year ago. I am so convinced it's only been months.

This thread is very unusual. It's quite clear that somebody already did generalise my observation. It's just that I didn't really remember it. I guess it's because all I remember from this thread is the ball and bin stuff that I didn't get and since the generalisation generalises for x^n whereas I generalise for n^a, the generalisation of this thread just wasn't in my mind.

I do think it's odd that the generalisation in the first post uses x^n. I'd imagine you'd use x for real numbers whereas you'd use n for natural numbers, as is the case with what I'm doing.

Well anyway, here's the generalisation I derived. I guess since I derived it myself, I'm able to use letters that make more sense to me. Plus, it's an actual complete equation.

Perhaps in time, with a better understanding of Maths, I can return to this thread with real updates. For the time being though, it seems I've merely reinvented (and prettied up) the wheel.

>>1979
Why do you write like you're trying to do a 19th century aristocrat impression?

Maths is for nerds.

>>1980
Why, let the stricken deer go weepe!

>>1979
>3) Clarity regarding what the term is for this field of study my question would fit into (if there is one)
This seems to be a specific case of the Binomial theorem where y is 0.

>Perhaps in time, with a better understanding of Maths, I can return to this thread with real updates. For the time being though, it seems I've merely reinvented (and prettied up) the wheel.
What updates do you plan on returning with? I mean, I don't get whether you are trying to understand it or to come up with a different proof or something.

>>1983
>specific case of the Binomial theorem where y is 0.
I don't think you can apply this directly. Binomial theorem states that

(x+y)^n = Sum{nCk x^(n-k) y^k}. Substituting y=0 into this just collapses the sum to its first term, which is x^n. Additionally the expression OP has involves alternating sums of binomial coefficients.

I'm pretty sure the combinatorial proof posted is valid. I'm not sure if you can find a nice algebraic proof for it. I don't recall ever seeing an algebraic proof for binomial theorem (only the combinatorial one and induction. You could probably find some sort of inductive proof but I couldn't go anywhere with that.

>I mean, I don't get whether you are trying to understand it or to come up with a different proof or something.
I agree that there's not too much to generalize from this particular problem. However if OP is interested in this sort of stuff he should look up "combinatorial proofs." You'll find lots of delightful identities similar to the one he posted, which can be proved with very clever combinatorial arguments. Things such as sum{k=0..n, nCk)^2} = (2n)C(n).

One person said that this might just be the binomial theorem. I decided to explore this. From Wikipedia, one can see the formula for the binomial expansion when applied to (1+x)^n. I decided to apply this and substitute my result for n^a to see what emerges. This doesn't seem to resemble anything I've seen before. I must confess that I have seen "generating functions" on Wikipedia but even then, they're not similar to what I have here.
I hope the colour-coding makes my work easier to follow.
I think I'll return once more to post the equation for (m+n)^a at which point, the binomial theorem will be fully expressed as a linear combination of binomial coefficients. After that, there's nothing left but to derive a proof of the original rule I stumbled upon.

>>1983
The goal I intend to tackle at some point is to prove the formula I discovered i.e. that n^a can be expressed as a linear combination of binomial coefficients (or one could call it a a finite, alternating series of combinations, whichever one is most intuitive to you). As it stands, it seems to merely "work". That one side of the equation is the equivalent of the other remains unexplained.

>>1984
>I'm not sure if you can find a nice algebraic proof for it. I don't recall ever seeing an algebraic proof for binomial theorem
I don't know if there's a proof for the binomial theorem but nonetheless, I believe there might be an algebraic proof for this rule I've stumbled upon i.e. an algebraic proof that one is the equivalent of the other.

>I agree that there's not too much to generalize from this particular problem
What makes you so certain that I couldn't stretch this to complex numbers and have imaginary binomial coefficients?
Also, I researched "summation of binomial coefficients" and so I've seen what you speak of. It's very interesting that somebody already found a way to talk about polynomials in terms of binomial coefficients but the formula presented didn't seem similar to what I found and it spoke of concepts beyond my current understanding. Also, there was no alternation in the summing of the coefficients.

>>1988
Since you're familiar with generating functions, here's a proof based on that. I think this is the cleanest algebra-only proof you'll be able to get for this, since usually proving combinatorial identities can get really tricky in general and there's no nice structure to this problem that you can induct over.

>What makes you so certain that I couldn't stretch this to complex numbers and have imaginary binomial coefficients?

You can have those of course; I think you'd have to use the generalized notion of a binomial where factorial is replaced by it's analytic continuation (gamma function). Once you go there I'm not sure if the proofs given (either combinatorial or via generating functions) still hold, since you've got issues of convergence to worry about.

>>1989
I'd seen the generating functions on Wikipedia however I did not understand them. I must confess that presently, they are beyond my knowledge. This thread is definitely something I will return to another time.

Japanese university math is pretty advanced (relative to the equivalent in US).

Post edited on 2nd Jul 2020, 8:44pm

>>2041
This just looks like sequences and (finite) series, though.

OP, you did well in asking if there was such a subject beforehand. Lately I was asking myself if there was something on sequences that are like arithmetical progressions, but with a different ratio between every number. I research deep in every possible related topic and couldn't find anything, even describing the problem didn't help. I ended up finding some formulas of my own, in the end, and was even going to post them here and ask about, but eventually I found they actually exist and are called quadratic sequences. There isn't a lot about them, though. The existing formulas are very different from the ones I made, and it appears that there are (as I suspected) even higher orders of magnitude, like cubic etc. What do you guys think of this whole thing?

>>2045
I think you can just generalize everything by writing it as a recurrence relation. For a quadratic relation we know that we must have

d(n) = f(n+1) - f(n) = an + b, which implies that f(n+1) = f(n) + an + b.

Now for the particular case of quadratic sequences I think finding a general formula for the nth term is relatively straightforward because we know how to do sums of arithemtic sequences, so you can apply this to find d(1) + d(2) + ... + d(n) which immediately gives you a formula for what f(n+1) is. Same thing applies for "cubic sequences" as well and so on since we have nice closed form solutions for those.