Simultaneous cores with restrictions and a question of Zaleski and Zeilberger
Paul Johnson

Fast Micron-Scale 3D Printing with a Resonant-Scanning Two-Photon Microscope
    Benjamin W. Pearre (1),

Christos Michas (2),

Jean-Marc Tsang (2),

Timothy J. Gardner (1,2),

Timothy M. Otchy (1)


((1) Dept of Biology, Boston University, Boston, MA, USA,

(2) Dept of Biomedical Engineering, Boston University, Boston, MA, USA)

    December 30, 2023
==============================================================================================================================================================================================================================================================


  The main new result of this paper is to count the number of (n,n+1)-core partitions with odd parts, answering a question of Zaleski and Zeilberger <cit.> with bounty a charitable contribution to the OEIS.  Along the way, we prove a general theorem giving a recurrence for (n, n+1)-core parts whose smallest part λ_ℓ and consecutive part differences λ_i-λ_i+1 lie in an arbitrary M⊂ which unifies many known results about (n, n+1)-core partitions with restrictions.  We end with discussions of enrichments of this theorem that keep track of the largest part, number of parts, and size of the partition, and about a few cases where the same methods work on more general simultaneous cores.
  


The paper is laid out as follows.  Section <ref> gives a quick background to the question and states our main theorems.  Section <ref> reviews the abacus construction, and uses it to prove Theorem <ref>, a general theorem giving recrusions for simultaneous (n,n+1)-cores meeting certain restrictions.  Section <ref> relates the count of simultaneous cores with odd parts to that of even parts, answering a question of Zeilberger and Zaleski. Section <ref> briefly discusses enriching the recursion of the main theorem to take into account other partitions, and Section <ref> briefly touches on a few cases where the basic recursion can move beyond (n, n+1)-cores.  



§ INTRODUCTION
 
A partition of n is a nonincreasing sequence λ_1≥λ_2≥⋯≥λ_k> 0 of positive integers such that ∑λ_i=n. We call n the size of λ and denote it by |λ|; we call
k the length of λ and denote it by ℓ(λ).


We frequently identify λ with its Young diagram; there are many conventions for this.  We draw λ in the first quadrant, with the parts of λ as the columns of a collection of boxes.

The arm a(□) of a cell □ is the number of cells contained in λ and above □, and the leg l(□) of a cell is the number of cells contained in λ and to the right of □.
The hook length h(□) of a cell is a(□)+l(□)+1.


The cell (2,1) of λ=3+2+2+1 is marked s; the cells in the
leg and arm of s are labeled a and l, respectively.


[scale=.5]
[thin, gray] (0,0) grid (1,3);
[thin, gray] (1,0) grid (3,2);
[thick] (0,0)–(0,3)–(1,3)–(1,2)–(3,2)–(3,1)–(4,1)–(4,0)–cycle;
(1.5,.5) nodes;
(1.5,1.5) nodea;
(2.5,.5) nodel;
(3.5,.5) node l;
(8.5,1.5) node[align=left] a(s)=# a=1 
 l(s)=# l=2 
 h(s)=4;





An a-core is a partition that has no hook lengths of size a. An (a,b)-core is a partition that is simultaneously an a-core and a b-core.  We use 𝒞_a,b to denote the set of (a,b)-cores.


We have labeled each cell □ of λ=3+2+2+1 with its hook length h(□).


[scale=.5]
[thin, gray] (0,0) grid (1,3);
[thin, gray] (1,0) grid (3,2);
[thick] (0,0)–(0,3)–(1,3)–(1,2)–(3,2)–(3,1)–(4,1)–(4,0)–cycle;
(.5,.5) node6;
(1.5,.5) node4;
(2.5,.5) node3;
(3.5,.5) node1;
(.5,1.5) node 4;
(1.5,1.5) node2;
(2.5,1.5) node1;
(.5,2.5) node1;



We see that λ is not an a-core for a∈{1,2,3,4,6};
but is an a-core for all other a.


The study of simultaneous core partitions began with the work of Anderson. <cit.>, who proved that when a and b are relatively prime, there 1/a+ba+ba of them.  Her proof uses the abacus to get a bijection with rational Dyck paths.   The study of simultaneous core partitions has exploded in recent years, largely due to the work of Amstrong, Hanusa and Jones <cit.> relating them to rational Catalan combinatorics.

