Mixing
Find the number of ways to choose N non-negative numbers that sum up to $S$ and are in strictly increasing order? [closed]
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
More formally, find the number of ways of dividing a sum $S$ among $N$ numbers — $a_1, a_2, a_3, dots, a_N$,
such that they are in strictly increasing order i.e. — $a_1 < a_2 < a_3 < dots < a_n$,
given that $sum_i=1^Na_i = S$ , $a_i >= 0$
Note that the order of the number is fixed.
Consider an example, $N = 3, S = 6$:
Total ways = 3
0, 1, 5
0, 2, 4
1, 2, 3
when $N = 3, S = 7$:
Total ways = 4
0, 1, 6
0, 2, 5
0, 3, 4
1, 2, 4
Edit:
The question's previous title asked for the probability, but to find probability I think we ultimately need to find such number of ways (I don't know if there is some other way). Feel free to answer in terms of probability or the number of such ways.
probability combinatorics number-theory elementary-number-theory probability-distributions
asked Jul 25 at 14:30
Rahul Goswami
319114
closed as unclear what you're asking by Mostafa Ayaz, saulspatz, Lord Shark the Unknown, amWhy, Parcly Taxel Jul 26 at 1:13
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
 |Â
show 9 more comments
up vote
1
down vote
favorite
More formally, find the number of ways of dividing a sum $S$ among $N$ numbers — $a_1, a_2, a_3, dots, a_N$,
such that they are in strictly increasing order i.e. — $a_1 < a_2 < a_3 < dots < a_n$,
given that $sum_i=1^Na_i = S$ , $a_i >= 0$
Note that the order of the number is fixed.
Consider an example, $N = 3, S = 6$:
Total ways = 3
0, 1, 5
0, 2, 4
1, 2, 3
when $N = 3, S = 7$:
Total ways = 4
0, 1, 6
0, 2, 5
0, 3, 4
1, 2, 4
Edit:
The question's previous title asked for the probability, but to find probability I think we ultimately need to find such number of ways (I don't know if there is some other way). Feel free to answer in terms of probability or the number of such ways.
probability combinatorics number-theory elementary-number-theory probability-distributions
asked Jul 25 at 14:30
Rahul Goswami
319114
closed as unclear what you're asking by Mostafa Ayaz, saulspatz, Lord Shark the Unknown, amWhy, Parcly Taxel Jul 26 at 1:13
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
What does this have to do with probability?
– saulspatz
Jul 25 at 14:38
2
If you are given $N$ distinct numbers the chance that they are in increasing order is $1/N!$. The fact that they sum to $S$ doesn't matter at all.
– Ross Millikan
Jul 25 at 14:41
1
If the numbers can be equal, how can they be strictly increasing as in $a_1 < a_2 < a_3 < dots < a_N$.
– Daniel Buck
Jul 25 at 14:52
1
I still don't understand what you are looking for. The numbers must be distinct if they can be strictly increasing. Are you looking for the number of compositions of $S$ into $N$ parts? The chance that among those compositions you have selected one in increasing order? Or what?
– Ross Millikan
Jul 25 at 14:57
1
Good edit. Note that the number of ways to write $S$ as sum of $N$ non-negative integers is $S+N-1choose N-1$. In my example that's $4+2-1choose2-1=5choose1=5$. So the denominator for the probability you're asking for has a nice, simple expressions. It's the numerator that you're really asking about.
– Barry Cipra
Jul 25 at 15:37
 |Â
