On the Intriguing Problem of Counting (n + 1, n + 2)-core partitions into Odd Parts Anthony ZALESKI and Doron ZEILBERGER

Abstract: Tewodros Amdeberhan and Armin Straub initiated the study of enumerating subfamilies of the set of (s, t)-core partitions. While the enumeration of (n + 1, n + 2)-core partitions into distinct parts is relatively easy (in fact it equals the Fibonacci number F_{n+2}), the enumeration of (n + 1, n + 2)-core partitions into odd parts remains elusive. Straub computed the first eleven terms of that sequence, and asked for a “formula,” or at least a fast way, to compute many terms. While we are unable to find a “fast” algorithm, we did manage to find a “faster” algorithm, which enabled us to compute 23 terms of this intriguing sequence. We strongly believe that this sequence has an algebraic generating function, since a “sister sequence” (see the article), is OEIS sequence A047749 that does have an algebraic generating function. One of us (DZ) is pledging a donation of 100 dollars to the OEIS, in honor of the first person to generate sufficiently many terms to conjecture (and prove non-rigorously) an algebraic equation for the generating function of this sequence, and another 100 dollars for a rigorous proof of that conjecture. Finally, we also develop algorithms that find explicit generating functions for other, more tractable, families of (n+1, n+2)-core partitions.

Added Jan. 24, 2018: Paul Johnson observed ([J]) and proved that the ”sister-sequence” counts (n+1, n+2)-core partitions into even parts, and even more impressively, related the two sequences, that easily implies a fast way to compute the enumerating sequence that we were interested in, from which one can easily derive a (rather complicated!) algebraic equation satisfied by the generating function. We would have needed 53 terms (rather than 23) to have guessed it.

Added Feb. 28, 2018: Paul Johnson has just posted his beautiful article

Simultaneous cores with restrictions and a question of Zaleski and Zeilberger,

https://arxiv.org/abs/1802.09621 ,

that does much more than we asked. A donation to the OEIS, of $200, in honor of Paul Johnson, has been made.

Supporting Maple Packages and Output

All the results in this article were obtained by the use of the Maple packages

• http://www.math.rutgers.edu/~zeilberg/tokhniot/OddArmin.txt ,
• http://www.math.rutgers.edu/~zeilberg/tokhniot/core.txt ,
• http://www.math.rutgers.edu/~zeilberg/tokhniot/stCorePlus.txt ,

whose output files, along with links to diagrams, are available from the front of this article

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/oddarmin.html .

(s, t)-Core Partitions

Recall that a partition is a non-increasing sequence of positive integers λ = (λ_{1}, …, λ_{k}) with k ≥ 0, called its number of parts; n := λ_{1} + … + λ_{k} is called its size, and we say that λ is a partition of n. Also recall that the Ferrers diagram (or equivalently, using empty squares rather than dots, Young diagram) of a partition λ is obtained by placing, in a left-justified way, λ_{i} dots at the i-th row. For example, the Ferrers diagram of the partition (5, 4, 2, 1, 1) is

\begin{matrix}∗ & ∗ & ∗ & ∗ & ∗ \\ ∗ & ∗ & ∗ & ∗ \\ ∗ & ∗ \\ ∗ \\ ∗ \end{matrix} .

Recall also that the hook length of a dot (i, j) in the Ferrers diagram, 1 ≤ j ≤ λ_{i}, is the number of dots to its right (in the same row) plus the number of dots below it (in the same column) plus one (for itself), in other words λ_{i}−i+λ′_{j} −j+1, where λ′ is the conjugate partition, obtained by reversing the roles of rows and columns. (For example if λ = (5, 4, 2, 1, 1) as above, then λ′ = (5, 3, 2, 2, 1).)

Here is a table of hook-lengths of the above partition, (5, 4, 2, 1, 1):

9 6 4 3 1 7 4 1 1 4 1 2 1 .

It follows that its set of hook-lengths is {1, 2, 3, 4, 6, 7, 9}. A partition is called an s-core if none of its hook-lengths is s. For example, the above partition, (5, 4, 2, 1, 1), is a 5-core, and an i-core for all i ≥ 10.

