Combinatorics

[MJK]

I'm quite sorry to keep using this forum this way.. but I just feel so uncomfortable unanswered, so.

6236754_1402771389.jpg (5.17 KiB) Viewed 6458 times

This is everything.

Mathics, a freeware alternative to Mathematica, claims the above true.

Code: Select all

(Input)
C := (#1)!/((#2)!*(#1-#2)!) &
Sum[C[n, k], {k, 0, s-1}] == Sum[2^(k-1)*C[n-k, s-k], {k, 1, s}]

(Output)
True

While I find this computer proof so fast and wonderful, it unfortunately does not explain its reasoning.

Can anyone please help me with this problem?

[schawipp]

Just a question on the syntax - does _nC_k stand for the number of combinations, where k elements are selected out of n (i.e. n!/(k!(n-k)!)?

[MJK]

Just a question on the syntax - does _nC_k stand for the number of combinations, where k elements are selected out of n (i.e. n!/(k!(n-k)!)?

Sure, as you can see in the code.

[RBerenguel]

Hmmm I'd prove this by induction over the number of elements of the sum. I.e. first check a simple case (like S=3) to bootstrap your intuition. Then assume it's true for some number S-1 (capital s, so it is different from the arguments in the formula.) Write down the formulas for S, and try to arrange them so you get "something" + the S-1 case. The case S=3 or S=4 will help you realise how this can work.

[RBerenguel]

Meh, more easy:

The combinatorics C(n,k) are the coefficients when expanding (a+b)^n. So, the sum of all up to a certain number is like (1+1)^S. I guess it's easier using this relationship

[zorq]

...

C(n,k) is the number of ways one can choose k things from a set of n things.
The left hand side is the number of ways one can pick at most s-1 things from a set of n.
Put your things in a row, and look at any of these choices. Let k be minimal such that this choice contains s-k from the first n-k things. Then k lies between 1 and s. The thing in position n-k+1 was not chosen, otherwise k could be decreased. An arbitrary subset of the rest could be chosen. So there are 2^{k-1} C(n-k,s-k) choices that give rise to this k. Together these are all, so both sides are equal.

[cyclops]

I dont quite understand the solution in the last post. So here my try.
These binomial problems are often simplified if you visualize with Pascal's triangle. For typographical reasons I use X for empty spots and T for 10.

0X0X0X0X0X1X0X0...
X0X0X0X0X1X1X0...
0X0X0X0X1X2X1X0...
X0X0X0X1X3X3X1X0...
0X0X0X1X4X6X4X1X0...
X0X0X1X5XTXTX5X1X0...

It is well known that every entry is the sum of its two diagonal neighbours above.
In the red sum the green 6 is contained one time. But the green 3 two times. One time via the 10 and one time via the 5. And the green 1 is contained 4 times in the red sum. Two times via the blue 1 and two times via blue 4.
So we have: the red sum = 16 = 1*6 + 2*3 + 4*1. as your theorem states.
It should now be easy to formalyze this "proof".
For example by induction: ( short hand ) The red sum is the green 6 + 2 times the blue sum ( 4 + 1 ) . But by induction is the blue sum is the green 3 + two times the green 1. So 1 + 5 + T= 1*6 + 2*3 +4*1. qed ( after obvious formalysation ).
Next it would be interesting to understand how the computer establishes this theorem. Probably hypergeometrical series are the key.

[zorq]

I dont quite understand the solution in the last post. So here my try.
Next it would be interesting to understand how the computer establishes this theorem. Probably hypergeometrical series are the key.

Zeilberger-Wilf theory provides automatic summation methods for such identities, so verification is completely routine.
Still it is a nice game to provide 1-1 correspondence proofs, where one finds a set that is counted by the left hand side, and also by the right hand side.

Let me redo your example.
We have n=5, s=3 and are showing that C(n,0) + ... + C(n,s-1) = C(n-1,s-1) + 2C(n-2,s-2) + 4C(n-3,s-3) + ... + 2^{s-1}C(n-s,0). In this case C(5,0)+C(5,1)+C(5,2) = C(4,2)+2C(3,1)+4C(2,0).
The left hand side is the number of subsets of size at most 2 in a set of 5: {}, {1}, {2}, {3}, {4}, {5}, {1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {2,4}, {2,5}, {3,4}, {3,5}, {4,5}.
For each of these subsets, find the smallest k such that it contains 3-k elements from {1,...,n-k}.
The value k=1 works for {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}.
The value k=2 works for {1}, {2}, {3}, {1,5}, {2,5}, {3,5}.
The value k=3 works for {}, {4}, {5}, {4,5}.
The sizes of these three sets are C(4,2) and 2C(3,1) and 4C(2,0).

You see that our solutions are basically the same.

[cyclops]

It took me quite some time to understand your reasoning. So I took the arrogance to rewrite it in my own language.

In the equation below you have partioned the left hand side into 3 disjunct parts.
Notation:

<1..4>₂ stands for all 2-element subsets of {1..4}
<4,5> all subsets of {4,5}
<> empty set
P X Q for all unions of one element from P with one from Q where P and Q are disjunct subsets of {1..5}.
+ for disjunct unions

{ {}, {1}, {2}, {3}, {4}, {5}, {1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {2,4}, {2,5}, {3,4}, {3,5}, {4,5} } =
<1..4>₂ X <> + <1..3>₁ X <5> + <1..2>₀ X <4,5>
The knack in your proof is to see that this equation is correct.
From this MJK's formula follows easily.
Though we proof the same formula, I think the proofs are essentially different.