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.
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
ReplyDeleteAnother 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.
The proof at stack exchange was nice but did not use Ferrer diagrams. Is there a proof that uses thos- perhaps indirectly.
DeleteLots could be 5 in some minds. Lots doesn't mean lots of interesting ones or ones not already proven in other ways.
ReplyDeleteThree results and some generating functions at https://www.britannica.com/science/combinatorics/The-Ferrer-diagram
Only two of these, the two I mentioned, seem to have Ferrer diagram proofs. Am I missing something?
DeleteRelevant?
ReplyDeletehttp://www-math.mit.edu/~rstan/papers/distinctparts.pdf
Igor Pak's survey of partition bijections might be relevant. https://www.math.ucla.edu/~pak/papers/psurvey.pdf
ReplyDeleteJust 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.
ReplyDeletehttps://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.
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.
ReplyDeleteIf there are also other proofs (likely Generating Functions) I suspect that Ferrers diagrams are the easiest proof, and they also give the bijection.
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!
ReplyDeleteon ferrer and young tableaux, i stumbled upon this
ReplyDelete"Four Correspondences Between Graphs
and Generalized Young Tableaux"
https://core.ac.uk/download/pdf/82185858.pdf