Welcome to our community

Be a part of something great, join today!

Partition question

conscipost

Member
Jan 26, 2012
39
Remember that the number of partitions of n into parts not exceeding m is equal to the number of partitions of n into m or fewer parts? Does anyone know much about the number of partitions of n into m parts not exceeding m?

Thanks!

Edit: Or more generally, the number of partitions of n into j parts not exceeding m?
Thanks again,
 
Last edited:

TheBigBadBen

Active member
May 12, 2013
84
Remember that the number of partitions of n into parts not exceeding m is equal to the number of partitions of n into m or fewer parts? Does anyone know much about the number of partitions of n into m parts not exceeding m?

Thanks!

Edit: Or more generally, the number of partitions of n into j parts not exceeding m?
Thanks again,
All right, so after trying to make sense of your post, I've decided that there are the following distinct questions to be answered here:

1: In how many ways can one partition $n$ objects into groups of less than $m$
2: In how many ways can one partition $n$ objects into $m$ or fewer groups
3: In how many ways can one partition $n$ objects into $j$ parts not exceeding $m$

Please correct me if you meant something else.
 

conscipost

Member
Jan 26, 2012
39
All right, so after trying to make sense of your post, I've decided that there are the following distinct questions to be answered here:

1: In how many ways can one partition $n$ objects into groups of less than $m$
2: In how many ways can one partition $n$ objects into $m$ or fewer groups
3: In how many ways can one partition $n$ objects into $j$ parts not exceeding $m$

Please correct me if you meant something else.
Hey, I'm just talking about integer partitions, but I'm sorry about the lack of clarity. I think it's well known that the number of partitions of an integer n w/ largest part m is equal to the number of partitions of n with m parts a statement equivalent to the first line "Remember".

However, I'm really interested in the question of how many integer partitions of n with j parts have parts not exceeding m.

Does that clarify things a little?
 
Last edited:

TheBigBadBen

Active member
May 12, 2013
84
Hey, I'm just talking about integer partitions, but I'm sorry about the lack of clarity. I think it's well known that the number of partitions of an integer n w/ largest part m is equal to the number of partitions of n with m parts a statement equivalent to the first line "Remember".

However, I'm really interested in the question of how many integer partitions of n with j parts have parts not exceeding m.

Does that clarify things a little?
I realize you mean for $m,n,j$ to be integers. It's still a tough problem.

After looking carefully, the link wasn't as related as I thought, so sorry about that.

Some things I figured out that might help: you can add up the multinomial coefficients
$$
\binom{n}{k_1,k_2,...,k_m}
$$
Over all choices of $k_j$ such that $0≤k_j≤n$, not counting repeating combinations of $k_j$, and $\sum_{j=1}^m k_j=n$, which I haven't found a way to simplify.

Or, if we're looking at the wider version of the problem where we have labeled parts $A_1,A_2,...,A_m$, then the number of ways you can distribute the $n$ objects to the $m$ sets (including potentially empty $A_j$s) is simply $m^n$.
 
Last edited:

conscipost

Member
Jan 26, 2012
39
I realize you mean for $m,n,j$ to be integers. It's still a tough problem.

After looking carefully, the link wasn't as related as I thought, so sorry about that.

Some things I figured out that might help: you can add up the multinomial coefficients
$$
\binom{n}{k_1,k_2,...,k_m}
$$
Over all choices of $k_j$ such that $0≤k_j≤n$, not counting repeating combinations of $k_j$, and $\sum_{j=1}^m k_j=n$, which I haven't found a way to simplify.

Or, if we're looking at the wider version of the problem where we have labeled parts $A_1,A_2,...,A_m$, then the number of ways you can distribute the $n$ objects to the $m$ sets (including potentially empty $A_j$s) is simply $m^n$.
Thanks again.
What I am hoping to find is the number of j-tuples of positive integers that are non increasing so that a0+a1+...+aj=n and ai is less than or equal to m.
Partition (number theory) - Wikipedia, the free encyclopedia
 
Last edited: