4
$\begingroup$

Consider the number of integer partitions of $n$, usually denoted by $p(n)$ and generated by $$\sum_{n\geq0}p(n)x^n=\prod_{k\geq1}\frac1{1-x^k}.$$

I have encountered an interesting enumeration.

Take all partitions of $n+2$ which do not use $1$ as a part. Then, count all different integers appearing in every such partition, call this number $u(n)$.

For example, say $n=4$ and hence $\{6,51,42,411,33,321,3111,222,2211,21111,111111\}$ are the partitions of $n+2=6$. Of these, $\{6,42,33,222\}$ avoid the integer $1$. The different integers here are $6,4,2,3,2$ for a total of $u(4)=5$.

QUESTION. Is it true that $u(n)=p(n)$ for all $n\geq1$?

Improve this question
$\endgroup$
1
  • $\begingroup$ Maybe this can be deducted from the first comment at OEIS A000070 and its proof, if any. $\endgroup$
    – Fabius Wiesner
    Commented Jul 21, 2023 at 8:20

2 Answers 2

Reset to default
7
$\begingroup$

Note that $u(n)=|\Theta(n+2)|$ where $\Theta(k)$ is the set of partitions of $k$ without 1's with one part being labelled (i.e., multisets of integers greater than 1 summing up to $k$ with one labelled element, like $\{{\bf 6}\},\{{\bf 4},2\},\{{\bf 2},4\},\{{\bf 3},3\}, \{{\bf 2},2,2\}$ for $k=6$).

Bijection from partitions of $n$ to $\Theta(n+2)$.

Take a partition $\lambda$ of $n$, let it have $s$ parts equal to 1. Remove them and add a labelled part $s+2$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Why is $u(n)=\vert\Theta(n+2)\vert$ true? $\endgroup$
    – T. Amdeberhan
    Commented Jul 22, 2023 at 1:21
  • 1
    $\begingroup$ @T.Amdeberhan: the reason is the same as the end of my other comment ("think about counting, for each $k$, the number of times $k$ appears as a part in a partition of $n+2$ with no $1$'s"). Although admittedly Fedor's language is a little ambiguous here; perhaps he should say "with one part value being labelled" (i.e., we cannot label the "second 2" in the partition (2,2)). $\endgroup$
    – Sam Hopkins
    Commented Jul 22, 2023 at 2:21
  • $\begingroup$ @SamHopkins I used to think that when we speak about partitions, there is no "second 2". But if we consider Young diagrams corresponding to partitions, there is indeed the second row of length 2. So, I add clarifications. $\endgroup$
    – Fedor Petrov
    Commented Jul 22, 2023 at 7:54
6
$\begingroup$

Let $q(n)$ count partitions of $n$ which don't have $1$ as a part.

Then $q(n-k)$ is the number of partitions of $n$ which do have $k$ as a part and don't have $1$ as a part, so $u(n) = \sum_{k=2}^{n+2} q(n+2-k) = \sum_{k'=0}^{n} q(n-k')$.

But $p(n) = \sum_{f=0}^n q(n-f)$ where $f$ counts the number of $1$s.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Your claim "Then $q(n−k)$ is the number of partitions of n which do have $k$ as a part and don't have 1 as a part," seems to require a proof. $\endgroup$
    – T. Amdeberhan
    Commented Jul 22, 2023 at 1:19
  • 1
    $\begingroup$ @T.Amdeberhan: it is immediate, no? To count partitions of $n$ which have $k$ as a part but no $1$'s, we force a part of $k$ and look at how many partitions of the remaining $n-k$ (still with no $1$'s) we can make. The slightly harder thing in Peter's answer to see is why $u(n) = \sum_{k=2}^{n+2} q(n+2-k)$, but this is also not hard (think about counting, for each $k$, the number of times $k$ appears as a part in a partition of $n$ with no $1$'s). $\endgroup$
    – Sam Hopkins
    Commented Jul 22, 2023 at 1:45
  • $\begingroup$ @T.Amdeberhan, I could add "by the trivial bijection", but it really is trivial. $\endgroup$
    – Peter Taylor
    Commented Jul 22, 2023 at 14:21

You must log in to answer this question.

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