One direction of this study initiated by Amdeberhan <cit.>, is to study simultaneous core partitions that are simultaneously core for more than two integers, and simultaneous core partitions that satisfy more classical conditions on partitions.  In <cit.> made many conjectures about counts of such simultaneous core partitions, which now seem to all be proven.  Our first result is a general theorem that gives a unified recursion that proves many of Amdeberhan's conjectures.  

The two most important examples for us are the following.  First, Amdeberhan conjectured that the number of (n, n+1)-core partitions with distinct parts was the n+1st Fibonacci number F_n+1; this was proven independently by Xiong <cit.> and Straub <cit.>.

Second, Amdeberhan conjectured a formula for the number P_d(n) of (n, n+1)-core partition all of whose parts are divisible by d, which was proven by Zhou <cit.>.  Specifically, if n=qd+r with 0≤ r<d, then 

    P_d(n)=r+1/n+1n+qn

which are known as Raney or Fuss-Catalan numbers, P_d(n)=A_q(d-1, r-1) in the notation in wikipedia. 

Our perspective is to unify both of these conditions (having distinct parts, and having all parts divisible by d) into the general family of conditions given by restricting the difference between consecutive parts of the partitions.  Let ℕ={0,1,2,…} be the natural numbers, and let 𝒫 denote the set of all partitions. Let ℓ(λ) be the number of parts, and define λ_ℓ+1=0 by convention.  We denote the empty partition by 0.


Let M⊂ℕ.  We define
  
    𝒫^M={λ∈ :  λ_i-λ_i+1∈ M  for  1≤ i ≤ℓ­1}

  
    𝒬^M={λ∈ :  λ_i-λ_i+1∈ M  for  1≤ i ≤ℓ}

That is, ^M is the set of partitions where the difference between consecutive parts is in M, and ^M⊂^M asks that in addition that the smallest part λ_ℓ is in M.


From our perspective, ^M is more natural, and will be focused on that. For most choices of M, ^M and ^M are very unnatural sets of partitions; we highlight a few choices of M that give more familiar classes of partitions.

 Let _+={1,2,…}.  Then ^_+=^_+ is the set of partitions with distinct parts.



For k>1 an integer, let k={0,k,2k,…}.  Then 𝒫^k is the set of partitions with all parts congruent modulo k, and ^k is the set of partitions with all parts divisible by k.
  In particular, ^2∖^2∪0 is the set of partitions with odd parts.


Combining the first two, taking M=k_+={k,2k,3k,…}, then ^k_+ consists of partitions with distinct parts, all of which are divisible by k, and ^k_+ consists of partitions with distinct parts, all of which are congruent mod k.


 Let +r={r,r+1,r+2,…} denote the set of integers great than or equal to r.  Then ^+r is the set of partitions with difference between consecutive parts at least r, and ^+r asks, in addition, that the smallest part is at least r.  When r=2, these two classes of partitions take part in the Rogers-Ramanujan identities:

    ∑_λ∈^+2 q^|λ|   =∏_m≥ 01/(1-q^5m+1)(1-q^5m+4)
    ∑_λ∈^+2 q^|λ|   =∏_m≥ 01/(1-q^5m+2)(1-q^5m+3)

  


 
  Let [r]={0,1,…, r}.  Then λ∈^[r] if and only if λ^T, the conjugate of λ, has no parts repeating more than r times.  These partitions take part in Glaisher's theorem:
  
    ∑_λ∈^[r]=∏_r+1∤ m1/1-q^m

in case r=1, this is Euler's theorem that the number of partitions of n into distinct parts is equal to the number of partitions of n into odd parts.



Our general theorem is a recurrence for |𝒞_n,n+1∩^M| for any subset M.  The recurrence has a different form depending on whether or not 0∈ M.  


  For M⊂, let C^M(n)=|𝒞_n∩^M| be the count of simultaneous (n, n+1)-core partitions with smallest part and consecutive part differences in M.  Then C^M(0)=1 (the empty partition), and C^m(n) is determined from this by the recurrence:
  
  
  * If 0∈ M,
    
    C^M_n+1=∑_k∈ M
    k≤ nC^M_kC^M_n-k

  
  * If 0∉ M,
    
    C^M_n+1=1+∑_k∈ M
    k≤ nC^M_n-k

  


We might term these recurrences the restricted recurrence Catalan and Fibonacci sequences, respectively; when M=, the recurrence is the standard recurrence for the Catalan numbers; when M=∖ 0, the recurrence is equivalent to the familiar formula for the sum of the first n Fibonacci numbers:

    F_n+1=1+∑_k=1^n-1 F_n-k

When M is only a subset of these two sets, the recurrence only has those terms corresponding to elements of M.