A partition is a simultaneous (s, t)-core partition if it avoids hook-lengths of both s and t. For example, the above partition, (5, 4, 2, 1, 1), is a (5, 8)-core partition (and a (5, 10)-core partition, and a (100, 103)-core partition etc.)

For a lucid and engaging account, see [AHJ].

As mentioned in [AHJ], Jaclyn Anderson ([An]) very elegantly proved the following.

Theorem ([An]) If s and t are relatively prime positive integers, then there are exactly

\frac{(s + t − 1)!}{s!t!}

(s, t)-core partitions.

For example, here are the (3 + 5 − 1)!/(3!5!) = 7 (3, 5)-core partitions:

{empty, 1, 2, 11, 31, 211, 4211} .

The Order Ideal P_{n+1,n+2} It turns out that it is most convenient to work with the order ideal

P_{s,t} := N\(sN + tN) ,

where N is the set of non-negative integers. Anderson showed that (s, t)-core partitions are in one-to-one correspondence with order ideals of P_{s,t} ([An]). Our poset of interest, P_{n+1,n+2}, can be identified with a triangular region in the 2D rectangular lattice, let’s call it A_{n},

A_{n} := {(i, j) ∈ N^{2} | 0 ≤ i ≤ n − 1 , 0 ≤ j ≤ n − 1 − i} ,

consisting of (n + 1)n/2 lattice points. We label the lattice point with

L(i, j) := (n + 1)n − 1 − (n + 2)i − (n + 1)j ,

in other words, we identify the lattice point (i, j) with the member (n + 1)n − 1 − (n + 2)i − (n + 1)j of P_{n+1,n+2}. To see the lattice P_{9,10} see

http://sites.math.rutgers.edu/~zeilberg/tokhniot/PictOddArmin/O0.html ,

and to see the lattice P_{10,11} see

http://sites.math.rutgers.edu/~zeilberg/tokhniot/PictOddArmin/O1.html .

Note that the point (n − 1, 0) is labeled 1, and when we read the labels along diagonals, from the bottom-right to the top-left, the labels increase by 1, but as we move from the end of one diagonal to the next one there are “discontinuities” of sizes 3, 4, …, n + 1 respectively. A subset S of A_{n} is an order ideal if it satisfies the following condition:

• If (i, j) ∈ S then (i′, j′) ∈ S for all (i′, j′) ∈ S such that i′ ≥ i and j′ ≥ j. In other words, if a lattice point belongs to S, then so do all the lattice points of A_{n} that are both to its (weak) right and are (weakly) above it. Conversely, and equivalently,

• If (i, j) ∉ S, then the set {(i′, j′) ∈ A_{n} | i′ ≤ i and j′ ≤ j} is disjoint from S. In other words, if a lattice point is unoccupied, then all the lattice points (weakly) below and (weakly) to its left are also unoccupied. With this interpretation, it is very easy to prove the special case of Anderson’s theorem that the number of (n + 1, n + 2)-core partitions is Catalan’s number (2n + 2)!/((n + 1)!(n + 2)!). Given such an order ideal, let’s call it S, let i (0 ≤ i ≤ n) be the smallest positive integer with the property that (n − 1 − i, i) is not a member of S: in other words, the smallest integer i such that (n − 1, 0), (n − 2, 1), …, (n − i, i − 1) are members of S while (n − 1 − i, i) is not a member of S.

Then all the points to the left of and below (n − 1 − i, i) are definitely unoccupied, and the order ideal has two parts,

• Those (strictly) below and (strictly) to the right of (n − 1 − i, i) ,

• Those (strictly) above and (strictly) to the left of (n − 1 − i, i) .

The former component is isomorphic to an order ideal of A_{i−1} with its outer diagonal fully occupied; i.e., by definition of i, {(n − 1, 0), (n − 2, 1), …, (n − i, i − 1)} are occupied, and removing these “mandatory” members, the remaining set is isomorphic to an order ideal of A_{i−2}. Let’s call it S_{1}.

The top part is isomorphic to an order ideal of A_{n−i}, let’s call it S_{2}.

This introduces a canonical decomposition

S → (i, S_{1}, S_{2}) , 0 ≤ i ≤ n , S_{1} ∈ A_{i−2} , S_{2} ∈ A_{n−i}  (CanonicalDecomposition)

that is obviously one-to-one. Let a_{n} be the number of order ideals of A_{n}; then it follows that it satisfies the recurrence

