More direct approach to a combinatorial problem

1.1k Views Asked by At

Suppose we randomly arrange $n$ objects of which $s$ are of silver, $1$ is of gold and the remaining $n-s-1$ are of copper.

The question I looked at is:

what is the probability that all eventual predecessors of the golden object are of silver?

We could rephrase this as:

what is the probability that among the eventual predecessors of the golden object are no copper objects.

I defined the described event as $E$ and approached the answer by first defining $E_i$ (this for $i=0,1,\dots,s$) as the event that the golden object is on spot $i+1$ and its predecessors are all of silver.

Then we find:$$P(E_i)=\frac1n\binom{s}i\binom{n-1}i^{-1}=\frac1n\binom{n-1}s^{-1}\binom{n-i-1}{n-s-1}$$ and making use of the hockey-stick identity we arrive at:$$P(E)=\sum_{i=0}^sP(E_i)=\frac1n\binom{n-1}s^{-1}\binom{n}{n-s}=\frac1{n-s}$$

That is a nice result. So nice that IMV it clearly indicates the existence of more direct way to find it. I tried to, but failed.

So my question is:

Can you provide me a more direct solution?

Thank you for taking notice of this and sorry in advance if this appears to be a duplicate question.


Edit

My original question did not mention the word "copper" neither the rephrasing of the question that uses the word "copper". In my (narrow) thinking I was purely focused on gold and silver. This fact provided the blind spot that I am now released from.

In situations like this a sort of battle takes place within me. I am very eager to find the smart solution myself. I can pose it as a question but my pride first forbids me to do so. After some struggling I set this (stupid) pride aside and decide to show my shortcomings. A healthy process.

Thank you all for your answers.

4

There are 4 best solutions below

2
On BEST ANSWER

Lay down all the copper and gold coins. The probability that the gold coin is first is $\frac1{n-s}$.

1
On

In any given arrangement of the $n$ objects, glue the $s$ silver objects in place and cyclically permute the other $n-s$ objects (the gold one and the unspecial ones). Exactly $1$ of those $n-s$ cyclic permutations, namely the one with the gold object placed before all the neutral objects, will have the property that the gold object is preceded by only silver objects.

2
On
  • From the right end, fill all the copper objects with the gold one immediately after the copper ends, $Pr= \frac{1}{n-s}$

  • Intermingle the silver objects anywhichway in the row

0
On

The key insight I got while editing the Question to include Copper Objects is this : We do not want to count the number of ways , we only want the Probability !

We can start with $(n-s-1)$ Copper Coins.
We can put the gold coin at start or middle or else where. That is $(n-s-1+1)=(n-s)$ ways.
This is the Initial Order , where "favourable" is $1$ (When gold is at Start) , "unfavourable" is $(n-s-1)$ (When is gold is not at Start) , "total" is $(n-s)$.

We can then put the Silver Coins in various Positons.
Each Initial Order will give $X$ Eventual Orders , where calculating $X$ is Cumbersome , involving various Summations & factorials.

Probability is $\frac{1 \times X}{(n-s) \times X}$
Thus we get the Probability Directly , without calculating $X$ , which will cancel !