3
$\begingroup$

I am working on distinct partitions. I recently created a function StrictIntegerPartitions. This is from the book Integer Partitions by George E. Andrews at Pennsylvania State University and Kimmo Eriksson at Mälardalen University published by Cambridge University Press in 2004 with ISBN 978-0-521-84118-4.

Another way of describing that the numbers in a set are distinct is that every pairwise difference is at least one. Let us say that parts are super-distinct if every difference is at least two. We shall now present a relatively modern bijective proof of a partition identity concerning distinct and super-distinct parts. Since every partition into super-distinct parts is also a partition into distinct parts, there must be more of the latter kind. For example, there are seven partitions of eleven into super-distinct parts: 11, 10+1, 9 +2, 8 +3, 7 +4, 7 + 3+1, 6 + 4+1 . There are a few more partitions where the parts are distinct but not super-distinct: 8 + 2+1, 6 +5, 6 + 3 +2, 5 + 4 + 2, and 5 + 3 + 2+1 . We shall prove the following strange-looking theorem: Theorem 3 p(n | super-distinct parts) — p(n | distinct parts, each even part > 2(# odd parts)). For n = 11, the right-hand expression counts the seven partitions 11, 10 + 1, 8 + 3, 7 + 4, 7 + 3 + 1, 6 + 4 + 1, and 6 + 5. The bijective proof of David Bressoud (from 1980) goes as follows: Take the Ferrers graphs of partitions into super-distinct parts and adjust the left margin to a slope of two dots extra indentation per row. Draw a vertical line in such a way that the last row has one dot to the left of this line, the next-to-last line has three dots to the left, etc. Thus, for 14 + 11 + 6 + 4 + 1, the graph looks like:

enter image description here

To the right of the line, we have obtained a new Ferrers graph, and we now rearrange its rows, starting with the odd rows in descending order followed by the even rows in descending order enter image description here

Ignoring the line and taking the rows of this graph as the parts of a partition, we get 14 + 8 + 6 + 7 + 1, a partition into distinct parts with each even part greater than four (i.e., twice the number of odd parts).

I would like to design a function SuperDistinctIntegerPartitions. For example, SuperDistinctIntegerPartitions11 would return {{11},{10,1},{9,2},{8,3},{7,4},{7,3,1},{6,4,1}}.

How can I use this to design a function to returns SuperDistinctIntegerPartitions? There is a Resource Function Ferrers Diagram that could be useful. The Resource Function uses a different orientation. Wikipedia states,

[Young diagrams and Ferrers diagrams] have several possible conventions, here we use English notation, with diagrams aligned in the upper-left corner.

enter image description here

This is related to this exercise. 36. Explain why the procedure is invertible, that is, why every partition into distinct parts with each even part greater than twice the number of odd parts is obtained exactly once. (Difficulty rating: 2)

I also found something helpful in this slideshow on slides 16 and 17.

enter image description here

enter image description here

I downloaded the presentation from http://player.slideplayer.com/download/10/2772378/g2qgMmjeKt8WgGBgww8Hdg/1691086330/2772378.ppt. Here are some more screenshots.

enter image description here

How do we know where the draw the line? How would I calculate the line should be drawn at the 9th position from the left and 8 positions from the right?

Here is another picture I drew for {14,11,6,4,1}

enter image description here

Here is a picture I drew with indentations for {14,11,6,4,1}: enter image description here

$\endgroup$

1 Answer 1

1
$\begingroup$

You want to use Mathematica to demonstrate the bijection between these 2 cases:

  1. Integer partition of $n$, all parts differ by $\geq 2$, i.e. The so-called super-strict integer partition
  2. Integer partition of $n$, $\text{ distinct parts }$, $\text{each even part}$ $>2\cdot (\# \text{odd parts})$.
SuperStrictIntegerPartitions[n_Integer] := 
 Module[{partitions, validPartition}, 
  partitions = IntegerPartitions[n];
  validPartition = 
   Function[partition, Min@Abs@Differences@Sort[partition] >= 2];
  Select[partitions, validPartition]]

superStrictIntegerPartitionsOf11 = SuperStrictIntegerPartitions[11]

DistinctEvenOddPartitions[n_Integer] := 
 Module[{partitions, validPartition}, 
  partitions = IntegerPartitions[n, All, Range[n]];
  validPartition = 
   Function[partition, 
    With[{evens = Select[partition, EvenQ], 
      odds = Select[partition, OddQ]}, 
     Min[evens] > 2*Length[odds] && DuplicateFreeQ[partition]]];
  Select[partitions, validPartition]]




distinctEvenOddPartitionsOf11 = DistinctEvenOddPartitions[11]

Length /@ {superStrictIntegerPartitionsOf11, 
  distinctEvenOddPartitionsOf11}     (*{7,7}*)

case 1 to case 2

helper[lst_List] := 
 Module[{odd, even}, odd = Sort[Select[lst, OddQ], Greater]; 
  even = Sort[Select[lst, EvenQ], Greater]; Join[odd, even]]
case1TransformToCase2[partition_] := 
 Module[{n, part1, part2}, n = Length@partition; 
  part1 = Reverse@Array[#*2 - 1 &, n]; 
  part2 = helper[partition - part1]; part1 + part2]

generatedDistinctEvenOddPartitionsOf11 = 
 case1TransformToCase2 /@ superStrictIntegerPartitionsOf11

Sort[Map[Sort, generatedDistinctEvenOddPartitionsOf11]] == 
 Sort[Map[Sort, distinctEvenOddPartitionsOf11]]

case 2 to case 1

helper1[lst_List] := 
 Module[{odd, even}, odd = Sort[Select[lst, OddQ], Greater];
  even = Sort[Select[lst, EvenQ], Greater]; Join[even, odd]]
case2TransformToCase1[partition_] := 
 Module[{n, part1, part2}, n = Length@partition;
  part1 = Reverse@Array[#*2 - 1 &, n];
  part2 = Sort[(helper1@partition) - part1, Greater]; part1 + part2]

generatedSuperStrictIntegerPartitionsOf11 = 
 case2TransformToCase1 /@ distinctEvenOddPartitionsOf11

Sort[Map[Sort, generatedSuperStrictIntegerPartitionsOf11]] == 
 Sort[Map[Sort, superStrictIntegerPartitionsOf11]]
$\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.