# Closed-form for the number of partitions of $n$ avoiding the partition $(4,3,1)$

• Let $$a(n)$$ be A309099 i.e. the number of partitions of $$n$$ avoiding the partition $$(4,3,1)$$.

• We say a partition $$\alpha$$ contains $$\mu$$ provided that one can delete rows and columns from (the Ferrers board of) $$\alpha$$ and then top/right justify to obtain $$\mu$$. If this is not possible then we say $$\alpha$$ avoids $$\mu$$. For example, the only partitions avoiding $$(2,1)$$ are those whose Ferrers boards are rectangles.

• Let $$b(n) = n + \sum\limits_{i=1}^{\left\lfloor\frac{n-1}{2}\right\rfloor}\sum\limits_{j=1}^{n-2i}\left\lfloor\frac{i+j-1}{i+1}\right\rfloor$$

I conjecture that $$b(n) = a(n).$$

Is there a way to prove it?

• is your conjecture based on empirical evidence or conceptual reasoning? Do you have a similar characterization of associated Ferrers boards? Dec 13, 2023 at 15:34
• The denominator is $i+1$ not $j+1$. Dec 13, 2023 at 21:50
• The $(4,3,1)$-avoiding" condition means equivalently that, after removing all instances of the maximum entry from the partition, one gets either the empty set, or a collection whose maximum and minimum differ by at most 1. So the relevant partitions are exactly those with $\le 2$ distinct parts, together with those of the form $[i,\dots, i, j,\dots, j, j-1,\dots, j-1]$ (with $i>j>1$). Surely that should help getting some explicit enumeration formula. Dec 14, 2023 at 7:32
• Remark: your $b(n)$ might be also written as$$\frac{n^2}4+\frac{7+(-1)^n}8+\sum_{i=2}^{\left\lfloor\frac n3\right\rfloor}\sum_{j=i}^{n-2i}\left\lfloor\frac ji\right\rfloor$$ Dec 14, 2023 at 7:48
• It is best not to editorialise in the title, so I have edited out the description of the closed form as amazing (without meaning to render any judgement on the amazing-ness myself). Dec 14, 2023 at 14:30

I suggest to show this inductively via showing that the difference $$a(n+1)-a(n)$$ always equals $$b(n+1)-b(n)$$.
As mentioned in the comments, the set $$S(n)$$ of $$(4,3,1)$$-avoiding partitions of $$n$$ is exactly the set of those for which the number of distinct parts is at most $$3$$, and if it equals $$3$$, then the smallest and second smallest parts should differ by $$1$$. Define now a map on partitions by increasing exactly one instance of the smallest part by $$1$$. This gives a "nearly injective" map from $$S(n)$$ into $$S(n+1)$$; indeed, the only "double hits" are partitions of the form $$[a^k, (a-1)^m]$$ for $$a\ge 3$$ and $$k,m\ge 1$$ (here $$a^k$$ should denote $$k$$-fold occurrence of $$a$$), since those are the images of both $$[a^{k-1}, (a-1)^{m+1}]$$ and $$[a^k, (a-1)^{m-1}, a-2]$$. Denote the set of these double hit partitions by $$A$$ and note that via conjugating Ferrer diagrams, $$A$$ is in bijection with the set of partitions of $$n+1$$ of the form $$[a,b^k]$$ with $$a and $$k\ge 2$$, i.e., with the set of solutions to $$n+1=a+kb$$ with $$1\le a and $$k\ge 2$$. For each $$b\in \{1,\dots, \lfloor \frac{n+1}{2}\rfloor\}$$, there is exactly one such solution, except for the proper divisors $$b$$ of $$n+1$$ (for which there is none). I.e., $$|A| = \lfloor \frac{n+1}{2} \rfloor - (d(n+1)-1) = \lfloor \frac{n-1}{2}\rfloor - (d(n+1)-2),$$ where $$d(n+1)-1$$ is the number of proper divisors of $$n+1$$.
Moreover, the set $$B$$ of partitions in $$S(n+1)$$ and not in the image of the map defined above are exactly the trivial partition $$[1,\dots, 1]$$ and the partitions $$[a,\dots, a, 1\dots, 1]$$ with $$a\ge 3$$ (and at least one instance of both $$a$$ and $$1$$). From this, it's obvious that $$|B|= 1+\sum_{a=3}^n \lfloor \frac{n}{a}\rfloor,$$ since indeed $$\lfloor \frac{n}{a}\rfloor$$ is just the number of possible multiplicities of the given value $$a$$ in a partition of the form above.
Thus, the difference $$a(n+1)-a(n)$$ is exactly $$|B|-|A|$$.
On the other hand, the difference $$b(n+1)-b(n)$$ is easily calculated (if you want, distinguish at first between even and odd $$n$$) as $$\begin{gather*} b(n+1)-b(n) = 1+\sum_{i=1}^{\lfloor \frac{n-1}{2} \rfloor} \lfloor \frac{n-i}{i+1}\rfloor = 1+(\sum_{i=1}^{\lfloor \frac{n-1}{2} \rfloor} \lfloor \frac{n+1}{i+1}\rfloor ) - \lfloor \frac{n-1}{2}\rfloor = \\ = 1+(\sum_{i=2}^{\lfloor \frac{n+1}{2} \rfloor} \lfloor \frac{n+1}{i}\rfloor ) - \lfloor \frac{n-1}{2}\rfloor \stackrel{(\star)}{=} 1+(\sum_{i= 2}^{\lfloor \frac{n+1}{2} \rfloor} \lfloor \frac{n}{i}\rfloor ) - \underbrace{(\lfloor \frac{n-1}{2}\rfloor - (d(n+1)-2))}_{=|A|} = \\ = |B| + \underbrace{(\lfloor \frac{n}{2} \rfloor - \sum_{i=\lfloor \frac{n+1}{2} \rfloor+1}^n 1)}_{=0} -|A| = |B|-|A| = a(n+1)-a(n). \end{gather*}$$ the equality marked $$(\star)$$ coming from the fact that $$\lfloor \frac{n}{i}\rfloor$$ and $$\lfloor \frac{n+1}{i}\rfloor$$ differ iff $$i\notin \{1,n+1\}$$ is a divisor of $$n+1$$.