show 9 more comments
up vote
1
down vote
favorite
up vote
1
down vote
favorite
More formally, find the number of ways of dividing a sum $S$ among $N$ numbers — $a_1, a_2, a_3, dots, a_N$,
such that they are in strictly increasing order i.e. — $a_1 < a_2 < a_3 < dots < a_n$,
given that $sum_i=1^Na_i = S$ , $a_i >= 0$
Note that the order of the number is fixed.
Consider an example, $N = 3, S = 6$:
Total ways = 3
0, 1, 5
0, 2, 4
1, 2, 3
when $N = 3, S = 7$:
Total ways = 4
0, 1, 6
0, 2, 5
0, 3, 4
1, 2, 4
Edit:
The question's previous title asked for the probability, but to find probability I think we ultimately need to find such number of ways (I don't know if there is some other way). Feel free to answer in terms of probability or the number of such ways.
probability combinatorics number-theory elementary-number-theory probability-distributions
asked Jul 25 at 14:30
Rahul Goswami
319114
More formally, find the number of ways of dividing a sum $S$ among $N$ numbers — $a_1, a_2, a_3, dots, a_N$,
such that they are in strictly increasing order i.e. — $a_1 < a_2 < a_3 < dots < a_n$,
given that $sum_i=1^Na_i = S$ , $a_i >= 0$
Note that the order of the number is fixed.
Consider an example, $N = 3, S = 6$:
Total ways = 3
0, 1, 5
0, 2, 4
1, 2, 3
when $N = 3, S = 7$:
Total ways = 4
0, 1, 6
0, 2, 5
0, 3, 4
1, 2, 4
Edit:
The question's previous title asked for the probability, but to find probability I think we ultimately need to find such number of ways (I don't know if there is some other way). Feel free to answer in terms of probability or the number of such ways.
probability combinatorics number-theory elementary-number-theory probability-distributions
asked Jul 25 at 14:30
Rahul Goswami
319114
edited Jul 25 at 15:31
asked Jul 25 at 14:30
Rahul Goswami
319114
asked Jul 25 at 14:30
Rahul Goswami
319114
asked Jul 25 at 14:30
Rahul Goswami
319114
319114
closed as unclear what you're asking by Mostafa Ayaz, saulspatz, Lord Shark the Unknown, amWhy, Parcly Taxel Jul 26 at 1:13
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
closed as unclear what you're asking by Mostafa Ayaz, saulspatz, Lord Shark the Unknown, amWhy, Parcly Taxel Jul 26 at 1:13
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
What does this have to do with probability?
– saulspatz
Jul 25 at 14:38
2
If you are given $N$ distinct numbers the chance that they are in increasing order is $1/N!$. The fact that they sum to $S$ doesn't matter at all.
– Ross Millikan
Jul 25 at 14:41
1
If the numbers can be equal, how can they be strictly increasing as in $a_1 < a_2 < a_3 < dots < a_N$.
– Daniel Buck
Jul 25 at 14:52
1
I still don't understand what you are looking for. The numbers must be distinct if they can be strictly increasing. Are you looking for the number of compositions of $S$ into $N$ parts? The chance that among those compositions you have selected one in increasing order? Or what?
– Ross Millikan
Jul 25 at 14:57
1
Good edit. Note that the number of ways to write $S$ as sum of $N$ non-negative integers is $S+N-1choose N-1$. In my example that's $4+2-1choose2-1=5choose1=5$. So the denominator for the probability you're asking for has a nice, simple expressions. It's the numerator that you're really asking about.
– Barry Cipra
Jul 25 at 15:37
 |Â
show 9 more comments
What does this have to do with probability?
– saulspatz
Jul 25 at 14:38
2
If you are given $N$ distinct numbers the chance that they are in increasing order is $1/N!$. The fact that they sum to $S$ doesn't matter at all.
– Ross Millikan
Jul 25 at 14:41
1
If the numbers can be equal, how can they be strictly increasing as in $a_1 < a_2 < a_3 < dots < a_N$.
– Daniel Buck
Jul 25 at 14:52
1
I still don't understand what you are looking for. The numbers must be distinct if they can be strictly increasing. Are you looking for the number of compositions of $S$ into $N$ parts? The chance that among those compositions you have selected one in increasing order? Or what?
– Ross Millikan
Jul 25 at 14:57
1
Good edit. Note that the number of ways to write $S$ as sum of $N$ non-negative integers is $S+N-1choose N-1$. In my example that's $4+2-1choose2-1=5choose1=5$. So the denominator for the probability you're asking for has a nice, simple expressions. It's the numerator that you're really asking about.
– Barry Cipra
Jul 25 at 15:37
What does this have to do with probability?
– saulspatz
Jul 25 at 14:38
What does this have to do with probability?
– saulspatz
Jul 25 at 14:38
2
2
If you are given $N$ distinct numbers the chance that they are in increasing order is $1/N!$. The fact that they sum to $S$ doesn't matter at all.
– Ross Millikan
Jul 25 at 14:41
If you are given $N$ distinct numbers the chance that they are in increasing order is $1/N!$. The fact that they sum to $S$ doesn't matter at all.
– Ross Millikan
Jul 25 at 14:41
1
1
If the numbers can be equal, how can they be strictly increasing as in $a_1 < a_2 < a_3 < dots < a_N$.
– Daniel Buck
Jul 25 at 14:52
If the numbers can be equal, how can they be strictly increasing as in $a_1 < a_2 < a_3 < dots < a_N$.
– Daniel Buck
Jul 25 at 14:52
1
1
I still don't understand what you are looking for. The numbers must be distinct if they can be strictly increasing. Are you looking for the number of compositions of $S$ into $N$ parts? The chance that among those compositions you have selected one in increasing order? Or what?
– Ross Millikan
Jul 25 at 14:57
I still don't understand what you are looking for. The numbers must be distinct if they can be strictly increasing. Are you looking for the number of compositions of $S$ into $N$ parts? The chance that among those compositions you have selected one in increasing order? Or what?
– Ross Millikan
Jul 25 at 14:57
1
1
Good edit. Note that the number of ways to write $S$ as sum of $N$ non-negative integers is $S+N-1choose N-1$. In my example that's $4+2-1choose2-1=5choose1=5$. So the denominator for the probability you're asking for has a nice, simple expressions. It's the numerator that you're really asking about.
– Barry Cipra
Jul 25 at 15:37
Good edit. Note that the number of ways to write $S$ as sum of $N$ non-negative integers is $S+N-1choose N-1$. In my example that's $4+2-1choose2-1=5choose1=5$. So the denominator for the probability you're asking for has a nice, simple expressions. It's the numerator that you're really asking about.
– Barry Cipra
Jul 25 at 15:37
 |Â
show 9 more comments
2 Answers
2
active
oldest
votes
up vote
1
down vote
accepted
We will first assume $0$ is not allowed as one of the numbers. We will cover $0$ at the end.
You can write a recurrence. If $A(S,N)$ is the number of ways of writing $S$ as a strictly increasing sum of $N$ numbers greater than $0$, we can look at whether $1$ is one of the numbers. If it is, we need to express $S-1$ as a strictly increasing sum of $N-1$ numbers greater than $1$. Subtract $1$ from them all and $N$ from $S$ and we see there are $A(S-N,N-1)$ ways to write $S$ in a way including $1$.
If $1$ is not included, we need to write $S$ as a sum of $N$ numbers greater than $1$. Again we can subtract $1$ from all the numbers and find there are $A(S-N,N)$ ways to write $S$ as a sum of $N$ numbers not including $1$, so
$$A(S,N)=A(S-N,N-1)+A(S-N,N)$$
Given the observation that $A(S,N)=0$ when $S lt frac 12N(N+1)$ and $A(S,1)=1$ this will bottom out quickly for reasonable values of $S,N$
Let $B(S,N)$ be the number of ways of expressing $S$ as the increasing sum of $N$ numbers where $0$ is permitted. If $0$ is included there are $A(S,N-1)$ ways. If $0$ is not included, there are $A(S,N)$ ways, so
$$B(S,N)=A(S,N-1)+A(S,N)$$
is the final count.
Taking the example of $S=7,N=3$ we have
$$B(7,3)=A(7,3)+A(7,2)\A(7,3)=A(4,2)+A(4,3)=1+0=1\
A(7,2)=A(5,1)+A(5,2)=1+A(3,1)+A(3,2)=3\B(7,3)=4$$
answered Jul 25 at 16:02
Ross Millikan
275k21186351
Great answer and approach! I don't think this recursive equation is solvable (in terms of a single formula), or is it?
– Rahul Goswami
Jul 25 at 16:40
1
I don't see an obvious one. Partition problems are often hard to express compactly. I would start by generating a big table of the $B$s. Mathematica, which I don't have, would make that easy. It would work in a spreadsheet using the LOOKUP function
– Ross Millikan
Jul 25 at 16:45
1
See this link: oeis.org/A008289 .
– Steve Kass
Jul 25 at 16:49
1
He is following the same logic as I am. His recurrence should be $p(k,n)=p(k-1,n-1)+p(k,n-k)$ as Wikipedia says. The first is partitions including at least one $1$, so you remove it and partition $n-1$ into $k-1$ parts. The second is partitions with no $1$, so subtract $1$ from each partition and partition $n-k$ into $k$ parts.
– Ross Millikan
Jul 25 at 18:05
1
He allows multiple zeros, unlike you. His solution is to add $1$ to each part and prohibit zeros. That is why $n$ goes to $n+k$. He does that first, so they are taken care of and if there is no $1$ we can subtract $1$ from every partition.
– Ross Millikan
Jul 25 at 20:44
 |Â
