File
154790467287.png
- (6.71KB
, 392x448
, CodeCogsEqn.png
)
Expressing Polynomials in terms of Combinatorials
Anonymous
01/19/19(Sat)05:31
No. 1767
[Edit]

Greetings.

I recently noticed that one could express a polynomial in terms of combinatorials and so I am curious as to how far one could go with this.

My requests are:
1) An expression of n^4 purely in terms of combinatorials
2) A method for finding these combinatorial-expressions
3) Clarity regarding what the term is for this field of study my question would fit into (if there is one)

I notice Pascal's triangle appears consistently (albeit with the rightmost '1' cut off) so perhaps, keeping the positive-negative alteration in mind, the n^4 combinatorial-expression is actually quite predictable but I have yet to test this and to be honest, I'd rather find a method than apply what I predict could be the cheat-sheet.

>>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.

>>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.