Both identities can be rephrased in terms of generating series, though if 0∈ M the statement requires the Hadamard product: recall if f=∑_i≥ 0 a_nq^n and g=∑_m≥ 0 b_jq^m are formal power series, the Hadamard product (f⋆ g)=∑_n≥ 0 a_nb_bq^n.
 For M ⊂, let 
    χ_M=∑_m∈ M q^m

  
    C^M(q)=∑_n≥ 0 C^M_nq^n
 

  Then if 0∈ M, we have
    
    C^M(q)=1+q(C_M(q)⋆χ_M(q))C_M(q)


  If 0∉ M, then 
    
    C_M(q)=1/1-q+qχ_m(q)C_m(q)

    and hence
    
    C_m(q)=1/1-q1/1-qχ_m(q)C_m(q)





Before we give the proof, we illustrate some examples of this theorem.

Let D(n) denote the number of (n, n+1)-cores with distinct parts, then D(n)=|𝒞_n∩^∖ 0|, and so we have
  
    D(n+1)=1+∑_k=1^n D(n-k)

  In particular, for n=0 the sum on the right hand side is empty, and so D(1)=1, and otherwise, removing the first term of the sum and reindexing gives
  
    D(n+1)=1+∑_k=1^n D(n-k)=D(n-1)+[1+∑_k=1^n-1 D(n-1-k)]=D(n-1)+D(n)

  and so D(n)=F(n), the Fibanocci numbers.




Let D_r(n) denotes the number of (n,n+1)-core with no part occuring more than r-times; by Example <ref> we have D_r(n)=|𝒞_n∩^[r]|, and hence  

    D_r(n+1)=∑_k=0^r D_r(k)D_r(n-k)

For n≤ r, this is the usual recurrence for Catalan numbers, and so in this range we have D_r(n)=C_n.  
If we take r=1, this directly recovers the standard Fibonacci recurrence for simultaneous cores with distinct parts, since D_1(0)=D_1(1)=1.  In general, since the recursion does not differ from the standard Catalan recursion until n>r, we have D_r(n)=C_n for n≤ r, and hence in general D_r(n+1)=∑_k=0^r C_k D_r(n-k).  Taking r=2, we have

    D_2(n+1)=D_2(n)+D_2(n-1)+2D_2(n-2)





Let P_d(n) denotes the number of (n, n+1)-core partitions with all parts divisible by d; this is the case M={0,d,2d,3d,…}.  The recurrence becomes:

    P_d(n+1)=∑_k=0^⌊ n/d⌋ P_d(dk)P_d(n-dk)

  which is Riordan's recurrence for the Fuss-Catalan numbers. In particular, in this case the Theorem reproves Amdeberhan's conjecture that, if n=qd+r with 0≤ r<d, then
  
    P_d(n)=r+1/n+1n+qq



 Let D_d(n) denote the number of (n, n+1)-core partitions with distinct parts, all divisible by d; this is the case M={d,2d,3d,…}. Let D_d(q) be the corresponding generating function.  We have χ_M(q)=q^d/(1-q^d), and a little algebra gives
  
    D_d(q)=1+q+q^2+⋯ +q^d-1/1-q^d-q^d+1

 and hence D_d(n) is the series determined by the recurrence D_d(n)=D_d(n-d)+D_d(n-d-1) and the initial values D_d(0)=D_d(1)=⋯=D_d(d-1)=1; when d=2 this is 1,1,1,2,2,3,4,5,7,9,12,16,… which up to reindexing is https://oeis.org/A000931A000931 the Padovan numbers.




Finally, Let O(n) and E(n) be the number of (n,n+1) cores with all parts odd or even, respectively.  Then E(n)=P_2(n) is already determined by the previous recurrence, and analysis of the abacus allows us to derive the formula

    E(n+2)=2O(n)-O(n-2)

and thus determine O(n); our derivation of this last expression is, at present, not as elegant as the expression seems to merit.



§ THE ABACUS CONSTRUCTION

In this section we briefly recall the abacus construction for n-core partitions.

Let w(λ)=a_1a_2a_3a_4⋯ be the boundary path of λ, with each a_i being either E or S, normalized so a_1=E is the first E step, and padded out with trailing Es if necessary.  Then λ is an n core if and only if a_k=E implies that a_k+n=E.  

The general idea behind the n-abacus construction is to split the a_i among n rows periodically.  If we write i=kn+r with 0≤ k, 1≤ r≤ n, then we will put a black circle at the rth row and kth column if a_i=E, and a white circle in that spot if a_i=S.  Note that this means our rows start with 1 but our columns start with 0.

