Let j and n be positive integers, with j ≤ n. An experiment consists of
choosing, at random, a j-tuple of positive integers whose sum is at most n.a) Find the size of the sample space. Hint: Consider n indistinguishable
balls placed in a row. Place j markers between consecutive pairs of balls,
with no two markers between the same pair of balls. (We also allow one
of the n markers to be placed at the end of the row of balls.) Show that
there is a 1-1 correspondence between the set of possible positions for
the markers and the set of j-tuples whose size we are trying to count.b) Find the probability that the j-tuple selected contains at least one 1.
For a), I thought this is basically stars and bars theorem 1 and based on the hint given it seems like it is. If so, I think the sample space is of size $\binom{n-1}{j-1}$, with each value in the j-tuple in the interval [1, n-j+1] (?). However, the question says the sum is at most n instead of equal to n, I’m not sure if that’s a typo or if I’m mis-interpreting the question.
For b), I’m completely stuck. I think I need to find the probability that the j-tuples that does not contain any 1s and then find the complement?
Best Answer
So i extend my comment a little. Recall that if $k>n$ then $\binom{n}{k}=0$ and so $$\sum _{k=0}^n\binom{k-1}{j-1}=\sum _{k=j}^n\binom{k-1}{j-1},$$ by the HockeyStick identity this sum equals $$\binom{n}{j}.$$ For the second part let's call your random tuple $\pi=(\pi_1,\cdots ,\pi_j)$ so that $$P(\pi \text{ has at least $1$ one})=1-P(\pi \text{ has no ones})=1-P(\pi _l>1 \text{ for }1\leq l\leq j),$$ so consider $\pi '=(\pi _1-1,\cdots ,\pi _j-1)$ this is a $j-$tuple which adds up to $$\sum _{r = 1}^j\pi_r-1=k-j$$ if the original $\pi$ used to add up to $k\leq n$ hence your $\pi '$ should add up to a number less or equal to $n-j$ but there are $\binom{n-j}{j}$ such $\pi '$ partitions(we did that previously but now with $n-j$ instead of just $n$). Can you conclude? Edited Ok, so in the comments you got the expression $$\sum _{k=j}^n\binom{k-j-1}{j-1},$$ the deal is that $k=j$ is impossible because the $\pi _i>1$ hence the sum is greater than $j$ so you start with $k=j+1$ and so the sum gives $$\binom{n-j}{j}$$ and hence the probability is $$1-\frac{\binom{n-j}{j}}{\binom{n}{j}}.$$ You are right, if $n<2j$ this is $1$ all partitions should have at least one 1.