show 4 more comments
up vote
1
down vote
You can solve this with a generating function. Let $$P = prod_i=0^S (1+x^iy)$$
The variable $y$ tracks the number of summands, and $x$ tracks the amount contributed to the sum. Then the number of sequences of $N$ strictly increasing summands adding up to $S$ is the coefficient of $x^Sy^N$ in $P$, since any set of $N$ distinct numbers adding up to $S$ creates a single such sequence due to the dual requirements for the summands being distinct and strictly increasing.
So for example with $N=3$, $S=6$ as above, we get the solution $0,1,5$ from $$(x^0y)(x^1y)(1)(1)(1)(x^5y)$$
You can calculate this for specific values using the MAGMA Online Calculator with the code:
Z<x,y>:=PolynomialRing(Integers(),2);
N:=3;
S:=30;
prod:=&*[1+x^i*y:i in 0..S];
Coefficient(Coefficient(prod,y,N),x,S);
answered Jul 25 at 15:47
Jeremy Dover
885410
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
We will first assume $0$ is not allowed as one of the numbers. We will cover $0$ at the end.
You can write a recurrence. If $A(S,N)$ is the number of ways of writing $S$ as a strictly increasing sum of $N$ numbers greater than $0$, we can look at whether $1$ is one of the numbers. If it is, we need to express $S-1$ as a strictly increasing sum of $N-1$ numbers greater than $1$. Subtract $1$ from them all and $N$ from $S$ and we see there are $A(S-N,N-1)$ ways to write $S$ in a way including $1$.
If $1$ is not included, we need to write $S$ as a sum of $N$ numbers greater than $1$. Again we can subtract $1$ from all the numbers and find there are $A(S-N,N)$ ways to write $S$ as a sum of $N$ numbers not including $1$, so
$$A(S,N)=A(S-N,N-1)+A(S-N,N)$$
Given the observation that $A(S,N)=0$ when $S lt frac 12N(N+1)$ and $A(S,1)=1$ this will bottom out quickly for reasonable values of $S,N$
Let $B(S,N)$ be the number of ways of expressing $S$ as the increasing sum of $N$ numbers where $0$ is permitted. If $0$ is included there are $A(S,N-1)$ ways. If $0$ is not included, there are $A(S,N)$ ways, so
$$B(S,N)=A(S,N-1)+A(S,N)$$
is the final count.
Taking the example of $S=7,N=3$ we have
$$B(7,3)=A(7,3)+A(7,2)\A(7,3)=A(4,2)+A(4,3)=1+0=1\
A(7,2)=A(5,1)+A(5,2)=1+A(3,1)+A(3,2)=3\B(7,3)=4$$
answered Jul 25 at 16:02
Ross Millikan
275k21186351
Great answer and approach! I don't think this recursive equation is solvable (in terms of a single formula), or is it?
– Rahul Goswami
Jul 25 at 16:40
1
I don't see an obvious one. Partition problems are often hard to express compactly. I would start by generating a big table of the $B$s. Mathematica, which I don't have, would make that easy. It would work in a spreadsheet using the LOOKUP function
– Ross Millikan
Jul 25 at 16:45
1
See this link: oeis.org/A008289 .
– Steve Kass
Jul 25 at 16:49
1
He is following the same logic as I am. His recurrence should be $p(k,n)=p(k-1,n-1)+p(k,n-k)$ as Wikipedia says. The first is partitions including at least one $1$, so you remove it and partition $n-1$ into $k-1$ parts. The second is partitions with no $1$, so subtract $1$ from each partition and partition $n-k$ into $k$ parts.
– Ross Millikan
Jul 25 at 18:05
1
He allows multiple zeros, unlike you. His solution is to add $1$ to each part and prohibit zeros. That is why $n$ goes to $n+k$. He does that first, so they are taken care of and if there is no $1$ we can subtract $1$ from every partition.
– Ross Millikan
Jul 25 at 20:44
 |Â
