tag:blogger.com,1999:blog-3722233.post9152128988613149804..comments2021-09-27T13:54:23.332-05:00Comments on Computational Complexity: Ferrer's Diagrams can be used to prove X theorems about partitions. What is X? Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-79518722684139292452021-05-06T00:45:08.859-05:002021-05-06T00:45:08.859-05:00on ferrer and young tableaux, i stumbled upon this...on ferrer and young tableaux, i stumbled upon this<br /><br />"Four Correspondences Between Graphs<br />and Generalized Young Tableaux"<br /><br />https://core.ac.uk/download/pdf/82185858.pdf<br /><br />John the Scotthttps://www.blogger.com/profile/14024505963810601849noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31939157025493736472021-04-30T11:18:25.110-05:002021-04-30T11:18:25.110-05:00Only two of these, the two I mentioned, seem to ha...Only two of these, the two I mentioned, seem to have Ferrer diagram proofs. Am I missing something? gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91043577014002367932021-04-30T11:16:57.598-05:002021-04-30T11:16:57.598-05:00The proof at stack exchange was nice but did not u...The proof at stack exchange was nice but did not use Ferrer diagrams. Is there a proof that uses thos- perhaps indirectly.gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42222910421918017002021-04-28T12:51:53.557-05:002021-04-28T12:51:53.557-05:00OH- feel free to post more on this (my last commen...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!gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43093823645460067452021-04-28T12:51:22.224-05:002021-04-28T12:51:22.224-05:00To ALL the commenters about: GREAT! I will look ov...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. <br /><br />If there are also other proofs (likely Generating Functions) I suspect that Ferrers diagrams are the easiest proof, and they also give the bijection. gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65152994426320759592021-04-28T12:45:10.003-05:002021-04-28T12:45:10.003-05:00Just wanted to add a couple of remarks. One of the...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.<br />https://en.wikipedia.org/wiki/Partition_(number_theory)#Conjugate_and_self-conjugate_partitions<br /><br />Another famous example is the pentagonal number theorem.<br />https://en.wikipedia.org/wiki/Pentagonal_number_theorem#Bijective_proof<br /><br />If Igor Pak's survey paper seems too dense, you might try these slides instead:<br />https://www.math.ucla.edu/~pak/lectures/bij-ptalk-IPAM1.pdf<br /><br />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.Timothy Chowhttp://alum.mit.edu/www/tchownoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30071214895094177152021-04-28T10:32:43.535-05:002021-04-28T10:32:43.535-05:00Igor Pak's survey of partition bijections migh...Igor Pak's survey of partition bijections might be relevant. https://www.math.ucla.edu/~pak/papers/psurvey.pdf<br />Timothy Chowhttp://alum.mit.edu/www/tchownoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83084591038377200692021-04-28T07:18:33.558-05:002021-04-28T07:18:33.558-05:00Relevant?
http://www-math.mit.edu/~rstan/papers/di...Relevant?<br />http://www-math.mit.edu/~rstan/papers/distinctparts.pdf<br />EGnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-85573855570508761452021-04-26T05:30:28.939-05:002021-04-26T05:30:28.939-05:00Lots could be 5 in some minds. Lots doesn't m...Lots could be 5 in some minds. Lots doesn't mean lots of interesting ones or ones not already proven in other ways.<br /><br />Three results and some generating functions at https://www.britannica.com/science/combinatorics/The-Ferrer-diagramJnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86936568366641154282021-04-26T00:22:49.958-05:002021-04-26T00:22:49.958-05:00There are many examples. My favorite is that the n...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<br /><br />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.domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.com