Mixing
Partition of n into k distinct partitions modulo $p$
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
Given $N$ and $K$ we have to find the number of partitions of $N$ into at most $K$ parts modulo $p$.
I was wondering if there was any formula to calculate this type of query.
I know about the recurrence formula $p_k(n)=p_k(n−k)+p_k−1(n)$ also about the ferrers diagram
But this can be used when $N$ and $K$ are small
I need to find for $1leq
N,K leq2*10^5$
combinatorics number-theory integer-partitions
edited Jul 25 at 12:21
Kenta S
1,1371418
asked Jul 25 at 11:28
dank uploader
13
add a comment |Â
up vote
0
down vote
favorite
Given $N$ and $K$ we have to find the number of partitions of $N$ into at most $K$ parts modulo $p$.
I was wondering if there was any formula to calculate this type of query.
I know about the recurrence formula $p_k(n)=p_k(n−k)+p_k−1(n)$ also about the ferrers diagram
But this can be used when $N$ and $K$ are small
I need to find for $1leq
N,K leq2*10^5$
combinatorics number-theory integer-partitions
edited Jul 25 at 12:21
Kenta S
1,1371418
asked Jul 25 at 11:28
dank uploader
13
Is it the parts that are being taken modulo $p$, or is it the number of partitions that's being taken modulo $p$?
– Gerry Myerson
Jul 25 at 13:05
Number of parts modulo p like $p_3(5)$ = 5,14,23,113,122 so count is 5 as there are 5 ways to represent it and this modulo 11 is 5 and this modulo 3 is 2
– dank uploader
Jul 25 at 17:54
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Given $N$ and $K$ we have to find the number of partitions of $N$ into at most $K$ parts modulo $p$.
I was wondering if there was any formula to calculate this type of query.
I know about the recurrence formula $p_k(n)=p_k(n−k)+p_k−1(n)$ also about the ferrers diagram
But this can be used when $N$ and $K$ are small
I need to find for $1leq
N,K leq2*10^5$
combinatorics number-theory integer-partitions
edited Jul 25 at 12:21
Kenta S
1,1371418
asked Jul 25 at 11:28
dank uploader
13
Given $N$ and $K$ we have to find the number of partitions of $N$ into at most $K$ parts modulo $p$.
I was wondering if there was any formula to calculate this type of query.
I know about the recurrence formula $p_k(n)=p_k(n−k)+p_k−1(n)$ also about the ferrers diagram
But this can be used when $N$ and $K$ are small
I need to find for $1leq
N,K leq2*10^5$
combinatorics number-theory integer-partitions
edited Jul 25 at 12:21
Kenta S
1,1371418
asked Jul 25 at 11:28
dank uploader
13
edited Jul 25 at 12:21
Kenta S
1,1371418
edited Jul 25 at 12:21
Kenta S
1,1371418
edited Jul 25 at 12:21
Kenta S
1,1371418
1,1371418
asked Jul 25 at 11:28
dank uploader
13
asked Jul 25 at 11:28
dank uploader
13
asked Jul 25 at 11:28
dank uploader
13
13
Is it the parts that are being taken modulo $p$, or is it the number of partitions that's being taken modulo $p$?
– Gerry Myerson
Jul 25 at 13:05
Number of parts modulo p like $p_3(5)$ = 5,14,23,113,122 so count is 5 as there are 5 ways to represent it and this modulo 11 is 5 and this modulo 3 is 2
– dank uploader
Jul 25 at 17:54
add a comment |Â
Is it the parts that are being taken modulo $p$, or is it the number of partitions that's being taken modulo $p$?
– Gerry Myerson
Jul 25 at 13:05
Number of parts modulo p like $p_3(5)$ = 5,14,23,113,122 so count is 5 as there are 5 ways to represent it and this modulo 11 is 5 and this modulo 3 is 2
– dank uploader
Jul 25 at 17:54
Is it the parts that are being taken modulo $p$, or is it the number of partitions that's being taken modulo $p$?
– Gerry Myerson
Jul 25 at 13:05
Is it the parts that are being taken modulo $p$, or is it the number of partitions that's being taken modulo $p$?
– Gerry Myerson
Jul 25 at 13:05
Number of parts modulo p like $p_3(5)$ = 5,14,23,113,122 so count is 5 as there are 5 ways to represent it and this modulo 11 is 5 and this modulo 3 is 2
– dank uploader
Jul 25 at 17:54
Number of parts modulo p like $p_3(5)$ = 5,14,23,113,122 so count is 5 as there are 5 ways to represent it and this modulo 11 is 5 and this modulo 3 is 2
– dank uploader
Jul 25 at 17:54
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
0
down vote
But this can be used when $N$ and $K$ are small
I need to find for $1leq N,K leq2*10^5$
Those are small.
That aside, a little thought experiment. Suppose that a nice formula were known for $p_k(n) bmod m$. There are easy upper bounds on $p_k(n)$: for example, $p_k(n) leq (n-k+1)^k-1$. Substitute for $m$ and our nice formula for $p_k(n) bmod (n-k+1)^k-1$ is just a nice formula for $p_k(n)$. But I don't see a nice formula in OEIS, and this is a well-studied and well-referenced sequence, so it's very unlikely that one is known.
answered Jul 26 at 12:52
Peter Taylor
7,69512239
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
But this can be used when $N$ and $K$ are small
I need to find for $1leq N,K leq2*10^5$
Those are small.
That aside, a little thought experiment. Suppose that a nice formula were known for $p_k(n) bmod m$. There are easy upper bounds on $p_k(n)$: for example, $p_k(n) leq (n-k+1)^k-1$. Substitute for $m$ and our nice formula for $p_k(n) bmod (n-k+1)^k-1$ is just a nice formula for $p_k(n)$. But I don't see a nice formula in OEIS, and this is a well-studied and well-referenced sequence, so it's very unlikely that one is known.
answered Jul 26 at 12:52
Peter Taylor
7,69512239
add a comment |Â
up vote
0
down vote
But this can be used when $N$ and $K$ are small
I need to find for $1leq N,K leq2*10^5$
Those are small.
That aside, a little thought experiment. Suppose that a nice formula were known for $p_k(n) bmod m$. There are easy upper bounds on $p_k(n)$: for example, $p_k(n) leq (n-k+1)^k-1$. Substitute for $m$ and our nice formula for $p_k(n) bmod (n-k+1)^k-1$ is just a nice formula for $p_k(n)$. But I don't see a nice formula in OEIS, and this is a well-studied and well-referenced sequence, so it's very unlikely that one is known.
answered Jul 26 at 12:52
Peter Taylor
7,69512239
add a comment |Â
up vote
0
down vote
up vote
0
down vote
But this can be used when $N$ and $K$ are small
I need to find for $1leq N,K leq2*10^5$
Those are small.
That aside, a little thought experiment. Suppose that a nice formula were known for $p_k(n) bmod m$. There are easy upper bounds on $p_k(n)$: for example, $p_k(n) leq (n-k+1)^k-1$. Substitute for $m$ and our nice formula for $p_k(n) bmod (n-k+1)^k-1$ is just a nice formula for $p_k(n)$. But I don't see a nice formula in OEIS, and this is a well-studied and well-referenced sequence, so it's very unlikely that one is known.
answered Jul 26 at 12:52
Peter Taylor
7,69512239
But this can be used when $N$ and $K$ are small
I need to find for $1leq N,K leq2*10^5$
Those are small.
That aside, a little thought experiment. Suppose that a nice formula were known for $p_k(n) bmod m$. There are easy upper bounds on $p_k(n)$: for example, $p_k(n) leq (n-k+1)^k-1$. Substitute for $m$ and our nice formula for $p_k(n) bmod (n-k+1)^k-1$ is just a nice formula for $p_k(n)$. But I don't see a nice formula in OEIS, and this is a well-studied and well-referenced sequence, so it's very unlikely that one is known.
answered Jul 26 at 12:52
Peter Taylor
7,69512239
answered Jul 26 at 12:52
Peter Taylor
7,69512239
answered Jul 26 at 12:52
Peter Taylor
7,69512239
answered Jul 26 at 12:52
Peter Taylor
7,69512239
7,69512239
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2862334%2fpartition-of-n-into-k-distinct-partitions-modulo-p%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Is it the parts that are being taken modulo $p$, or is it the number of partitions that's being taken modulo $p$?
– Gerry Myerson
Jul 25 at 13:05
Number of parts modulo p like $p_3(5)$ = 5,14,23,113,122 so count is 5 as there are 5 ways to represent it and this modulo 11 is 5 and this modulo 3 is 2
– dank uploader
Jul 25 at 17:54