1
$\begingroup$

If I have the following set {$1,2,3,4$}, and I want to know the number of possible lists of size 3 that contain $1$ and $2$ in them, I tried the following, and think of it as the number of ways to select 3 elements:

$2·1·2=4$ as in "number of choices for the first number, then the second... " But the actual number is 12.

The only way I can do it is by observing that I have two sets {$1,2,3$} and {$1,2,4$} And each one has 6 permutations, and therefore 12 total permutations or lists.

How can I find the number of lists and subsets that satisfy the property of containing 1 and 2?

$\endgroup$
4
  • $\begingroup$ Your first method works too : "total permutations" - ("permutations without 1" + "permutations without 2") $$4.3.2 - (3.2.1 + 3.2.1) $$ $\endgroup$
    – AgentS
    Sep 6 '14 at 10:08
  • $\begingroup$ By list you mean n-tuple? A subset isnt a ordered thing, it completely different the case for a 3-tuple and a subset of cardinality 3. Can you repeat elements on the lists/3-tuple? $\endgroup$
    – Masacroso
    Sep 6 '14 at 10:36
  • $\begingroup$ Yeah, that's what I meant. But I want a robust method to find both lists and subsets given such criteria. $\endgroup$
    – Hex4869
    Sep 6 '14 at 10:41
  • 1
    $\begingroup$ Apparently you want neither $(1,2,1)$, nor $(2,6,1)$, but I could not tell the first and hardly the second from your description. $\endgroup$
    – Carsten S
    Sep 6 '14 at 11:22
3
$\begingroup$

In fact, $2*1*2=4$ isn't that far away from your other solution. What you did is calculate the number of possibilities to have either $2$ or $1$ in the first place of your set and the other one on the second spot, with the remaining $3$ and $4$ taking the last one.

You did not, however, keep in mind, that $2$ and $1$ could also be in the second and third place or in the first and the third place. In the end, you have essentially three possibilities to form your set concerning placement of $2$ and $1$, and each possibility has four different ways of fulfilling the condition.

So you get: $3*2*1*2 = 12$ , which is the correct solution.

I hope that helped!

SDV

$\endgroup$
2
$\begingroup$

Let's say that you are looking for the number of sets of $\left\{ 1,\dots,n\right\} $ of size $m$ that contain $\left\{ 1,\dots,k\right\} $.

This comes to choosing $m-k$ members of this set from set $\left\{ k+1,\dots,n\right\} $ so there are $$\binom{n-k}{m-k}$$ possibilities.

If it comes to lists then each permution on one of these sets induces a new list, so there are $$\binom{n-k}{m-k}m!$$ possibilities.

$\endgroup$
2
  • $\begingroup$ But it doesn't work for $m=1$, containing {1}: (4-1)!/(1-1)!= 6 $\endgroup$
    – Hex4869
    Sep 6 '14 at 11:02
  • 1
    $\begingroup$ @Hex4869 It also workes for $m=1=k$. Note that $\binom{n-1}{0}=1$ for each $n\geq1$. Do not confuse it with $\frac{(n-1)!}{0!}$ $\endgroup$
    – drhab
    Sep 6 '14 at 11:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.