5
$\begingroup$

While solving (a system of) a system of linear equations level-by-level recursively, I am finding some redundant equations for level $n\geq5$. The reason why the redundancies arise is because $P(n)\neq P(n-1)+P(n-2)$ for $n\geq5$. The redundancies are given by the sequence : $$ 0,0,0,0,1,1,3,4,7,10,16,21,32,43,60,80,110,\dots~. $$

Here, $P(n)$ is the number of partitions of the integer $n$. This is the sequence is given by $P(n-1)+P(n-2)-P(n)$ for $n\geq1$.

A generating function for the above sequence is $$ 1 - (1-q-q^2)\prod_{n=1}^\infty {1\over (1-q^n)}~. $$

Is this sequence (or any closely related one) encountered in some context in combinatorics? What is being counted?

(I have searched this in OEIS; there are a few sequences matching till the $16$ above but disagrees thereafter.)

Improve this question
$\endgroup$
6
  • 4
    $\begingroup$ By Euler's pentagonal-number theorem, the denominator $\prod_{n=1}^\infty (1-q^n)$ is $1 - q - q^2 + q^5 + q^7 - q^{12} - q^{15} + + - - \cdots$, so your sequence is $P(n-5) + P(n-7) - P(n-12) - P(n-15) + + - - \cdots$. Beyond that I don't know. $\endgroup$
    – Noam D. Elkies
    Commented Sep 1, 2019 at 3:20
  • 2
    $\begingroup$ Take a partition of n elements and remove 1 element from its smallest class. (If this gives an empty class, throw that away.) This gives P(n-1) results with (P(n)-P(n-1)) duplicates. Maybe you are removing something like two elements? Gerhard "Trying To Add An Idea" Paseman, 2019.08.31. $\endgroup$
    – Gerhard Paseman
    Commented Sep 1, 2019 at 3:37
  • $\begingroup$ @GerhardPaseman Could you please elaborate a bit more or give an example? I didn't quite follow what you meant by smallest class. $\endgroup$
    – TheTwistedSector
    Commented Sep 1, 2019 at 4:06
  • 1
    $\begingroup$ There is a way of generating all partitions of N from all partitions of N-1, assuming they are presented as ordered tuples of positive integers: add 1 in at most two ways. If a partition of N-1 does not have a unique smallest member (say it starts 3,3,5, ...), then prepend a 1 (to make it 1,3,3,5, ,...), otherwise prepend and then for a new partition add 1 to the smallest number. I wonder if your process involves "adding 2". Gerhard "Just Trying To Brainstorm Here" Paseman, 2019.08.31. $\endgroup$
    – Gerhard Paseman
    Commented Sep 1, 2019 at 5:29
  • 1
    $\begingroup$ I've added the sequence to the OEIS as A324368. $\endgroup$
    – Max Alekseyev
    Commented Sep 5, 2019 at 16:41

2 Answers 2

Reset to default
3
$\begingroup$

Let $C_k$ be the set of partitions of $n$ containing $k$.

Following @MaxAlekseyev's point we have, $$P(n-1)+P(n-2)-P(n)=|C_1|+|C_2|-P(n),$$ $$=|C_1\cap C_2|+|C_1\cup C_2|-P(n)$$ This is the # of partitions containing both 1 and 2, minus the # of partitions containing neither 1 nor 2.

This number is nonnegative since to any partition containing neither 1 nor 2, writing it in nonincreasing order as $t_1,\dots, t_k$, we can associate the partition $t_1,\dots,t_k-3,2,1$ which does contain 1 and 2 (and this map is one-to-one).

Thus for all $n$, $P(n-1)+P(n-2)-P(n)$ is exactly counting

how many partitions of $n$ contain both 1 and 2, and are not of the form $t_1,\dots,t_{k-1},t_k-3,2,1$ (removing $t_k-3$ if it is 0) where $t_1\ge\dots\ge t_k\ge 3$.

For $n=5$, this includes only one: $2+1+1+1$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for the answer. I implemented this on the computer and I seem to get the sequence 0, 0, 1, 1, 3, 4, 7, 10, 15, 21, 30, 41, 56, 76, 101,.. i.e. there is agreement till the 10. It is quite possible I am making a mistake though. $\endgroup$
    – TheTwistedSector
    Commented Sep 2, 2019 at 3:32
  • $\begingroup$ Here's the Mathematica code. add2[lst_] := Table[lst + 2 IdentityMatrix[Length[lst]][[i]], {i, 1, Length[lst]}]; cBoole[f_] := 1 - Boole[f]; isSpecial[lst_] := cBoole@MemberQ[cBoole@MemberQ[#, 1] & /@ add2[lst], 1]; isForm[lst_] := If[EvenQ[Total[lst]] && Count[lst, 1] == 2 && Count[lst, 2] == Length[lst] - 2, 0, 1]; which[n_] := (isForm[#] & /@ Partitions[n])*(isSpecial[#] & /@ Partitions[n]); bruteCount[n_] := Total[which[n]]; Table[bruteCount[n], {n, 1, 15}] $\endgroup$
    – TheTwistedSector
    Commented Sep 2, 2019 at 3:33
  • 1
    $\begingroup$ @TheTwistedSector sorry I think I fixed it now $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Sep 2, 2019 at 7:31
3
$\begingroup$

Notice that $P(n-1)$ counts the number of partition of $n$ that contain $1$, while $P(n-2)$ counts the number of partition of $n$ that contain $2$.

It follows that $P(n-1)+P(n-2)-P(n)$ equals the difference between the number of partitions of $n$ that contain $\{1,2\}$ and the number of partitions of $n$ that contain neither $1$ nor $2$.

Improve this answer
$\endgroup$

You must log in to answer this question.

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