show 4 more comments
up vote
1
down vote
accepted
We will first assume $0$ is not allowed as one of the numbers. We will cover $0$ at the end.
You can write a recurrence. If $A(S,N)$ is the number of ways of writing $S$ as a strictly increasing sum of $N$ numbers greater than $0$, we can look at whether $1$ is one of the numbers. If it is, we need to express $S-1$ as a strictly increasing sum of $N-1$ numbers greater than $1$. Subtract $1$ from them all and $N$ from $S$ and we see there are $A(S-N,N-1)$ ways to write $S$ in a way including $1$.
If $1$ is not included, we need to write $S$ as a sum of $N$ numbers greater than $1$. Again we can subtract $1$ from all the numbers and find there are $A(S-N,N)$ ways to write $S$ as a sum of $N$ numbers not including $1$, so
$$A(S,N)=A(S-N,N-1)+A(S-N,N)$$
Given the observation that $A(S,N)=0$ when $S lt frac 12N(N+1)$ and $A(S,1)=1$ this will bottom out quickly for reasonable values of $S,N$
Let $B(S,N)$ be the number of ways of expressing $S$ as the increasing sum of $N$ numbers where $0$ is permitted. If $0$ is included there are $A(S,N-1)$ ways. If $0$ is not included, there are $A(S,N)$ ways, so
$$B(S,N)=A(S,N-1)+A(S,N)$$
is the final count.
Taking the example of $S=7,N=3$ we have
$$B(7,3)=A(7,3)+A(7,2)\A(7,3)=A(4,2)+A(4,3)=1+0=1\
A(7,2)=A(5,1)+A(5,2)=1+A(3,1)+A(3,2)=3\B(7,3)=4$$
answered Jul 25 at 16:02
Ross Millikan
275k21186351
Great answer and approach! I don't think this recursive equation is solvable (in terms of a single formula), or is it?
– Rahul Goswami
Jul 25 at 16:40
1
I don't see an obvious one. Partition problems are often hard to express compactly. I would start by generating a big table of the $B$s. Mathematica, which I don't have, would make that easy. It would work in a spreadsheet using the LOOKUP function
– Ross Millikan
Jul 25 at 16:45
1
See this link: oeis.org/A008289 .
– Steve Kass
Jul 25 at 16:49
1
He is following the same logic as I am. His recurrence should be $p(k,n)=p(k-1,n-1)+p(k,n-k)$ as Wikipedia says. The first is partitions including at least one $1$, so you remove it and partition $n-1$ into $k-1$ parts. The second is partitions with no $1$, so subtract $1$ from each partition and partition $n-k$ into $k$ parts.
– Ross Millikan
Jul 25 at 18:05
1
He allows multiple zeros, unlike you. His solution is to add $1$ to each part and prohibit zeros. That is why $n$ goes to $n+k$. He does that first, so they are taken care of and if there is no $1$ we can subtract $1$ from every partition.
– Ross Millikan
Jul 25 at 20:44
 |Â
