3
$\begingroup$

Definition

Let's denote $P(n,k)$ represents the set of ordered partitions of integer $n$ into $k$ parts. For example, $P(5,3)=\{(1,1,3),(1,2,2),(1,3,1),(2,1,2),(2,2,1),(3,1,1)\}$

(there is another orderless definition where $P(5,3)=\{(1,1,3),(1,2,2)\}$)

My goal is to calculate the probability of the probability of the last digit in $P(n,k)$, for example, in the ordered example, there are $1\to9,2\to6,3\to3$, so the probability is $\frac{1}{2}, \frac{1}{3},\frac{1}{6}$respectively.

My Attempts

To calculate the result for large $n,k$, my current attempt is to use a recursive formula and implemented as dynamic programming.Let $dp(n,k)$be a list of numbers corresponding to occurrence of $0$ to $9$. $$dp(n,k)=union(\sum_{i=k-1}^{n-1}dp(i,k-1),\sum_{i=1}^{n-k-1}(i\%10)\to dpn(i))$$ $$dpn(n,k)=\sum_{i=k-1}^{n-1}dpn(i,k-1)$$ with the initial condition: $$dpn(n,1)=1$$ $$dp(n,1)=\{n\%10 \to1\}$$ (sum, union of lists produces a list of the sum of corresponding elements)

Question

However, this method is just slightly better than a brute force approach. I am wondering if there is any existing theory taking about this problem, either definition is OK.

$\endgroup$
6
  • $\begingroup$ Related: Stars and bars $\endgroup$
    – user304329
    Commented Mar 12, 2017 at 9:58
  • $\begingroup$ Note that your two definitions are not equivalent; for example $P(6,3)$ produces the probabilities $\tfrac25,\tfrac3{10},\tfrac15,\tfrac1{10}$ for the first definition but $\tfrac13,\tfrac49,\tfrac19,\tfrac19$ for the other $\endgroup$
    – user304329
    Commented Mar 12, 2017 at 10:05
  • $\begingroup$ @vrugtehagel I know that $\endgroup$
    – vapor
    Commented Mar 12, 2017 at 10:19
  • $\begingroup$ @vrugtehagel Is this question simple as star and bars? If yes then this question would be some simple mistake. Can you give some more hints? $\endgroup$
    – vapor
    Commented Mar 12, 2017 at 10:41
  • $\begingroup$ No, I don't think the question is that easy. I was just saying it's related; might help you or someone else out. I'm still thinking about it, in the process of writing an answer if it works out. $\endgroup$
    – user304329
    Commented Mar 12, 2017 at 10:53

1 Answer 1

2
$\begingroup$

We'll go with your first definition. Note that your two definitions are not equivalent; for example $P(6,3)$ produces the probabilities $\tfrac25,\tfrac3{10},\tfrac15,\tfrac1{10}$ for the first definition but $\tfrac13,\tfrac49,\tfrac19,\tfrac19$ for the other.


Let's first find how many $1$'s there are in $P(n,k)$. First note, with stars and bars we can deduce that $$|P(n,k)|={n-1\choose k-1}$$ Now let me introduce you to my notation: I denote $$(i,P(n,k)):=\{(i,j_1,j_2,\cdots,j_k)|(j_1,\cdots,j_k)\in P(n,k)\}$$ So, for example, $P(3,2)=\{(1,2),(2,1)\}$ and thus $(4,P(3,2))=\{(4,1,2),(4,2,1)\}$. Now notice the following:

$$P(n,k)=\bigcup_{i=1}^{n-k+1} (i,P(n-i,k-1))\tag{$*$}$$

