Partitions with a unique maximum part

Arrangements, combinations and permutations, probability, ...
Post Reply
User avatar
PurpleBlu3s
Posts: 73
Joined: Mon Sep 19, 2011 5:49 pm

Partitions with a unique maximum part

Post by PurpleBlu3s » Tue May 31, 2016 4:00 pm

I am in need of a way to calculate a few things about partitions. If we say there are 4 objects (n=4), then the partitions of 4 are:
4
3 + 1
2 + 2 *
2 + 1 + 1
1 + 1 + 1 + 1 *

* these partitions do not have a unique mode.

I'm looking for a function, p'(n), that will tell me how many partitions there are with unique maximum values (i.e. a unique mode). So p(4) = 5, but p'(4) = 3.

Also, I am looking for a function that can tell me what the unique maximum value is for a particular partition, i, in the set of partitions. For instance, in the partition 3+1, the unique maximum/mode is 3.

Can anyone help me with this?

Many thanks.
Image

User avatar
jaap
Posts: 520
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Partitions with a unique maximum part

Post by jaap » Wed Jun 01, 2016 9:54 am

The only definition of mode that I know is "the value that appears most often in a set of data" but that is clearly not what you mean here.

User avatar
PurpleBlu3s
Posts: 73
Joined: Mon Sep 19, 2011 5:49 pm

Re: Partitions with a unique maximum part

Post by PurpleBlu3s » Wed Jun 01, 2016 11:25 am

If you think of partitioning data based on value, then what I mean is the number of occurrences of the mode.

For example, we have a set of 8 data points:

1 1 2 3 2 2 2 4

Grouping them based on their value:

(2 2 2 2) (1 1) (3) (4)

Counting the size of the groups:

4 2 1 1

This is a partition of 8, and the number of occurrences of the mode is 4.
Image

v6ph1
Posts: 109
Joined: Mon Aug 25, 2014 6:14 pm

Re: Partitions with a unique maximum part

Post by v6ph1 » Wed Jun 01, 2016 10:09 pm

The classic way of calculating the partitions is recursive using the Pk(n) = Partitions of n with k as maximum:
https://en.wikipedia.org/wiki/Partition ... r_of_parts
So you can use these results and calc p*(n) = ∑i=2n Pi-1(n-i)
Image

merlinnimue
Posts: 4
Joined: Sun Aug 28, 2016 3:27 pm

Re: Partitions with a unique maximum part

Post by merlinnimue » Sun Apr 29, 2018 6:35 pm

I know this is old, but I just saw this on reviewing the forums and I wanted to share my thoughts (spoilered for anyone who wants to work on it).
Expand
I believe $p'(n) = p(n - 1)$.

By the remarks of v6ph1, the generating function for $p'(n)$ can be written as $$\sum p'(n)x^n = x + \frac{x^2}{1 - x} + \frac{x^3}{(1 - x)(1 - x^2)} + \frac{x^4}{(1 - x)(1 - x^2)(1 - x^3)} + \dots$$where the monomial represents the largest part, and the binomials represent all lesser parts.

But, on computing the partial sums, I noticed something interesting: $$\begin{align} x &= x \\ x + \frac{x^2}{1 - x} &= \frac{x}{1 - x} \\ x + \frac{x^2}{1 - x} + \frac{x^3}{(1 - x)(1 - x^2)} &= \frac{x}{(1 - x)(1 - x^2)} \\ x + \frac{x^2}{1 - x} + \frac{x^3}{(1 - x)(1 - x^2)} + \frac{x^4}{(1 - x)(1 - x^2)(1 - x^3)} &= \frac{x}{(1 - x)(1 - x^2)(1 - x^3)} \end{align}$$It therefore follows that $$\sum p'(n)x^n = x \prod \frac1{1 - x^k} = \sum p(n) x^{n + 1}$$After I saw this, I realized that the correspondence is trivial: any partition $\lambda$ of $n - 1$ gives a partition of $n$ with unique largest part by adding 1 to any of the largest parts of $\lambda$.
Image

Post Reply