show 4 more comments
up vote
1
down vote
accepted
up vote
1
down vote
accepted
We will first assume $0$ is not allowed as one of the numbers. We will cover $0$ at the end.
You can write a recurrence. If $A(S,N)$ is the number of ways of writing $S$ as a strictly increasing sum of $N$ numbers greater than $0$, we can look at whether $1$ is one of the numbers. If it is, we need to express $S-1$ as a strictly increasing sum of $N-1$ numbers greater than $1$. Subtract $1$ from them all and $N$ from $S$ and we see there are $A(S-N,N-1)$ ways to write $S$ in a way including $1$.
If $1$ is not included, we need to write $S$ as a sum of $N$ numbers greater than $1$. Again we can subtract $1$ from all the numbers and find there are $A(S-N,N)$ ways to write $S$ as a sum of $N$ numbers not including $1$, so
$$A(S,N)=A(S-N,N-1)+A(S-N,N)$$
Given the observation that $A(S,N)=0$ when $S lt frac 12N(N+1)$ and $A(S,1)=1$ this will bottom out quickly for reasonable values of $S,N$
Let $B(S,N)$ be the number of ways of expressing $S$ as the increasing sum of $N$ numbers where $0$ is permitted. If $0$ is included there are $A(S,N-1)$ ways. If $0$ is not included, there are $A(S,N)$ ways, so
$$B(S,N)=A(S,N-1)+A(S,N)$$
is the final count.
Taking the example of $S=7,N=3$ we have
$$B(7,3)=A(7,3)+A(7,2)\A(7,3)=A(4,2)+A(4,3)=1+0=1\
A(7,2)=A(5,1)+A(5,2)=1+A(3,1)+A(3,2)=3\B(7,3)=4$$
answered Jul 25 at 16:02
Ross Millikan
275k21186351
We will first assume $0$ is not allowed as one of the numbers. We will cover $0$ at the end.
You can write a recurrence. If $A(S,N)$ is the number of ways of writing $S$ as a strictly increasing sum of $N$ numbers greater than $0$, we can look at whether $1$ is one of the numbers. If it is, we need to express $S-1$ as a strictly increasing sum of $N-1$ numbers greater than $1$. Subtract $1$ from them all and $N$ from $S$ and we see there are $A(S-N,N-1)$ ways to write $S$ in a way including $1$.
If $1$ is not included, we need to write $S$ as a sum of $N$ numbers greater than $1$. Again we can subtract $1$ from all the numbers and find there are $A(S-N,N)$ ways to write $S$ as a sum of $N$ numbers not including $1$, so
$$A(S,N)=A(S-N,N-1)+A(S-N,N)$$
Given the observation that $A(S,N)=0$ when $S lt frac 12N(N+1)$ and $A(S,1)=1$ this will bottom out quickly for reasonable values of $S,N$
Let $B(S,N)$ be the number of ways of expressing $S$ as the increasing sum of $N$ numbers where $0$ is permitted. If $0$ is included there are $A(S,N-1)$ ways. If $0$ is not included, there are $A(S,N)$ ways, so
$$B(S,N)=A(S,N-1)+A(S,N)$$
is the final count.
Taking the example of $S=7,N=3$ we have
$$B(7,3)=A(7,3)+A(7,2)\A(7,3)=A(4,2)+A(4,3)=1+0=1\
A(7,2)=A(5,1)+A(5,2)=1+A(3,1)+A(3,2)=3\B(7,3)=4$$
answered Jul 25 at 16:02
Ross Millikan
275k21186351
edited Jul 25 at 16:40
answered Jul 25 at 16:02
Ross Millikan
275k21186351
answered Jul 25 at 16:02
Ross Millikan
275k21186351
answered Jul 25 at 16:02
Ross Millikan
275k21186351
275k21186351
Great answer and approach! I don't think this recursive equation is solvable (in terms of a single formula), or is it?
– Rahul Goswami
Jul 25 at 16:40
1
I don't see an obvious one. Partition problems are often hard to express compactly. I would start by generating a big table of the $B$s. Mathematica, which I don't have, would make that easy. It would work in a spreadsheet using the LOOKUP function
– Ross Millikan
Jul 25 at 16:45
1
See this link: oeis.org/A008289 .
– Steve Kass
Jul 25 at 16:49
1
He is following the same logic as I am. His recurrence should be $p(k,n)=p(k-1,n-1)+p(k,n-k)$ as Wikipedia says. The first is partitions including at least one $1$, so you remove it and partition $n-1$ into $k-1$ parts. The second is partitions with no $1$, so subtract $1$ from each partition and partition $n-k$ into $k$ parts.
– Ross Millikan
Jul 25 at 18:05
1
He allows multiple zeros, unlike you. His solution is to add $1$ to each part and prohibit zeros. That is why $n$ goes to $n+k$. He does that first, so they are taken care of and if there is no $1$ we can subtract $1$ from every partition.
– Ross Millikan
Jul 25 at 20:44
 |Â
show 4 more comments
Great answer and approach! I don't think this recursive equation is solvable (in terms of a single formula), or is it?
– Rahul Goswami
Jul 25 at 16:40
1
I don't see an obvious one. Partition problems are often hard to express compactly. I would start by generating a big table of the $B$s. Mathematica, which I don't have, would make that easy. It would work in a spreadsheet using the LOOKUP function
– Ross Millikan
Jul 25 at 16:45
1
See this link: oeis.org/A008289 .
– Steve Kass
Jul 25 at 16:49
1
He is following the same logic as I am. His recurrence should be $p(k,n)=p(k-1,n-1)+p(k,n-k)$ as Wikipedia says. The first is partitions including at least one $1$, so you remove it and partition $n-1$ into $k-1$ parts. The second is partitions with no $1$, so subtract $1$ from each partition and partition $n-k$ into $k$ parts.
– Ross Millikan
Jul 25 at 18:05
1
He allows multiple zeros, unlike you. His solution is to add $1$ to each part and prohibit zeros. That is why $n$ goes to $n+k$. He does that first, so they are taken care of and if there is no $1$ we can subtract $1$ from every partition.
– Ross Millikan
Jul 25 at 20:44
Great answer and approach! I don't think this recursive equation is solvable (in terms of a single formula), or is it?
– Rahul Goswami
Jul 25 at 16:40
Great answer and approach! I don't think this recursive equation is solvable (in terms of a single formula), or is it?
– Rahul Goswami
Jul 25 at 16:40
1
1
I don't see an obvious one. Partition problems are often hard to express compactly. I would start by generating a big table of the $B$s. Mathematica, which I don't have, would make that easy. It would work in a spreadsheet using the LOOKUP function
– Ross Millikan
Jul 25 at 16:45
I don't see an obvious one. Partition problems are often hard to express compactly. I would start by generating a big table of the $B$s. Mathematica, which I don't have, would make that easy. It would work in a spreadsheet using the LOOKUP function
– Ross Millikan
Jul 25 at 16:45
1
1
See this link: oeis.org/A008289 .
– Steve Kass
Jul 25 at 16:49
See this link: oeis.org/A008289 .
– Steve Kass
Jul 25 at 16:49
1
1
He is following the same logic as I am. His recurrence should be $p(k,n)=p(k-1,n-1)+p(k,n-k)$ as Wikipedia says. The first is partitions including at least one $1$, so you remove it and partition $n-1$ into $k-1$ parts. The second is partitions with no $1$, so subtract $1$ from each partition and partition $n-k$ into $k$ parts.
– Ross Millikan
Jul 25 at 18:05
He is following the same logic as I am. His recurrence should be $p(k,n)=p(k-1,n-1)+p(k,n-k)$ as Wikipedia says. The first is partitions including at least one $1$, so you remove it and partition $n-1$ into $k-1$ parts. The second is partitions with no $1$, so subtract $1$ from each partition and partition $n-k$ into $k$ parts.
– Ross Millikan
Jul 25 at 18:05
1
1
He allows multiple zeros, unlike you. His solution is to add $1$ to each part and prohibit zeros. That is why $n$ goes to $n+k$. He does that first, so they are taken care of and if there is no $1$ we can subtract $1$ from every partition.
– Ross Millikan
Jul 25 at 20:44
He allows multiple zeros, unlike you. His solution is to add $1$ to each part and prohibit zeros. That is why $n$ goes to $n+k$. He does that first, so they are taken care of and if there is no $1$ we can subtract $1$ from every partition.
– Ross Millikan
Jul 25 at 20:44
 |Â
