2
$\begingroup$

What is the number of ways that I can select subset (k) from larger set (n) where the order is NOT important and without replacement (I can't use the element more than once).

For example I have the set A={1,2,2} and I need to select only two number from the set. How many possibility are there?

will, manually its {(1,2),(2,2)} so the answer is 2. How to get three directly without listing the possibilities???

Second thing, what if I have the same example but with replacement (I can use the element more than once)>>>> the answer is {(1,1),(1,2),(2,2)}, so 3 possibilities, How to get 3 directly ??

$\endgroup$
5
  • 1
    $\begingroup$ By definition, 'where the order is NOT important and without replacement (I can't use the element more than once)' is superfluous. Sets do not have order, and cannot contain repeated elements. $\{1,2,2\}$ would be treated as $\{1,2\}$ if considered to be a set. $\endgroup$
    – Shuri2060
    Commented Jul 13, 2017 at 18:55
  • 1
    $\begingroup$ You should probably use multisets instead in your question. en.wikipedia.org/wiki/Multiset $\endgroup$
    – Shuri2060
    Commented Jul 13, 2017 at 18:57
  • $\begingroup$ You can imagine it as a bag with three pins, 2 blue and one red. and you must select only two pins where order is important, the only possible outcome are {{B,B},{B,R},{R,B}} $\endgroup$
    – Love Eva
    Commented Jul 13, 2017 at 18:58
  • $\begingroup$ I understand your intention, but sets are different from what you're referring to. You should be writing the example you just gave as $\{(B,B),(B,R),(R,B)\}$, ie. a set of ordered pairs. $\endgroup$
    – Shuri2060
    Commented Jul 13, 2017 at 19:01
  • $\begingroup$ Yes its a typo, just corrected the notation. $\endgroup$
    – Love Eva
    Commented Jul 13, 2017 at 19:06

1 Answer 1

1
$\begingroup$

First of all, I'd like to make some important distinctions:

A set is a collection of non-repeated elements without order

A multiset is a collection of elements without order

A tuple is a finite ordered list of elements

It's important to bear in mind the distinction between these and to know which one you need.

For example, in your question, it's clear you're referring to multisets rather than sets, but you aren't referring to tuples for the subsets you're taking as you want the order not to be important.


Partial answer for the last question:

If you allow replacement, then you may as well consider sets rather than multisets as $\{A,B,B\}$ will give the same result as $\{A,B\}$. All you're interested in is the number of distinct elements in this case.

Therefore the question can be rephrased as: How many multisets are there of $k$ elements such that all elements belong a fixed set $S$ of size $n$?

The solution to this is $n+k-1\choose n$


Explanation:

This uses the solution to the Stars and Bars problem. There are $k$ stars and $n-1$ bars. To see how, let us consider the number of times each element in $S$ appears. Each element can appear between $0$ and $k$ times, and the sum of these appearances for each element must be $k$.

In other words, we're interested in how many ways $k$ can be split up between 'jars' which represent each element of $S$.

Example:

Let $S=\{A,B,C,D,E\}$ and $k=5$. Some possible multisets may be $\{A,A,A,C,D\}$ and $\{B,B,D,D,D\}$. This can be represented with ★★★||★|★| and |★★||★★★| respectively.

The stars represent the number of appearances of a certain element, and the bars represent the dividers between each letter. For the first example:

$$\underbrace{★★★}_{\text{Appearances of: }A}|\underbrace{}_B|\underbrace{★}_C|\underbrace{★}_D|\underbrace{}_E$$


$\endgroup$
4
  • $\begingroup$ This is correct for the case of allowing replacement. What about if replacement is not allowed ? @shuri2060 $\endgroup$
    – Love Eva
    Commented Jul 13, 2017 at 20:11
  • $\begingroup$ @LoveEva I've given it some thought and a little research, and the answer isn't as simple - it's going to depend on the individual frequencies of each element in the multiset. I'll edit it in if I come up with it $\endgroup$
    – Shuri2060
    Commented Jul 13, 2017 at 20:31
  • $\begingroup$ I did find the method "generating functions" from the link mathforum.org/library/drmath/view/56197.html is it always true ? if yes is there any fast way to find the coefficient right away without expanding ? @shuri2060 $\endgroup$
    – Love Eva
    Commented Jul 13, 2017 at 20:47
  • $\begingroup$ @LoveEva I haven't read all of it, but I gather that finding the coefficient of the polynomial in the bottom section is one of the ways of solving the problem. As far as I can see, it works. Yes, you can find the coefficient right away without expanding. You can use the method suggested there, but you can also find it by inspection for small $n$. All you need to do is systematically count the number of ways of selecting powers of $x$ which add to $k$ from each bracket. But that effectively is the same as counting the number of ways in the original problem. $\endgroup$
    – Shuri2060
    Commented Jul 13, 2017 at 21:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .