Choosing from identical objects of different types

  • I
  • Thread starter yucheng
  • Start date
In summary, the conversation discusses the best approach for solving a problem that involves selecting objects without replacement from a set with duplicates. The most promising methods suggested include the hypergeometric distribution, generating functions, and the use of PIE (Principle of Inclusion-Exclusion). While some sources provide incomplete or impractical solutions, others suggest using the multivariate hypergeometric distribution for calculating probabilities and defining the term "number of ways" for counting selections with identical items.
  • #1
yucheng
232
57
TL;DR Summary
I am asking about the general formulation. But to be concrete....

How many ways can we choose 6 objects from say {A,A,B,B,B,C,D,E,E,E,F,G,G,G}? (identical objects of different type)

Pure evil: What's the probability of choosing 2A's and 2 B's?

This can be formulated as partitions with constraints or choosing with finite replacement or choosing from identical objects of different types.
Do you have any comments? What's the most general way to solve it? Inclusion-exclusion (PIE) is impractical for general case. Where to read further on this problem?

Here's what I've found.

Hypergeometric distribution???
https://math.stackexchange.com/ques...-out-of-n-identical-objects?noredirect=1&lq=1

Generating functions: this is promising but incomplete. Is brute force expansion the only way to get the coefficient?
https://math.stackexchange.com/ques...replacement-from-a-set-that-contains-duplicat
https://math.stackexchange.com/a/2757736/767174

Generating functions: Perhaps more complete and concrete. But in the end, the author is unable to compute the coefficients (at least by hand) but still suggests PIE
https://math.stackexchange.com/questions/41724/combination-problem-with-constraints

Again PIE (with stars and bars)
https://math.stackexchange.com/questions/3047584/drawing-balls-with-a-finite-number-of-replacement

Slightly more comprehensive, but the author suggests PIE, which kills the brain for slightly more complicated problems
https://math.stackexchange.com/ques...mula-for-combinations-with-identical-elements

I think this is plain wrong!
https://math.stackexchange.com/questions/582788/distinct-combinations-of-non-distinct-elements?rq=1
 
Physics news on Phys.org
  • #2
To calculate probabilities I think you need the multivariate hypergeometric distribution, described here: https://en.wikipedia.org/wiki/Hypergeometric_distribution#Multivariate_hypergeometric_distribution
It is a generalisation of the hypergeometric distribution to cases where there are more than two categories (usually described as colours).

To count the "number of ways" we'd first need to define exactly what we mean by that, as the term becomes ambiguous when we have identical items.
 
  • Love
Likes yucheng

FAQ: Choosing from identical objects of different types

What is the concept of "Choosing from identical objects of different types" in combinatorics?

The concept involves selecting a certain number of objects from a collection where the objects are identical within their types but different across types. This is often addressed using the "stars and bars" theorem, which provides a way to determine the number of ways to distribute indistinguishable objects into distinguishable bins.

How do you apply the "stars and bars" method to solve these problems?

The "stars and bars" method is used to determine the number of ways to distribute n identical objects into k distinct bins. It involves representing objects as stars and dividers as bars. The number of ways to distribute the objects is given by the binomial coefficient C(n+k-1, k-1), where n is the number of objects and k is the number of bins.

Can you provide an example of a problem involving choosing from identical objects of different types?

Sure! Suppose you have 5 identical apples and 3 identical oranges. You want to choose 4 fruits. The number of ways to do this can be calculated by considering the different combinations of apples and oranges that add up to 4. This is a typical application of the "stars and bars" method.

What are some common applications of this combinatorial method?

This method is commonly used in problems involving partitioning, distributing resources, or forming groups where the objects are identical within their types. Applications can be found in fields like computer science (e.g., distributing tasks to processors), operations research, and even in everyday scenarios like distributing identical candies into different bags.

Are there any limitations or special considerations when using this method?

One limitation is that the "stars and bars" method assumes that the objects are truly identical within their types and that the bins or groups are distinguishable. If the bins are not distinguishable, or if the objects are not truly identical, other combinatorial methods may be needed. Additionally, care must be taken to correctly interpret the problem to apply the method appropriately.

Similar threads

I Proving inequality about dimension of quotient vector spaces
Replies
0
Views
821
I Conditional probability choosing from the objects
Replies
4
Views
2K
Possible webpage title: Understanding Combinations with Identical Objects
Replies
1
Views
2K
Equiprobable sample space: N Identical objects in K different containers
Replies
9
Views
2K
I have N different objects and I choose g out of them
Replies
2
Views
2K
I Why should a Fourier transform not be a change of basis?
2
Replies
43
Views
6K
I Recursive Ordinals and Creativity
Replies
4
Views
1K
I How Big of an Object Orbiting Closer to the Sun Than Earth Could Be Overlooked?
Replies
17
Views
3K
I Exploring ΛCDM Model: Cosmology Intertwined in 4 Pre-Prints
Replies
1
Views
2K
I The standard model from loop quantum gravity via spinors octonions
Replies
26
Views
2K

Hot Threads

Recent Insights

Back
Top