Combinatorics doubts

Question

Good morning folks,
I'm really struggling with combinatorics which I have to use to arbitrate tag collisions in RFID exercises for my IOT exams.
I'll also have a discrete math exam on combinatorics so I kind of know what we're talking about but apparently I'm unable to count.
The situation is the following: I have $r= 4 $ slots inside of which I can put one or more among $n = 3$ tags. In fact I have to explore all the possibilities.
A tag is resolved if it's alone to fit a slot.
So calling $S_i$ the event that $i$ tag are resolved I have:
$P(S_0) = (frac{1}{4})^4$ because for this to happen all three tags must go into the same slot.
$P(S_1) = ?$ This is why I opened the thread. I'm not able to compose the formula that counts all the possible configurations for which two tags go into one slot and one into another (i.e. one tag is resolved)
$P(S_2) = 0$ because there's no way you can let just two tag pass
$P(S_3) =  ?$ this should be related to the falling factorial $(4)_3$ I think as I have to count all the 3-permutations from a 4-set but I'm not sure the probability it's just the reciprocal of the falling factorial.
In general I have to be able to count this kind of situations but I can't generalize a formula that works often.
Thanks for the help!

Henry · Answer

There are $4^3=64$ ways of placing the tags.  Of these:

There are ${3 choose 3}{4 choose 1}=4$ ways of putting all three tags in the same slot and so a probability of $P(S_0)=frac{4}{4^3}=frac1{16}$ of resolving zero tags

There are ${3 choose 2}{4 choose 1}times {1 choose 1}{3 choose 1}=36$ ways of putting two tags in one slot and one in another and so a probability of $P(S_1)=frac{36}{4^3}=frac{9}{16}$ of resolving one tag

There are no ways of putting two tags each alone in slots and the third not alone and so a probability of $P(S_2)=0$ of resolving two tags

There are ${4 choose 1} times {3 choose 1} times {2 choose 1}=24$ ways of putting each tag alone in slots and so a probability of $P(S_3)=frac{24}{4^3}=frac{3}{8}$ of resolving all three tags

As a check, $4+36+0+24=64$ and $frac1{16}+frac{9}{16}+0+frac38=1$

Combinatorics doubts

One Answer

Add your own answers!

Ask a Question