Sunday, April 25, 2021

Ferrer's Diagrams can be used to prove X theorems about partitions. What is X?

1978: I took an excellent  ugrad course in combinatorics from James C Frauenthal (he sometimes wrote his name as the biniomial cofficient (J choose F))  and he covered Ferrer's diagrams. They are a nice way to prove equalities about types of partitions.   See here for a definition and a few examples. I have this (possibly false) memory that there were LOTS of partition theorems proven nicely with Ferrer's diagrams.

Fast forward to 2021:

2021: My TA Emily  needs a topic to cover in Honors Discrete Math. I have this memory that there were LOTS of theorems about partitions proven with Ferrer's diagrams. We look at many websites on Ferrer diagrams  and  find only TWO examples:

The numb of partitions of n into k parts is the numb of partitions of n into parts the largest of which is k.


The numb of partitions of n into \le k parts is the numb of partitions of n into parts the largest of which is \le k

We DO find many theorems about partitions such as this corollary to the Rogers-Ramanujan theorem:

The numb of partitions of n such that adjacent parts differ by at least 2 is the numb of partitions of n such that each partition is either \equiv 1 mod 5 or \equiv 4 mod 5.

This is a HARD theorem and there is no Ferrer-diagram or other elementary proof. 

SO, I have one MEMORY but the reality seems different. Possibilities:

1) My memory is wrong. There really are only 2 examples (or some very small number).

2) There are other examples but I can't find them on the web. I HOPE this is true--- if someone knows of other ways to use Ferrer diagrams to get partition results, please comment. 


10 comments:

  1. There are many examples. My favorite is that the number of partitions of n into distinct parts equals the number of partitions of n into odd parts: https://math.stackexchange.com/questions/54961/the-number-of-partitions-of-n-into-distinct-parts-equals-the-number-of-partiti

    Another one that I like is that the sum of the number of partitions from 0 to d − 1 with the additional property that the smallest part does not equal the second smallest part is the number of partitions of d.

    ReplyDelete
    Replies
    1. The proof at stack exchange was nice but did not use Ferrer diagrams. Is there a proof that uses thos- perhaps indirectly.

      Delete
  2. Lots could be 5 in some minds. Lots doesn't mean lots of interesting ones or ones not already proven in other ways.

    Three results and some generating functions at https://www.britannica.com/science/combinatorics/The-Ferrer-diagram

    ReplyDelete
    Replies
    1. Only two of these, the two I mentioned, seem to have Ferrer diagram proofs. Am I missing something?

      Delete
  3. Relevant?
    http://www-math.mit.edu/~rstan/papers/distinctparts.pdf

    ReplyDelete
  4. Igor Pak's survey of partition bijections might be relevant. https://www.math.ucla.edu/~pak/papers/psurvey.pdf

    ReplyDelete
  5. Just wanted to add a couple of remarks. One of the simplest examples is the bijection between self-conjugate partitions and partitions into distinct odd parts.
    https://en.wikipedia.org/wiki/Partition_(number_theory)#Conjugate_and_self-conjugate_partitions

    Another famous example is the pentagonal number theorem.
    https://en.wikipedia.org/wiki/Pentagonal_number_theorem#Bijective_proof

    If Igor Pak's survey paper seems too dense, you might try these slides instead:
    https://www.math.ucla.edu/~pak/lectures/bij-ptalk-IPAM1.pdf

    Let me also remind you that another keyword you can try is "Young diagram." Young diagrams are used in proofs of many theorems about Young tableaux, although if you really are interested only in theorems about partitions, then maybe theorems about Young tableaux (or plane partitions) don't count.

    ReplyDelete
  6. To ALL the commenters about: GREAT! I will look over all of your references and at some point produce a survey of ALL partition results that can be proven from Ferrer's diagrams- even if its only 5, thats 3 more than I had.

    If there are also other proofs (likely Generating Functions) I suspect that Ferrers diagrams are the easiest proof, and they also give the bijection.

    ReplyDelete
  7. OH- feel free to post more on this (my last comment could be viewed as `Okay, we're done' which is NOT true- if there is more, thats great!

    ReplyDelete
  8. on ferrer and young tableaux, i stumbled upon this

    "Four Correspondences Between Graphs
    and Generalized Young Tableaux"

    https://core.ac.uk/download/pdf/82185858.pdf

    ReplyDelete