I'm having trouble seeing the big picture of this proof.

  • Context: Undergrad 
  • Thread starter Thread starter Terrell
  • Start date Start date
  • Tags Tags
    Picture Proof
Click For Summary

Discussion Overview

The discussion revolves around understanding a proof related to counting r-combinations of a set X that do not contain consecutive integers. Participants are exploring the concept of bijections and how they relate to the proof's validity.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested

Main Points Raised

  • Some participants express confusion about how the proof demonstrates that (n-r+1, r) represents the number of r-combinations of X without consecutive integers.
  • There is a question about whether the issue lies in the understanding of the bijection or in how the establishment of the bijection proves the result.
  • One participant proposes that after applying the bijective function, the original set and the new set have the same number of elements, leading to the conclusion about the number of ways to choose r-elements.
  • Another participant challenges the assertion that the original set consists of non-consecutive integers while the new set consists of consecutive integers, suggesting that this may not be necessarily true.
  • There is acknowledgment of a potential misinterpretation regarding the phrasing of the sets, specifically the difference between "consists of" and "may contain."

Areas of Agreement / Disagreement

Participants do not reach a consensus on the proof's clarity or correctness, with multiple competing views and uncertainties remaining regarding the bijection and the nature of the sets involved.

Contextual Notes

Some participants note limitations in the phrasing used to describe the sets, which may affect the understanding of the proof's validity. There is also an unresolved discussion about the implications of the bijection.

Terrell
Messages
316
Reaction score
26
I don't see how it proves that (n-r+1, r) is the number of r-combinations of X which contain no consecutive integers.
 

Attachments

  • bijective proof.png
    bijective proof.png
    20.6 KB · Views: 492
Physics news on Phys.org
Terrell said:
I don't see how it proves that (n-r+1, r) is the number of r-combinations of X which contain no consecutive integers.
Is it that you do not see that it is a bijection, or that establishment of the bijection proves the result?
 
haruspex said:
Is it that you do not see that it is a bijection, or that establishment of the bijection proves the result?
i can't see that the establishment of the bijection proves the result. please do help me
 
haruspex said:
Is it that you do not see that it is a bijection, or that establishment of the bijection proves the result?
after giving it some thought, i think I've got it. after applying the bijective function to set S, we can observe that the number of elements of the original set is equal to the number of elements in the set produced by the bijective funtion. however, the only difference is that the original set consists of non-consecutive integers and the "new" set consists of consecutive integers. since both of the sets contains n-r+1 elements, the number of ways to choose r-elements from the "new" set is (n-r+1, r) which should also equal for the original set. did i got that one right?
 
Terrell said:
after giving it some thought, i think I've got it. after applying the bijective function to set S, we can observe that the number of elements of the original set is equal to the number of elements in the set produced by the bijective funtion. however, the only difference is that the original set consists of non-consecutive integers and the "new" set consists of consecutive integers. since both of the sets contains n-r+1 elements, the number of ways to choose r-elements from the "new" set is (n-r+1, r) which should also equal for the original set. did i got that one right?
Yes.
 
  • Like
Likes   Reactions: Terrell
haruspex said:
Yes.
I think you were being too generous. When Terrell said, "original set consists of non-consecutive integers and the "new" set consists of consecutive integers.", he was referring to S and f(S) and that is in fact not necessarily true.
 
  • Like
Likes   Reactions: Terrell
Zafa Pi said:
I think you were being too generous. When Terrell said, "original set consists of non-consecutive integers and the "new" set consists of consecutive integers.", he was referring to S and f(S) and that is in fact not necessarily true.
You are right, I missed that it said "consists of" instead of "may contain", but that is probably just a minor slip in expressing it.
 
  • Like
Likes   Reactions: Terrell
haruspex said:
You are right, I missed that it said "consists of" instead of "may contain", but that is probably just a minor slip in expressing it.
Agreed.
 
  • Like
Likes   Reactions: Terrell

Similar threads

Undergrad Thinking about equality of infinite sets
  • · Replies 5 ·
Replies
5
Views
3K
Undergrad The set of nonzero values of pmf is at most countable
  • · Replies 3 ·
Replies
3
Views
4K
MHB How to prove an inequality with a direct proof?
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Proof of a fact about real numbers - transcendental and algebraic
  • · Replies 7 ·
Replies
7
Views
3K
Undergrad Is an algorithm for a proof required to halt?
  • · Replies 3 ·
Replies
3
Views
2K
High School Probability a randomly chosen natural number, which is not smaller than 𝑥, is greater than x?
  • · Replies 15 ·
Replies
15
Views
2K
Undergrad Understanding the Law of Iterated Expectation in Probability Derivations
  • · Replies 4 ·
Replies
4
Views
2K
Undergrad On Jensen's inequality for conditional expectation
  • · Replies 1 ·
Replies
1
Views
3K
MHB Probability of misprints on each page
  • · Replies 7 ·
Replies
7
Views
2K
Undergrad Help understanding conditional expectation identity
  • · Replies 1 ·
Replies
1
Views
3K