On the n-abacus, the condition for being an n-core translate to once a spot on a given row is black, every later spot on that row must also be black.  Our choice of normalization means that for n-cores, the first row will always be filled entirely with black dots.    

Thus, we can record the n-core as a function f:{0,1,…, n-1}→ℕ by letting f(i) be the first column where the ith row has a black dot.  Note that we always have f(0)=0, giving a bijection from n-cores to ^n-1, but including this value will prove useful for describing (n, n+1)-cores.

The condition to see an n+1-core on the n abacus is that if the circle on the ith row and jth column is black, with i<n, then the circle at the i+1st row and j+1st column is also black.  In terms of the function f, this condition is f(i+1)≤ f(i)+1.    In addition to this, if the bead on the nth row (last row) and jth column is filled, then so must be the bead on the 1st row and j+2 column.  Since we only work with n-cores, the first row is always completely filled, and this condition is vacuous.  This is a large part of what makes (n, n+1)-cores easier to handle than general (a,b)-cores.

Summarizing, we have shown the following:
The set of (n, n+1)-core partitions are in bijection with functions f:{0,…, n-1}→ℕ satisfying:


  * f(0)=0

  * f(k+1)≤ f(k)+1





§ PROOF OF THE GENERAL THEOREM




 §.§ Main ideas
 Proving theorem <ref> depends on two things: understanding how the standard Catalan number recurrence is proven in terms of the abaci functions, and understanding how to spot whether or not an n-core is in ^M from its abaci.

The standard Catalan recurrence is often proven in terms of decomposing Dyck paths by the first return to the diagonal.  There is a natural bijection from abaci functions to Dyck paths – f(k) measures how far beneath the line y=x the Dyck path is at the kth step.  Thus, we can prove the standard recurrence for Catalan numbers by decomposing the abaci functions by their first nontrivial 0.

[scale=.8]
in 0,1,...,3           
in 0,1,...,7
(,) circle (.4);

  (-.5,7.5)–(-.5,6.5)–(.5,6.5)–(.5,5.5)–(1.5,5.5)–(1.5,4.5)–(-.5,4.5)–(-.5,1.5)–(.5,1.5)–(.5,-.5)–(3.5,-.5)–(3.5,7.5)–(-.5,7.5);
in 0,1,...,3           
in 0,1,...,7
(,) circle (.4);
 
[shift=(-.5,8.5), yscale=-1]
ıin 1,...,8
 at (0,ı) ı;

at (.5,7.5) 9;
at (.5,6.5) 10;
at (.5,5.5) 11;
[xshift=5cm]
  at (0,7) f(0)=0;
  at (0,6) f(1)=1;
  at (0,5) f(2)=2;
  at (0,4) f(3)=0;
  at (0,3) f(4)=0;
  at (0,2) f(5)=0;
  at (0,1) f(6)=1;
  at (0,0) f(7)=1;
  

[xshift=7cm]
  [very thin, gray] (0,0) grid (8,8);
  [very thin, dashed, gray] (0,0)–(8,8);
  [ultra thick](0,0)–(3,0)–(3,3)–(4,3)–(4,4)–(5,4)–(5,5)–(7,5)–(7,6)–(8,6)–(8,8);
  at (-.2,.2) 0;
  at (.8,1.2) 1;
  at (1.8,2.2) 2;
  at (2.8,3.2) 0;
  at (3.8,4.2) 0;
  at (4.8,5.2) 0;
  at (5.8,6.2) 1;
    at (6.8,7.2) 1;




[yshift=10cm]
[very thin, gray]  (0,0)  grid (7,6);
[ultra thick] (0,5)–(1,5)–(1,3)–(4,3)–(4,1)–(6,1)–(6,0);
at (.5,5.2) 1;
at (1.2, 4.5) 2;
at (1.2, 3.5) 3;
at (1.5,3.2) 4;
at (2.5,3.2) 5;
at (3.5,3.2) 6;
at (4.2, 2.5) 7;
at (4.2, 1.5) 8;
at (4.5,1.2) 9;
at (5.5,1.2) 10;
at (6.2, .5) 11;





To recognize whether or not the partition corresponding to a given abacus is in ^M, we must discuss how to recognize consecutive part differences λ_i-λ_i+1 in terms of the abacus.  

  An n-core partitions λ is in ^M if and only if the length of every run of white beads in a column is in M.
  