a_{n} = ∑_{i=0}^{n} a_{i−1}a_{n−i−1} ,

with the initial condition a_{−1} = 1. As is well-known (and easy to see) this implies that indeed a_{n} = (2n + 2)!/((n + 1)!(n + 2)!).

Note that for the above argument the labels are irrelevant.

Counting subfamilies

Distinct Partitions

What about counting (n + 1, n + 2)-core partitions into distinct parts? It was conjectured by Amdeberhan[Am], and first proved (as a special case of a much more general result) by Straub[S1] that this number is F_{n+2}, where (F_{n}) is the Fibonacci sequence.. Using order ideals, this is immediate. By the transformation

(a_{1}, a_{2}, …, a_{k}) → (a_{1} − (k − 1), …, a_{k}) ,

from the sorted list of labels to an (n + 1, n + 2)-core partition, the condition of being distinct translates to the fact that the corresponding order ideal can’t have any adjacent points, when “read” along diagonals, from right-to-left and from bottom-to-top. This precludes any member of an inner diagonal (since their existence would imply at least two adjacent points in the outermost diagonal), and the members of S that do belong to the outer-diagonal can’t be adjacent. Let d_{n} be their number. If (n − 1, 0) is not a member of S then S can be viewed as an order ideal (with the above condition) of A_{n−1}, accounting for d_{n−1} such creatures. On the other hand, if (n − 1, 0) ∈ S, then (n − 2, 1) ∉ S, and removing both of these yields an order ideal of A_{n−2} (with the above conditions), hence d_{n} satisfies the recurrence

d_{n} = d_{n−1} + d_{n−2} ,

subject to the initial conditions d_{0} = 1, d_{1} = 2.

For multi-cores see the elegant paper [AmL].

Intermezzo: The Joy and Agony of Enumerative Combinatorics

It is both fascinating and frustrating that in enumeration problems, ‘tweaking’ a problem ever so slightly turns it from almost trivial (and often, utterly trivial) to very difficult (and often, intractable). For example, it is utterly trivial that the number of n-step walks in the 2D rectangular lattice is 4^{n}, but just add the adjective “self-avoiding”—in other words, the number of such walks that never visit the same vertex twice—and the enumeration problem becomes (most probably) intractable and, at any rate, wide open.