To illustrate this fact, take your $P(5,3)$ example and see; \begin{align} P(5,3)=&\{(1,1,3),(1,2,2),(1,3,1)\}\tag{that's $(1,P(4,2))$}\\ &\cup\{(2,1,2),(2,2,1)\}\tag{that's $(2,P(3,2))$}\\ &\cup\{(3,1,1)\}\tag{that's $(3,P(2,2))$} \end{align} Try this yourself on paper and you'll see why expression $(*)$ is trivial. Now let us introduce another notation: let's write $P_a(n,k)$ for the number of $a$'s that occur in $P(n,k)$. So for example, $P_1(5,3)=9$. Now with formula $(*)$, we see (for $k>1$):

\begin{align} P_a(n,k)&=|P(n-a,k-1)|+\sum_{i=1}^{n-k+1}P_a(n-i,k-1)\\ &={n-a-1\choose k-2}+\sum_{i=1}^{n-k+1}P_a(n-i,k-1) \end{align}

This formula is useful, because we can do induction with it to prove possible conjectures we have. For example, calculating some values for $P_1(n,k)$ leads quickly to a pattern;


For all $n,k$ with $n\neq 1$, we have $P_1(n,k)=k\cdot{n-2\choose k-2}$

Proof. First note that this theorem uses the fact that ${a\choose b}=0$ if $b<0$ or $b>a$. We will now use induction to $n$ to prove our statement. First, if $n=2$, then the expression says $P_1(2,k)=k\cdot {0\choose k-2}$. This is easy to confirm numerically: $P(2,1)=\{(2)\}$ which has $P_1(2,1)=1\cdot {0\choose -1}=0$ ones in it; and $P(2,2)=\{(1,1)\}$ has $P_1(2,2)=2\cdot {0\choose 0}=2$ ones in it. All good so far! Now assume the theorem is true for $(1,k),(2,k),\cdots,(n-1,k)$. Then we see, for $k\geq 3$:

\begin{align} P_1(n,k)&={n-2\choose k-2}+\sum_{i=1}^{n-k+1}P_1(n-i,k-1)\\ &={n-2\choose k-2}+\sum_{i=1}^{n-k+1}(k-1){n-i-2\choose k-3}\\ &={n-2\choose k-2}+(k-1)\sum_{i=1}^{n-k+1}{n-i-2\choose k-3}\\ &={n-2\choose k-2}+(k-1)\sum_{i=k-3}^{n-3}{n-(i-k+4)-2\choose k-3}\\ &={n-2\choose k-2}+(k-1)\sum_{i=k-3}^{n-3}{(n-3)-i+(k-3)\choose k-3}\\ &={n-2\choose k-2}+(k-1)\sum_{i=k-3}^{n-3}{i\choose k-3}\\ &={n-2\choose k-2}+(k-1){n-2\choose k-2}\\ &=k\cdot {n-2\choose k-2} \end{align}

Where we've used the Hockey-stick identity in the second-last line. For $k=1$, the expression is obvious; $P_1(n,1)=0$, since $P(n,1)=\{(n)\}$ and $n\neq 1$. Now we have $k=2$ left; but this case is trivial too, since $P(n,2)=\{(1,n-1),(2,n-2),\cdots,(n-2,2),(n-1,1)\}$, so $P_1(n,2)=2$. Thus, by the principle of mathematical induction, we've proved the statement.


With this statement, we already have a major result: the probability of having a $1$ in $P(n,k)$ is $$\frac{k{n-2\choose k-2}}{k{n-1\choose k-1}}=\frac{k-1}{n-1}$$ We divide by $k{n-1\choose k-1}$ because $|P(n,k)|={n-1\choose k-1}$ and each partition contains $k$ numbers.
We can actually do the exact same thing for other numbers.

For all $n,k,a$ with $n>a$, we have $P_a(n,k)=k\cdot{n-a-1\choose k-2}$

First note that $P_a(n,1)=0$ (except when $n=a$, then $P_a(n,1)=1$). This is true because $P(n,1)=\{(n)\}$ (hence the exception). Also, $P_a(n,n-i)=0$ if $i<a-1$, since if we want to partition $n$ in sums of $n-i$ terms, and we want to use one term $a$, then we have to partition $n-a$ in $n-i-1$ terms; this will obviously not work (because $n-a<n-i-1$ so there should be at least one term less than $1$, impossible). Now we can do induction again (a little quicker this time):

\begin{align} P_a(n,k)&={n-a-1\choose k-2}+\sum_{i=1}^{n-k+1}P_a(n-i,k-1)\\ &={n-a-1\choose k-2}+(k-1)\sum_{i=1}^{n-k+1}{n-i-a-1\choose k-3}\\ &={n-a-1\choose k-2}+(k-1)\sum_{i=k-a-2}^{n-a-2}{i\choose k-3}\\ &={n-a-1\choose k-2}+(k-1)\sum_{i=k-3}^{n-a-2}{i\choose k-3}\\ &={n-a-1\choose k-2}+(k-1){n-a-1\choose k-2}\\ &=k{n-a-1\choose k-2} \end{align}

You shouldn't do induction this loosely normally; I do it here to reduce the length of the post. Try to convince yourself of this theorem by doing the proof rigorously.


And so we arrive at our final result:

The probability of having an $a$ in $P(n,k)$ is exactly $$\frac{k{n-a-1\choose k-2}}{k{n-1\choose k-1}}=\frac{{n-a-1\choose k-2}}{{n-1\choose k-1}}$$

We don't simplify this further with factorials, since ${a\choose b}=\frac{a!}{b!(a-b)!}$ is only true for $0\leq b\leq a$.

So in case of $P(5,3)$, we see the chance of having a $3$ is $$\frac{{5-3-1\choose 3-2}}{{5-1\choose 3-1}}=\frac{{1\choose 1}}{{4\choose 2}}=\frac16$$

$\endgroup$
2
  • $\begingroup$ Thank you very much for the hard work! I stopped at the recursive step and turned to a computer, you showed that it can be solved. $\endgroup$
    – vapor
    Commented Mar 12, 2017 at 15:38
  • $\begingroup$ No problem! Happy to help, it was a fun problem :) $\endgroup$
    – user304329
    Commented Mar 12, 2017 at 21:06

You must log in to answer this question.

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