Since the black circles are horizontal steps, and the white circles are vertical steps, the differences between consecutive parts (and the smallest part) are exactly the lengths of the runs of consecutive white beads, that is, the number of white beads between any two consecutive black beads on the abacus.  

Since the first row is all black beads, none of these runs of beads will run across more than one column. 


The proof of Theorem 1 is simply combining the standard derivation of the Catalan recurrence with Lemma <ref>


 §.§ Proof of Theorem 1

Let f be the abacus function of an (n+1,n+2)-core partition.  

The proof is essentially in the diagram above, and the picture as follows:


First, we consider the case 0∉ M.  First, we argue that in the second column, we already have every bead is black.  Indeed, the top bead of the second column is black because λ is an n-core, and the second bead of the second column is black because λ is an n+1-core, but since 0∉ M if we ever have two consecutive black beads then all the beads from that point on must be black.  So λ is determined by its first column.

Now, consider the first column, although 0∉ M, there is still one partition where the second bead could also be black – the empty partition.  Otherwise, the second bead must occur after k white beads, where k∈ M.  Removing the first k+1 rows, the remaining n+1-(k+1)=n-k rows must be the abacus of an (n-k, n-k+1) core, giving the recurrence. 

This paragraph still holds in the case 0∈ M; now deleting the first row and first column from the first k+1 rows gives the abacus of a k, k+1 core.



Now, consider the first column; the top bead is black.  

In particular, looking after the first column; the dot on runner 0 is black, and so there must be another black dot on at least one of runner 1,2...r+1, or we would have r+1 consecutive white dots in a column.

Let ℓ>0 be the first positive runner that has a black dot.  Then, on the one hand we can read runners ℓ to r-1 as an n-ℓ abacus.  On the other hand, looking at runners 0..ℓ-1, the first column is fixed as a black dot and ℓ-1 white dots.  Looking at the second column, the first two dots must be black.  So, looking at the first





§ SIMULTANEOUS CORES WITH ALL ODD PARTS
 We now turn to addressing simultaneous cores with all odd parts.  

Let E(n) (O(n)) be the number of simultaneous (n,n+1)-cores with all parts even (odd, respectively).  Then
  
    2O(n)-O(n-2)=E(n+2)

  Since we can calculate E(n), this determines O(n).


