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$ Dec 13, 2023 at 15:34
  • 1
    $\begingroup$ The denominator is $i+1$ not $j+1$. $\endgroup$ 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$ 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$ 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
    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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.