5
$\begingroup$
  • 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?

$\endgroup$
7
  • 2
    $\begingroup$ is your conjecture based on empirical evidence or conceptual reasoning? Do you have a similar characterization of associated Ferrers boards? $\endgroup$ Commented Dec 13, 2023 at 15:34
  • 1
    $\begingroup$ The denominator is $i+1$ not $j+1$. $\endgroup$ Commented Dec 13, 2023 at 21:50
  • 5
    $\begingroup$ 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. $\endgroup$ Commented Dec 14, 2023 at 7:32
  • 2
    $\begingroup$ 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$$ $\endgroup$ Commented Dec 14, 2023 at 7:48
  • 3
    $\begingroup$ 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). $\endgroup$
    – LSpice
    Commented Dec 14, 2023 at 14:30

1 Answer 1

6
$\begingroup$

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<b$ and $k\ge 2$, i.e., with the set of solutions to $n+1=a+kb$ with $1\le a<b$ 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$.

$\endgroup$

You must log in to answer this question.

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