Register to reply

Independent Sets of Cycles proof...Involves Combinations!

Share this thread:
rbzima
#1
Sep19-07, 06:35 PM
P: 86
1. The problem statement, all variables and given/known data

Let [tex]C_n[/tex] Recalling our notation from class, we know that [tex]I_0(C_n) = 1[/tex] and [tex]I_1(C_n) = n.[/tex] Prove that for [tex]k > 1,[/tex]

[tex]I_k(C_n)=\left(\frac{n}{k}\right)\left(\stackrel{n-k-1}{k-1}\right)[/tex]

2. Relevant equations

[tex]I_k[/tex] implies number of independent sets of size k
[tex]C_n[/tex] implies the cycle with n vertices.
Therefore, [tex]I_k(C_n)[/tex] implies the number of independent sets of size k in some cycle with n vertices.
[tex]I_k\left(C_n\right)=I_k\left(C_{n-1}\right)+I_{k-1}\left(C_{n-2}\right)[/tex]


3. The attempt at a solution

I've worked through the algebra to a point where it becomes rather disheartening, and it seems to be getting no where whatsoever. I've tried thinking of a combinatorial proof for this, however cannot come up with any scenario to think of or how it might be applied in this instance. If anyone can simply lead me in the right direction, that would be totally fantastic!
Phys.Org News Partner Science news on Phys.org
Guidelines for enhancing solar cells using surface plasmon polaritons
Trees and shrubs invading critical grasslands, diminish cattle production
Climate change will threaten fish by drying out Southwest US streams, research predicts

Register to reply

Related Discussions
Proof about operations on sets Calculus & Beyond Homework 2
More proof on sets help Set Theory, Logic, Probability, Statistics 2
Measure theory and independent sets Calculus & Beyond Homework 3
Proof of Permutation and Combinations formulas? Set Theory, Logic, Probability, Statistics 0