show 4 more comments
up vote
1
down vote
You can solve this with a generating function. Let $$P = prod_i=0^S (1+x^iy)$$
The variable $y$ tracks the number of summands, and $x$ tracks the amount contributed to the sum. Then the number of sequences of $N$ strictly increasing summands adding up to $S$ is the coefficient of $x^Sy^N$ in $P$, since any set of $N$ distinct numbers adding up to $S$ creates a single such sequence due to the dual requirements for the summands being distinct and strictly increasing.
So for example with $N=3$, $S=6$ as above, we get the solution $0,1,5$ from $$(x^0y)(x^1y)(1)(1)(1)(x^5y)$$
You can calculate this for specific values using the MAGMA Online Calculator with the code:
Z<x,y>:=PolynomialRing(Integers(),2);
N:=3;
S:=30;
prod:=&*[1+x^i*y:i in 0..S];
Coefficient(Coefficient(prod,y,N),x,S);
answered Jul 25 at 15:47
Jeremy Dover
885410
add a comment |Â
up vote
1
down vote
You can solve this with a generating function. Let $$P = prod_i=0^S (1+x^iy)$$
The variable $y$ tracks the number of summands, and $x$ tracks the amount contributed to the sum. Then the number of sequences of $N$ strictly increasing summands adding up to $S$ is the coefficient of $x^Sy^N$ in $P$, since any set of $N$ distinct numbers adding up to $S$ creates a single such sequence due to the dual requirements for the summands being distinct and strictly increasing.
So for example with $N=3$, $S=6$ as above, we get the solution $0,1,5$ from $$(x^0y)(x^1y)(1)(1)(1)(x^5y)$$
You can calculate this for specific values using the MAGMA Online Calculator with the code:
Z<x,y>:=PolynomialRing(Integers(),2);
N:=3;
S:=30;
prod:=&*[1+x^i*y:i in 0..S];
Coefficient(Coefficient(prod,y,N),x,S);
answered Jul 25 at 15:47
Jeremy Dover
885410
add a comment |Â
up vote
1
down vote
up vote
1
down vote
You can solve this with a generating function. Let $$P = prod_i=0^S (1+x^iy)$$
The variable $y$ tracks the number of summands, and $x$ tracks the amount contributed to the sum. Then the number of sequences of $N$ strictly increasing summands adding up to $S$ is the coefficient of $x^Sy^N$ in $P$, since any set of $N$ distinct numbers adding up to $S$ creates a single such sequence due to the dual requirements for the summands being distinct and strictly increasing.
So for example with $N=3$, $S=6$ as above, we get the solution $0,1,5$ from $$(x^0y)(x^1y)(1)(1)(1)(x^5y)$$
You can calculate this for specific values using the MAGMA Online Calculator with the code:
Z<x,y>:=PolynomialRing(Integers(),2);
N:=3;
S:=30;
prod:=&*[1+x^i*y:i in 0..S];
Coefficient(Coefficient(prod,y,N),x,S);
answered Jul 25 at 15:47
Jeremy Dover
885410
You can solve this with a generating function. Let $$P = prod_i=0^S (1+x^iy)$$
The variable $y$ tracks the number of summands, and $x$ tracks the amount contributed to the sum. Then the number of sequences of $N$ strictly increasing summands adding up to $S$ is the coefficient of $x^Sy^N$ in $P$, since any set of $N$ distinct numbers adding up to $S$ creates a single such sequence due to the dual requirements for the summands being distinct and strictly increasing.
So for example with $N=3$, $S=6$ as above, we get the solution $0,1,5$ from $$(x^0y)(x^1y)(1)(1)(1)(x^5y)$$
You can calculate this for specific values using the MAGMA Online Calculator with the code:
Z<x,y>:=PolynomialRing(Integers(),2);
N:=3;
S:=30;
prod:=&*[1+x^i*y:i in 0..S];
Coefficient(Coefficient(prod,y,N),x,S);
answered Jul 25 at 15:47
Jeremy Dover
885410
edited Jul 25 at 15:52
answered Jul 25 at 15:47
Jeremy Dover
885410
answered Jul 25 at 15:47
Jeremy Dover
885410
answered Jul 25 at 15:47
Jeremy Dover
885410
885410
add a comment |Â
add a comment |Â
What does this have to do with probability?
– saulspatz
Jul 25 at 14:38
2
If you are given $N$ distinct numbers the chance that they are in increasing order is $1/N!$. The fact that they sum to $S$ doesn't matter at all.
– Ross Millikan
Jul 25 at 14:41
1
If the numbers can be equal, how can they be strictly increasing as in $a_1 < a_2 < a_3 < dots < a_N$.
– Daniel Buck
Jul 25 at 14:52
1
I still don't understand what you are looking for. The numbers must be distinct if they can be strictly increasing. Are you looking for the number of compositions of $S$ into $N$ parts? The chance that among those compositions you have selected one in increasing order? Or what?
– Ross Millikan
Jul 25 at 14:57
1
Good edit. Note that the number of ways to write $S$ as sum of $N$ non-negative integers is $S+N-1choose N-1$. In my example that's $4+2-1choose2-1=5choose1=5$. So the denominator for the probability you're asking for has a nice, simple expressions. It's the numerator that you're really asking about.
– Barry Cipra
Jul 25 at 15:37