Counting Problem: How to Get the Right Answer?

In summary, the conversation discusses the number of k-element subsets that have k-1 elements in common with a specific subset, A, of {1, 2, ..., n}. The number of choices for B that fulfill this condition is k(n-k), and if the condition is interpreted as "at least k-1 elements in common," the total number of choices is k(n-k)+1. The speaker had trouble with overcounting and realized that their previous calculation of (n-k+1)k - \frac{k(k-1)}{2} was not always accurate.
  • #1
morphism
Science Advisor
Homework Helper
2,016
4
Suppose you pick a k-element subset of {1, 2, ..., n}, call it A. How many of the other k-element subsets have k-1 elements in common with A?

I've been at this for quite some time, but I always overcount. Can anyone help me out? My last attempt gave me [itex](n-k+1)k - \frac{k(k-1)}{2}[/itex], which isn't always correct. I feel I'm missing something simple.
 
Last edited:
Physics news on Phys.org
  • #2
How many choices for B are there such that B is a k-element subset with k-1 elements in common with A? There are k-choices for the element of A that B doesn't have, and n-k choices for the element of AC that B does have, giving a total of k(n-k) choices for B. And if by "k-1 elements in common" you mean "at least k-1 elements in common," add 1 to include A.
 
  • #3
Thanks! My problem was that I always took n-k+1 for the element of A^c that B doesn't have, which forced me to overcomplicate things thinking my reasoning was wrong, when in fact it was only a simple overcount.
 

Related to Counting Problem: How to Get the Right Answer?

1. What is the counting problem?

The counting problem is a mathematical concept that involves determining the total number of possible outcomes for a given scenario or set of events.

2. How do you approach the counting problem?

There are several techniques to approach the counting problem, such as using permutation or combination formulas, creating a tree diagram, or using the multiplication principle. The best approach depends on the specific problem and the type of information given.

3. What is the difference between permutations and combinations?

Permutations involve the arrangement of objects where the order matters, while combinations involve the selection of objects where the order does not matter. Permutations use the formula nPr = n!/(n-r)! and combinations use the formula nCr = n!/r!(n-r)!, where n is the total number of objects and r is the number of objects being selected.

4. How do you know if you should use permutations or combinations?

You should use permutations when the order of the objects matters, such as arranging a group of people in a line. You should use combinations when the order does not matter, such as selecting a group of people to be on a team.

5. Can the counting problem be applied to real-life situations?

Yes, the counting problem can be applied to real-life situations, such as counting the number of possible outcomes in a game of chance, determining the number of possible combinations for a password, or calculating the number of ways to arrange a set of items on a shelf.

Similar threads

  • Calculus and Beyond Homework Help
Replies
17
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
678
  • Calculus and Beyond Homework Help
Replies
18
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
532
  • Calculus and Beyond Homework Help
Replies
3
Views
625
  • Calculus and Beyond Homework Help
Replies
4
Views
449
  • Calculus and Beyond Homework Help
Replies
4
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
2K
Back
Top