Our proof of this theorem seems needlessly complicated – presumably there's a more direct proof.


  If λ has all odd parts, then λ_i-λ_i+1 is always even, except for λ_ℓ-λ_ℓ+1=λ_ℓ, the smallest part.















  
  In terms of the abacus diagram, any run of white dots has even length, except the last run has odd length.  Thus, we see that n-core partitions with all parts odd seem very closely related to n-core partitions with all parts even, and one might hope to relate them by just adding or removing an extra white bead to the last run.  If this run is in the first column, this works fine.  However, if the last run is not in the first column, then adding an extra column here will make one of the earlier columns have an odd run of white beads.

   Let DE(n) and DO(n) be the number of (n,n+1)-core partitions with all parts even and odd, respectively.  Then DO(n)=DE(n+1). 

   We define a bijection φ:DO(n)→ DE(n+1).  First, φ takes the empty partition to the empty partition. Since in both cases the partitions are required to have distinct parts, they are determined by the first column of their abacus.

    Let λ∈ DO(n) be nonempty;  then its n-abacus has at least one run of white beads.  All runs of white beads in its n-abacus have an even length, except the last run has an odd length.  We define the n+1-abacus of φ(λ) by its first column – it is the same as that of λ, except with one white bead added to its last run.  The result clearly has distinct parts and all runs of white beads having even length, and hence is in DE(n+1).
    Clearly φ is invertible, with φ^-1 removing one row from the n+1-abacus.
    


  


  There are two cases.  The simple case is if all the white circles are in the first column of the n-abacus of λ (that is, f(k)≤ 1).  Given such a simultaneous core with all parts odd, we may simply add one white bead to odd run of beads, adding an extra row to the abacus, and getting the abacus diagram of an (n+1, n+2)-core with simultaneous part.  Similarly, given a simultaneous core with all parts even, whose abacus is all in the first column, we may just remove a white dot from the last run of white dots and get an (n, n+1) core with all parts odd. 

  Let SE(n), SO(n) be the number of (n, n+1)-cores, whose n abacus has all white circles in the first column, and all parts even, or odd, respectively.  The previous paragraph shows SO(n)=SE(n+1).  On the other hand, we can derive a recursion for SE(n) just as in our main theorem, by decomposing over the location of the second black circle in the first column.  This gives
  
    SE(n)=SE(n-1)+SE(n-3)+SE(n-5)+⋯=SE(n-1)+SE(n-2)

  by removing the first term of the sum and using the identity on the remaing terms.  Note though that SE(0)=SE(1)=SE(2)=1, as the second equation only holds if n≥ 3.  Thus, SO(n-1)=SE(n)=F(n).

  The complicated case is when the abacus diagram of λ has white dots on at least two columns (that is, there is some x with f(x)≥ 2.  Denote CE(n), CO(n), the number of such (n, n+1)-cores with all parts even (or odd, respectively).

  If λ∈ CO(n), we may not simply insert a single extra row into our abacus diagram with a white dot in the last column and get a partition in CE(n+1).  Although doing so would make the last run of white circles have an even number, the runs of white circles in the previous columns would now have odd number of beads.

  In terms of the function f, suppose the last run was in the mth column, from rows ℓ+1 to ℓ+k; i.e., f(ℓ)=m-1, f(ℓ+1)=f(ℓ+2)=⋯=f(ℓ+k)=m, and f(ℓ+k+i)<m for i≥ 0.  Then the description above is attempts to define a new function g by
  
    g(i)= f(i)     i≤ℓ+k 
     m     i=ℓ+k+1 
     f(i-1)    i≥ℓ+k+2

The final run of white circles in the abacus of g does indeed have one more than that of f, but the run of beads in the m-1 column just before also has one more white bead in it; since this run was by assumption even before, it is now odd, a problem.



  To fix this, we will insert two new rows into the abacus diagram.  One of these rows will add a white bead to the last run of white beads; the other other one will add a black bead immediately or after this run, and have white beads in all previous columns.  Thus, we've added one white bead to the very last run of whites, but to every other run of white beads we've either added no white beads or two white beads, and the result is indeed in CE(n+2).

  However, there are two different ways we could add two columns as above – we can stick the black bead immediately before the last run, or immediately after the last run.  In terms of the function f defining the abacus, these two new functions g_b and g_a (for before and after) are
  
    g_b(i)= f(i)     i≤ℓ
    
      m-1     i=ℓ+1 
    
      m     i=ℓ+2 
    
      f(i-2)    i≥ℓ+3


  
    g_a(i)= f(i)     i≤ℓ+k 
    
      m     i=ℓ+k+1 
    
      m-1     i=ℓ+k+2 
    
      f(i-2)    i≥ℓ+k+3

[scale=.6]  
in 0,1,...,2           
in 0,1,...,4
(,) circle (.4);

  (-.5,4.5)–(-.5,3.5)–(.5,3.5)–(.5,1.5)–(1.5,1.5)–(1.5,.5)–(.5,.5)–(.5,-.5)–(2.5,-.5)–(2.5,4.5)–(-.5,4.5);
in 0,1,...,2           
in 0,1,...,4
(,) circle (.4);

at (1,-1) f;

[xshift=4cm]
in 0,1,...,2           
in 0,1,...,6
(,) circle (.4);

  (-.5,6.5)–(-.5,5.5)–(.5,5.5)–(.5,2.5)–(1.5,2.5)–(1.5,.5)–(.5,.5)–(.5,-.5)–(2.5,-.5)–(2.5,6.5)–(-.5,6.5);
in 0,1,...,2           
in 0,1,...,6
(,) circle (.4);

[thin, gray] (-.5,1.5)–(-.5,3.5)–(2.5,3.5)–(2.5,1.5)–cycle;
at (1,-1) g_b;
at (3.5,2.5) Added 
 rows;
  


[xshift=10cm]
in 0,1,...,2           
in 0,1,...,6
(,) circle (.4);

  (-.5,6.5)–(-.5,5.5)–(.5,5.5)–(.5,3.5)–(1.5,3.5)–(1.5,1.5)–(.5,1.5)–(.5,-.5)–(2.5,-.5)–(2.5,6.5)–(-.5,6.5);
in 0,1,...,2           
in 0,1,...,6
(,) circle (.4);

[thin, gray] (-.5,.5)–(-.5,2.5)–(2.5,2.5)–(2.5,.5)–cycle;
at (1,-1) g_a;
at (3.5,1.5) Added 
 rows;






  Thus, there are 2CO(n) abacus diagrams in CE(n+2) obtained in this way.  However,  some of the abacus diagrams in CE(n+2) are obtained twice in this way, while others aren't obtained at all.

  An abacus diagram in CE(n+2) is obtained twice in this way if both immediately before and following this run there's an “extra” black bead in that column. More precisely, if the last run of white circles is in the mth column from ℓ+1 to ℓ+k, then we must have f(ℓ)=m-1 and f(ℓ+1)=⋯=f(ℓ+k=m.  We say that there is an extra black bead before if in addition f(ℓ-1)=m-1, and we say there is an extra black bead after if in addition f(ℓ+k+1=m-1).

  In case there is an extra black bead both before and after, we may remove both the rows have the abacus having these “extra” black beads and get an abacus diagram in CE(n), and vice versa.  Thus, we are double counting CE(n) different elements.

[scale=.6]
in 0,1,...,2           
in 0,1,...,6
(,) circle (.4);

  (-.5,6.5)–(-.5,5.5)–(.5,5.5)–(.5,3.5)–(1.5,3.5)–(1.5,1.5)–(.5,1.5)–(.5,-.5)–(2.5,-.5)–(2.5,6.5)–(-.5,6.5);
in 0,1,...,2           
in 0,1,...,6
(,) circle (.4);

at (1,-1)  extra before 
 and after ;
[thin, gray] (-.5,.5)–(2.5,.5)–(2.5,1.5)–(-.5,1.5)–cycle;
[thin, gray] (-.5,4.5)–(-.5,5.5)–(2.5,5.5)–(2.5,4.5)–cycle;

[xshift=4cm]
  in 0,1,...,2           
in 0,1,...,4
(,) circle (.4);

  (-.5,4.5)–(-.5,3.5)–(.5,3.5)–(.5,2.5)–(1.5,2.5)–(1.5,1.5)–(.5,1.5)–(.5,-.5)–(2.5,-.5)–(2.5,4.5)–(-.5,4.5);
in 0,1,...,2           
in 0,1,...,4
(,) circle (.4);

at (1,-1) add two 
 before this;



[xshift=8cm]
  in 0,1,...,2           
in 0,1,...,4
(,) circle (.4);

  (-.5,4.5)–(-.5,3.5)–(.5,3.5)–(.5,1.5)–(1.5,1.5)–(1.5,.5)–(.5,.5)–(.5,-.5)–(2.5,-.5)–(2.5,4.5)–(-.5,4.5);
in 0,1,...,2           
in 0,1,...,4
(,) circle (.4);

at (1,-1) add two 
 after this;



[xshift=12cm]
  in 0,1,...,2           
in 0,1,...,4
(,) circle (.4);

  (-.5,4.5)–(-.5,3.5)–(.5,3.5)–(.5,2.5)–(1.5,2.5)–(1.5,.5)–(.5,.5)–(.5,-.5)–(2.5,-.5)–(2.5,4.5)–(-.5,4.5);
in 0,1,...,2           
in 0,1,...,4
(,) circle (.4);

at (1,-1) extra rows
 removed;



  
  The diagrams in CE(n+2) that aren't obtained at all are those that don't have an “extra” black bead before OR after the last run of white beads.   In this case, we see that immediately above the black bead that's the upper bound of this run, we must have another run of white beads; otherwise, the second to last column would have an odd run of white beads.

More long-windedly in terms of the function f: since the run of white beads is the last one, we must have f(ℓ+k+1≤ m-2).  What about f(ℓ-1)?  Since f(ℓ)=m-1, we must have f(ℓ-1)≥ m-2. Since hte last row of beads is at height m, we must have f(ℓ-1)≤ m.  Since there is no extra bead in front of the run by assumption, we cannot have f(ℓ-1)=m-1.  Finally, we cannot have f(ℓ-1)=m-2, as then we'd have an odd length run of beads in the m-1st column in rows ℓ to ℓ+k.  Therefore, we must have f(ℓ-1)=m.

[scale=.6]
  in 0,1,...,2           
in 0,1,...,11
(,) circle (.4);

  (-.5,11.5)–(-.5,10.5)–(.5,10.5)–(.5,9.5)–(1.5,9.5)–(1.5,5.5)–(.5,5.5)–(.5,4.5)–(1.5,4.5)–(1.5,.5)–(-.5,.5)–(-.5,-.5)–(2.5,-.5)–(2.5,11.5)–(-.5,11.5);
in 0,1,...,2           
in 0,1,...,11
(,) circle (.4);

[thin, gray] (-.5,.5)–(-.5,6.5)–(2.5,6.5)–(2.5,.5)–cycle;




Thus, in this case we can delete the whole final run of white beads (which has length 2c for some even c), the black bead bounding the bead above this, and the last white bead from this run before (hence deleting 2c+2 rows), and get a partition in CO(n-2c).  In terms of the function f, we are defining a new function h by


    h(i)= f(i)     i≤ℓ-2 
    
      f(i+2c+2)     i≥ℓ-1

However, there's the added wrinkle that we don't get all partitions in CO(n-2k) in this way, but only those with no “extra” black dots after the last run of white beads – the function h has its last odd length run ending at h(ℓ-2)=f(ℓ-2)=m, but h(ℓ-1)=f(ℓ+2c+1)≤ m-2.

But if we have an abacus diagram of a partition in CO(n-2k) that does have a “extra” black dot, after the last run of white beads, we may just turn that extra black dot to white, obtaining an arbitrary diagram in CE(n-2k).
[scale=.6]
in 0,1,...,2           
in 0,1,...,4
(,) circle (.4);

  (-.5,4.5)–(-.5,3.5)–(.5,3.5)–(.5,2.5)–(1.5,2.5)–(1.5,1.5)–(.5,1.5)–(.5,-.5)–(2.5,-.5)–(2.5,4.5)–(-.5,4.5);
in 0,1,...,2           
in 0,1,...,4
(,) circle (.4);

at (1,-1) extra after;

[xshift=8cm]
in 0,1,...,2           
in 0,1,...,4
(,) circle (.4);

  (-.5,4.5)–(-.5,3.5)–(.5,3.5)–(.5,2.5)–(1.5,2.5)–(1.5,.5)–(.5,.5)–(.5,-.5)–(2.5,-.5)–(2.5,4.5)–(-.5,4.5);
in 0,1,...,2           
in 0,1,...,4
(,) circle (.4);

at (1,-1) turned 'extra' to white;







That is, we've seen the number of partitions in CE(n+2) we've failed to count in 2CO(n) is ∑ (CO(n-2k)-CE(n-2k)).

  Putting it all together, we have:
 
    CE(n+2)=2CO(n)-CE(n)+∑_k≥ 1 (CO(n-2k)-CE(n-2k))

  or
  
    CO(n)=∑_k≥ 0( CE(n+2-2k)-CO(n-2k))

  Removing the first term of the sum, reindexing, and reapplying the equation, gives
  
    CO(n)   =CE(n+2)-CO(n)+∑_k≥ 0( CE(n-2+2-2k)-CO(n-2-2k))
       =CE(n+2)-CO(n)-CO(n-2)

  and hence CE(n+2)=2O(n)-CO(n-2).

  To get the corresponding identity for O(n) and E(n), we need to add back the one column simultaneous cores counted by SE(n) and SO(n).  But since SO(n-1)=SE(n)=F(n), we have
 
    SE(n+2)=F(n+2)=F(n+1)+F(n)=2F(n+1)-F(n-1)=2SO(n)-SO(n-2)

  







§ ENRICHED RECURSIONS
  It is natural to not just study the number of simultaneous cores, but various functions on them.  We briefly summarize some results about how these play with our basic recursion.

The most obvious are the size |λ|, length (or number of parts) ℓ(λ), and largest part λ_1. In particular, we can enrich the generating function C^M(q) to count the partitions λ according to any or all of these variables.  
Armstrong, Hanusa and Jones <cit.> define (q,t)-rational Catalan numbers are the sum
Paramonov <cit.> studies this sum over partitions with distinct parts.

The three basic statistics can all be read off easily from the abacus diagram:


  * The length ℓ(λ) is the number of black beads coming before at least one white bead

  * The largest part λ_1 is the number of white beads on the abacus
  
  * The size |λ| is the number of inversions, that is, pairs (a, b) where a is a black bead, b is a white bead, and a comes before b
  

When 0∉ M, and the partition has distinct parts, all of these statistics play well with our basic recurrence.  


Let TL_M(q) be the generating function for the sum of all the largest parts, TP_M(q) the total lengths, and TS_M(q) the generating function for the total sizes of all parts, respectively.  Then

    TL_M(q)=q^2d/dqχ_M(q)F_M(Q)1/1-qχ_M(q)


    TP_M(q)=qχ_M(q)F_M(q)1/1-qχ_M(q)


    TS_M(q)=(q^2d/dqχ_M(q)F_M(q)+qχ_MTL_M(q))1/1-qχ_M(q)


    TS_M=TL_M1/1-qχ_M




    TL=q^2χ^'/(1-q)(1-qχ)^2

  
    TP=qχ/(1-q)(1-qχ)^2

  
    TS=q^2χ^'/(1-q)(1-qχ)^3

 


§ BEYOND (N, N+1)-CORES
 




  plain
  