Another example is counting permutations that avoid a pattern. The number of permutations, π, of length n that avoid the pattern 12 (i.e. you can’t have 1 ≤ i_{1} < i_{2} ≤ n such π_{i_{1}} < π_{i_{2}}) is trivially 1. A bit less trivially, but still very doable, is the fact that the number of permutations, π, of length n that avoid the pattern 123 (i.e. you can’t have 1 ≤ i_{1} < i_{2} < i_{3} ≤ n such π_{i_{1}} < π_{i_{2}} < π_{i_{3}}) is the good old Catalan number (2n)!/(n!(n + 1)!). But for most patterns, such an enumeration is (probably) intractable. The simplest wide open case, that we believe is intractable (but we would be happy to be proven wrong) is to count permutations that avoid the pattern 1324 (OEIS sequence A061552 [https://oeis.org/A061552]), for which the current record is knowing the 36 first terms.

Returning to the main topic, consider enumerating (2n − 1, 2n + 1)-core partitions into distinct parts. Armin Straub conjectured the deceptively simple formula 4^{n}. Alas, its (known) proofs are far from simple! Straub’s conjecture was first proved, by Sherry H.F. Yan, Guizhi Qin, Zemin Jin, Robin D.P. Zhou [YQJZ], via an ingenious but rather complicated combinatorial proof. A shorter, but still non-trivial proof was given in [ZZ], using “guess-and-check,” and this was further simplified by Straub (see [ZZ]). As far as we know, enumerating (s, t)-core partitions into distinct parts for other cases, say (3n − 1, 3n + 1)-core partitions, is wide open.

The problem of counting (n + 1, n + 2)-core partitions into odd parts

Leonhard Euler famously proved that the number of partitions of an integer n into distinct parts equals the number of partitions of the same n into odd parts. (This classical theorem was recently refined in a new, very surprising way, by Armin Straub ([S1])).

Moving on to counting (n + 1, n + 2)-core partitions into odd parts (note that we are counting all of them, regardless of their size, so the n here is not the same as the n in Euler’s theorem), it seems that the number of such partitions has nothing to do with the number of (n + 1, n + 2)-core partitions into distinct parts (i.e. F_{n+2}). This new problem seems (at least to us) much harder. On the other hand, we believe that it should be doable, and invite anybody to tackle it (see the abstract) and thereby support the OEIS.

We will now describe our approach, its success (it enabled us to crank out 23 terms, thereby extending Straub’s 11 terms, and with better computers, and more optimization, one may be able to crank out a few more terms), and its major shortcoming. At the end of the day, it is an exponential time (and memory!) algorithm.

A Scheme for Counting Order Ideals of P_{n+1,n+2} Corresponding to (n + 1, n + 2)-core partitions into odd parts

It is readily seen, by the mapping from order ideals to partitions

(a_{1}, …, a_{k}) → (a_{1} + k − 1, a_{2} + k − 2, …, a_{k} + 0)

that an order ideal of P_{n+1,n+2} corresponds to an (n + 1, n + 2)-core partition into odd parts if and only if, when reading the occupied labels, as described above, along diagonals, from bottom-right to top-left, starting from the rightmost diagonal and “walking” to the left, (i) the first label read is odd and (ii) the labels alternate in parity. Since only the parity matters, we can color the vertices of A_{n} by the colors “even” and “odd.”

Alas, one has to distinguish two cases. For both n even and odd, the label of (n−1, 0) is odd (since it is always 1), and as you proceed, in A_{n} along diagonals, the parities alternate. But for n odd, all the parities along the same row are the same, while if n is even, they alternate. Hence we are forced to consider the more general problem where there is a “coloring” parameter, let’s call it c, (c = 0 or c = 1) such that the “color” is

C(i, j) := 1 + c i + (1 − c)j modulo 2 .

So let’s forget, for now, about (n + 1, n + 2)-core partitions into odd parts, and instead define the following:

• Let e^{(0)}(n) be the number of order ideals of P_{n+1,n+2} such that when read along diagonals, the occupied vertices alternate in color using coloring parameter c = 0, and the first label is odd.

• Let e^{(1)}(n) be the number of order ideals of P_{n+1,n+2} such that when read along diagonals, the occupied vertices alternate in color using coloring parameter c = 1, and the first label is odd.

Once we would find a way to compute both sequences e_{n}^{(0)} and e_{n}^{(1)}, our object of desire, the Straub sequence, enumerating (n + 1, n + 2)-core partitions into odd parts, let’s call it s_{n}, would be given by

s_{n} = \{ \begin{matrix}e_{n}^{(0)} , if n is even; \\ e_{n}^{(1)} , if n is odd \end{matrix} .

For two examples of order ideals corresponding to (10, 11)-core partitions into odd parts, see

http://sites.math.rutgers.edu/~zeilberg/tokhniot/PictOddArmin/O2.html ,

and

http://sites.math.rutgers.edu/~zeilberg/tokhniot/PictOddArmin/O3.html .

Dynamical Programming

The obvious way would be to try and extend the above argument for counting all order ideals of P_{n+1,n+2}, using (CanonicalDecomposition).

Let (n − 1 − i, i) be the ‘first’ unoccupied vertex of the order ideal S of A_{n}, let (i, S_{1}, S_{2}) be its image under (CanonicalDecomposition). The smaller order ideals S_{1} (of A_{i−2}) and S_{2} (of A_{n−i}) also have the property, that within each diagonal, the colors of the occupied vertices alternate, but, alas, as you move from one diagonal to the next one, the “alternation” may (and often does) “break-down”. Also the two components in the “canonical decomposition” are not “independent” but must satisfy some compatibility conditions.

This forces us to consider much more general creatures, order ideals whose “colors” (parity) alternate within each individual diagonal, and having, in addition, a given “coloring profile”, the list of pairs of colors of the first and last vertices in each diagonal, reading from left to right. For example, the profile of the order ideal in

http://sites.math.rutgers.edu/~zeilberg/tokhniot/PictOddArmin/O2.html

is [[1, 1], [0, 0], [1, 0]], since it is supported in the three outermost diagonals and the occupied vertices on rightmost diagonal start with 3 (odd parity, hence 1), and end with 9 (hence the first component of the profile is [1, 1]). The lowest occupied vertex on the second diagonal has label 14 (hence 0) and the last one has label 18 (hence 0), hence for the second diagonal, we have [0, 0]. Finally, the lowest label on the third diagonal is 25 and the highest is 26, hence [1, 0]. Note that for any profile of an order ideal corresponding to an (n + 1, n + 2)-core partition

[[a_{1}, b_{1}], [a_{2}, b_{2}], …, [a_{k}, b_{k}]] ,

b_{i} and a_{i+1} must have opposite parities. Also, a_{1} = 1. We call such profiles good profiles. Hence there are 2^{k−1} good profiles. Unfortunately, in order to use dynamical programming, we need to consider all 2^{2k} profiles for k diagonals (and it is easy to see that for us, k ≤ n/2). Hence our algorithm is exponential time (and memory).

We essentially use (CanonicalDecomposition) but refined to order ideals with a given profile, and at the end we sum over all good profiles.

The details are straightforward but rather tedious, and may be gotten from looking at the source code of the Maple package OddArmin.txt, available from

http://www.math.rutgers.edu/~zeilberg/tokhniot/OddArmin.txt .

See procedure NuOIG(n,c) giving e_{n}^{(c)} for c = 0 and c = 1. It is obtained by adding up the outputs of procedure NuOIP(n,c,P) where P is the ‘profile’, and adding up all the outputs from the set of ‘good profiles’.

Procedure NuOIP(n,c,P) is a refined version of (CanonicalDecomposition). The problem is the proliferation of profiles. For each “good” order ideal with given profile P, for which (n − 1 − i, i) is the ‘first’ unoccupied vertex, the two smaller order ideals, of A_{i−2} and A_{n−i}, have implied profiles. The program finds all such pairs (P1,P2) and adds up

NuOIP(i-2,c,P1)*NuOIP(n-i,c,P2) ,

for all such pairs.

The output was as follows.

• The first 23 terms of the sequence e_{n}^{(0)} (staring with n = 0) are

2, 4, 7, 17, 30, 80, 143, 404, 728, 2140, 3876, 11729, 21318, 65952, 120175,
378321, 690690, 2205168, 4032015, 13023324, 23841480, 77761008, 142498692 .

• The first 23 terms of the sequence e_{n}^{(1)} (staring with n = 0) are

2, 3, 7, 12, 31, 55, 152, 273, 790, 1428, 4271, 7752, 23767, 43263, 135221, 46675, 782968,

1430715, 4598804, 8414640, 27332956, 50067108, 164081764

But, we really don’t care about e_{n}^{(0)} when n is odd, or e_{n}^{(1)} when n is even. We want the Straub sequence e_{n}^{(n mod 2)}. In other words, we extract the even-indexed terms of the former sequence and the odd-indexed terms of the latter sequence, and then we interleave them. This yields the first 23 terms of the Straub sequence:

1, 2, 4, 7, 17, 31, 80, 152, 404, 790, 2140, 4271, 11729, 23767, 65952, 135221,
378321, 782968, 2205168, 4598804, 13023324, 27332956, 77761008 .

This sequence is not (yet) in the OEIS (but hopefully it will be very soon). But what about the “rejected” terms, the ones that we do not care about? Maybe we should care about them!

The first 23 terms of the sequence e_{n}^{(n+1 mod 2)} are

1, 2, 3, 7, 12, 30, 55, 143, 273, 728, 1428, 3876, 7752, 21318, 43263, 120175,

246675, 690690, 1430715, 4032015, 8414640, 23841480, 50067108 .

To our utter surprise (and delight), this sequence is in the OEIS, (but for entirely different reasons!). It is sequence A047749 and has a very nice closed-form expression: If n = 2m, then \frac{1}{2m+1} · \binom{3m}{m}, while if n = 2m + 1, then \frac{1}{2m+1} · \binom{3m+1}{m+1}. As mentioned in the OEIS entry, it is easily verified that its generating function, Y = Y (x), satisfies the simple cubic equation

x Y^{3} − 2 Y^{2} + 3 Y − 1 = 0 .

We are almost sure that the generating function of the Straub sequence s_{n} = e_{n}^{(n mod 2)} also satisfies an algebraic equation, but the above 23 terms did not allow us to guess one.

As we mentioned in the abstract, we would gladly donate one hundred dollars to the OEIS, in honor of the first person to generate enough terms that would enable the discovery of such an algebraic equation (with a few terms to spare, yielding a non-rigorous proof), and an additional one hundred dollars (either in honor of the same or different person(s) and/or machines), for a rigorous proof.

Enumerating Restricted Families of Core Partitions

Finally, we shall discuss some bonus families of partitions related to Straub’s paper. In these cases, we were able to use symbolic computation to rigorously derive rational generating functions.

(n + 1, n + 2)-core partitions with at most k repeats of a part

As noted, the sequence of numbers enumerating (n + 1, n + 2)-core partitions with distinct parts is \{F_{n+2}\}_{n=0}^{∞}, whose generating function is the very simple rational function \frac{1+x}{1−x−x^{2}} . We shall now show that it is not hard to derive such rational generating functions to enumerate (n+1, n+2)-core partitions where each part gets repeated at most k times, for any, given, specific (i.e. numeric, not symbolic) k, where the former case corresponds to k = 1.

Again, consider the poset A_{n} := P_{n+1,n+2}, whose order ideals correspond to (n + 1, n + 2)-core partitions. Suppose S is an order ideal of A_{n} corresponding to a partition in which each part appears at most k times. This is equivalent to saying S contains at most k consecutive labels. (Note that, because S is an order ideal, a necessary condition for this is that the elements of S reside in the k outermost diagonals of A_{n}.)

As before, let (n − 1 − i, i) be the smallest-labeled unoccupied point in the outermost diagonal of S, so that S contains the labels 1, …, i but not i + 1. Due to our new restriction, i ≤ k. Again, let S_{1} contain the elements of S below (n − 1 − i, i) and not on the outer diagonal; let S_{2} contain elements above (n − 1 − i, i). Then S_{1} is isomorphic to an arbitrary order ideal of A_{i−2}, and S_{2} is isomorphic to an order ideal of A_{n−i} with no k consecutive labels.

So, with k fixed, we can see S as the “concatenation” of two types of order ideals—one with a filled-in base of size ≤ k, and another of the same type as S. The generating function enumerating the first type of order ideals is a finite polynomial: its coefficients are Catalan numbers. So we obtain an algebraic equation satisfied by the desired generating function that can easily be solved in Maple. See the procedure Fk in the Maple package. Here are the generating functions for 2 ≤ k ≤ 4: k = 2:

−\frac{2 x^{2} + x + 1}{2 x^{3} + x^{2} + x − 1} ,

whose first few coefficients are 1, 2, 5, 9, 18, 37, 73, 146, 293, 585, 1170, 2341, 4681, 9362, 18725, 37449, …, ;

k = 3:

−\frac{5 x^{3} + 2 x^{2} + x + 1}{5 x^{4} + 2 x^{3} + x^{2} + x − 1} ,

whose first few coefficients are 1, 2, 5, 14, 28, 62, 143, 331, 738, 1665, 3780, 8576, 19376, 43837, 99265, 224734, …;

k = 4:

−\frac{14 x^{4} + 5 x^{3} + 2 x^{2} + x + 1}{14 x^{5} + 5 x^{4} + 2 x^{3} + x^{2} + x − 1} ,

whose first few coefficients are

1, 2, 5, 14, 42, 90, 213, 527, 1326, 3317, 8022, 19608, 48272, 119073, 293109,

719074, 1766201, 4342666, 10679582, 26253546, 64516501, 158569355, 389788182 ….

For the generating functions, and first few terms, for the cases 5 ≤ k ≤ 20, see the webpage

http://sites.math.rutgers.edu/~zeilberg/tokhniot/oOddArmin3.txt .

(n + 1, n + 2)-core partitions into odd parts, whose corresponding order ideals are confined to the k outermost diagonals Inspired by the necessary condition mentioned above, let us enumerate (n+1, n+2)-core partitions into odd parts whose order ideals are restricted to the outer k diagonals. As before, we classify S according to its profile P, a list of pairs, each pair giving the parities of the largest and smallest labels of S in a certain diagonal. Also, define i(S) to be the smallest j such that (j, 0) is occupied.

Call (P (S), i(S)) the “type” of S; for fixed k, there are finitely many types. Further, any S of a certain type is the concatenation of its elements on the x-axis with some smaller order ideal of A_{n−1} having a compatible type. Thus, the generating function of order ideals having a certain type satisfies some algebraic equation involving the generating functions of its “child” types. Once we solve this system and sum the generating functions over P, we get what we are after. See Gk in the Maple package.

For k = 2 the generating function is

−\frac{x^{4} − x^{3} − x^{2} + x + 1}{x^{5} − x^{4} − 2 x^{3} + 3 x^{2} + x − 1} ,

whose first few coefficients are

1, 2, 4, 7, 15, 27, 56, 104, 210, 398, 791, 1517, 2988, 5769, 11306, 21911,
42820, 83160, 162261, 315496, 615050, 1196676, 2331733, 4538426, 8840719 .

For k = 3 the generating function is

−\frac{x^{9} + x^{8} − 4 x^{7} − 6 x^{6} + 8 x^{5} + 9 x^{4} − 5 x^{3} − 5 x^{2} + x + 1}{(x^{9} + 2 x^{8} − 3 x^{7} − 9 x^{6} + 3 x^{5} + 14 x^{4} − x^{3} − 7 x^{2} + 1) (x − 1)} ,

whose first few coefficients are

1, 2, 4, 7, 17, 31, 76, 144, 344, 670, 1560, 3103, 7079, 14315, 32152, 65861,
146183, 302456, 665300, 1387172, 3030464, 6356068, 13813464, 29103412, 62999146 ….

For generating functions, and first few terms, for the cases 4 ≤ k ≤ 5, see the webpage

http://sites.math.rutgers.edu/~zeilberg/tokhniot/oOddArmin2.txt .

References

[Am] Tewodros Amdeberhan, Theorems, problems and conjectures,

https://arxiv.org/abs/1207.4045 .

[AmL] Tewodros Amdeberhan and Emily Sergel Leven , Multi-cores, posets, and lattice paths, https://arxiv.org/abs/1406.2250. Also published in Adv. Appl. Math. 71(2015), 1-13.

[An] Jaclyn Anderson, Partitions which are simultaneously t_{1} and t_{2} -core, Discrete Math. 248(2002), 237-243.

[AHJ] Drew Armstrong, Christopher R.H. Hanusa, and B. Jones, Results and conjectures on simultaneous core partitions, https://arxiv.org/abs/1308.0572 . Also published in European J. Combin. 41 (2014), 205-220.

[J] Paul Johnson, Simultaneous cores with restrictions and a question of Zaleski and Zeilberger,

https://arxiv.org/abs/1802.09621 .

[S1] Armin Straub, Core partitions into distinct parts and an analog of Euler’s theorem, https://arxiv.org/abs/1601.07161. Also published in: European J. of Combinatorics 57 (2016), 40-49.

[S2] Armin Straub, Core partitions into distinct parts and an analog of Euler’s theorem (JMM),

(talk), http://arminstraub.com/talk/corepartitions-jmm .

[YQJZ] Sherry H.F. Yan, Guizhi Qin, Zemin Jin, Robin D.P. Zhou, On (2k+1, 2k+3)-core partitions

with distinct parts, https://arxiv.org/abs/1604.03729 .

[Za] Anthony Zaleski, Explicit expressions for the moments of the size of an (s, s + 1)-core partition with distinct parts, https://arxiv.org/abs/1608.02262. Also appeared in Advances in Applied Mathematics Vol 84 (2017), 1-7.

[ZZ] Anthony Zaleski and Doron Zeilberger, Explicit (Polynomial!) Expressions for the Expectation, Variance and Higher Moments of the Size of of a (2n+1,2n+3)-core partition with Distinct

parts , https://arxiv.org/abs/1611.05775 and
http://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/armin.html . Also ap-

peared in J. Difference Equations and Applications Volume 23(2017), 1241-1254,

Anthony Zaleski, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: az202 at math dot rutgers dot edu .

Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: DoronZeil at gmail dot com .

Exclusively Published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger and arxiv.org .

First version: Dec. 26, 2017; Previous version: Jan. 24, 2018; This version: Feb. 28, 2018.