User:Peter Luschny/Orbitals

O R B I T A L S

Introduction

A planar orbital system is a family of concentric circles in a plane divided into n sectors. An orbital is a closed path consisting of arcs on these circles such that at each boundary of a sector the path jumps to the next inner or outer circle. One exception is allowed: if n is odd the path may continue on the same circle, but just once (Geschlossenheitsbedingung).

After fixing one circle as the central circle there are three types of orbitals: a high orbital that never goes below the central circle, a low orbital that never goes above the central circle, and a swinging orbital that is neither a high nor a low orbital.

Figure 1: ­ Orbitals over 5 sectors

The diagram above shows all orbitals over 5 sectors. (At the bottom of this page the case of 6 sectors is shown. All plots are from a paper by the author given in the references.) .

Actually each orbital system shows two orbitals: the one drawn in green and its dual, in orange. In the diagrams, the kernel of an orbital system is white if the orbital is a high orbital and dark if it is a low orbital. Light gray signals a oscillating orbital which is neither a high orbital nor a low orbital. The number of high orbitals is the same as the number of low orbitals.

Why consider orbitals?

I will try to give some motivation.

Catalan numbers are inseparable from even numbered objects. They count:

• Balanced parenthesizing of strings of length 2n.
• Dyck paths of length 2n ending on the horizontal axis.
• Nonintersecting chording the vertices of a convex 2n-gon.

This commitment to 2n appears unfair to the odd numbers. Already Leibniz declared that it is the odd numbers that please God.

So let's ask the question: What combinatorial model could be advised which holds for all n and reduces in the case of an even n to the Catalan model?

The orbitals provide such a model.

A first argument in favor of this particular model comes from a simple statistic on orbital systems. Let T(n, k) be the number of orbitals over n sectors which rise to a maximum height k over the central circle. Then T(n, 0), the number of orbitals which never rise above the central circle are 1, 1, 1, 3, 2, 10, 5, 35, 14, 126, ... For even n these are indeed the Catalan numbers 1, 1, 2, 5, 14, ... And looking up the OEIS entry we find that these are also the "smallest number of crossing-free matchings on n points in the plane" which nicely extends Euler's "Betrachtungen, auf wie vielerley Arten ein gegebenes polygonum durch Diagonallinien in triangula zerschnitten werden könne" (1751).

Of course such combinatorial considerations must also be supported by analytical ones. My favorite one of this type is the extension of Penson's and Sixdeniers's integral representations of the Catalan numbers from the even case

$C_{2n}\ =\ {\frac {1}{2\pi }}{\int _{0}^{4}}x^{n}{\frac {\left(4-x\right)^{1/2}}{x^{1/2}}}dx$

to the odd case by just inverting the weight function

$C_{2n+1}\ =\ {\frac {1}{2\pi }}{\int _{0}^{4}}x^{n}{\frac {x^{1/2}}{\left(4-x\right)^{1/2}}}dx\ .$

More on this can be found in my May 2011 blog post The lost Catalan numbers. .

There are several interesting ways to encode orbitals, for example as rational numbers, but this is a topic which we will not discuss here. It is important to note that binary 01 sequences (which are appropriate for Catalan words) or +- charge sequences (which are appropriate for ballot sequences) are not appropriate to encode orbitals. Encoding of orbitals need three symbols, {-1, 0, 1} or {-, *, +} as a coding base. In a TeX environment $\scriptstyle \{{\hat {1}},\,0,\,1\}$ are convenient symbols.

     - - * + +    - - + * +    - * - + +    - - + + *    * - - + +
     - * + - +    - + - * +    * - + - +    - + * - +    - + - + *
     - * + + -    + - - * +    - + + - *    * - + + -    + - * - +
     - + * + -    * + - - +    + - - + *    - + + * -    + * - - +
     + - + - *    + - * + -    * + - + -    + - + * -    + * - + -
     * + + - -    + + - - *    + * + - -    + + - * -    + + * - -

                 Figure 1 ­ Orbitals over 5 sectors

     - - - + + +      - - + - + +     - - + + - +     - + - - + +
     - - + + + -      + - - - + +     - + - + - +     - + - + + -
     - + + - - +      + - - + - +     - + + - + -     + - - + + -
     + - + - - +      + - + - + -     - + + + - -     + + - - - +
     + - + + - -      + + - - + -     + + - + - -     + + + - - -

                 Figure 2 ­ Orbitals over 6 sectors
             

With SageMath unit orbitals over n sectors can be generated by the function below.

def Orbitals(n):
    sym_range = [i for i in range(-n+1, n, 2)]
    for c in Combinations(sym_range, n):
        P = Permutations([sgn(v) for v in c])
        for p in P: yield p

The Catalan decomposition of an orbital

Every orbital ω can be decomposed into list of orbitals [α, β, ..., γ] which are alternately entirely above or below the main circle ('above' and 'below' in the weak sense) and such that ω = α + β + ... + γ. Here '+' denotes the obvious concatenation operation of two orbitals $\omega \in {\mathcal {P}}_{n}$ and $\gamma \in {\mathcal {P}}_{k}$ leading to an orbital $\omega +\gamma \in {\mathcal {P}}_{n+k}$. To make the decomposition unique we set by convention that if a '0' is on the border of two orbitals it is allocated to the first one.

For instance ${\hat {1}}11{\hat {1}}1{\hat {1}}={\hat {1}}1+1{\hat {1}}1{\hat {1}}$ and ${\hat {1}}1{\hat {1}}101{\hat {1}}{\hat {1}}1={\hat {1}}1{\hat {1}}10+1{\hat {1}}+{\hat {1}}1.$

How many orbitals in ${\mathcal {P}}_{n}$ have a Catalan decomposition with k parts? The statistic starts:

[ n] [k=0,1,2,...] [row sum]
[ 0] [1] 1
[ 1] [0, 1] 1
[ 2] [0, 2] 2
[ 3] [0, 6] 6
[ 4] [0, 4, 2] 6
[ 5] [0, 20, 10] 30
[ 6] [0, 10, 8, 2] 20
[ 7] [0, 70, 56, 14] 140
[ 8] [0, 28, 28, 12, 2] 70
[ 9] [0, 252, 252, 108, 18] 630
[10] [0, 84, 96, 54, 16, 2] 252
[11] [0, 924, 1056, 594, 176, 22] 2772
[12] [0, 264, 330, 220, 88, 20, 2] 924
[13] [0, 3432, 4290, 2860, 1144, 260, 26] 12012
[14] [0, 858, 1144, 858, 416, 130, 24, 2] 3432

For example T(2n, n) = 2 counts the Catalan decompositions

[-1, 1]+[1, -1]+[-1, 1]+...+[(-1)^n, (-1)^(n+1)] and
[1, -1]+[-1, 1]+[1, -1]+...+[(-1)^(n+1), (-1)^n].

There are some interesting things to observe: The main diagonal is given by the elementary cellular automaton `Rule 59´, T(n, ⌊n / 2⌋) = A266722(n) for n > 1. The number of oscillating orbitals A232500(n) = n≀ - T(n,1) and T(n,1) = Sum_{k>=0} T(n+1,k) for odd n > 1. Here n≀ denotes the swinging factorial A056040. The statistic now is in A275325.

If we replace simultaneously ${\hat {1}}\rightleftarrows 1$ in an orbital ω then we call the resulting orbital the complement of ω and denote it by ω'. For example $({\hat {1}}011{\hat {1}})'=10{\hat {1}}{\hat {1}}1$.

Apart from T(0,0) and T(1,1) all T(n,k) are even due to the fact that with an orbital also the decomposition of its complement has k parts. To abstract from this effect we also entered the statistic S(n,k) = T(n,k) / 2 in A275326. It turns out that A128899 is a subtriangle of this triangle (even rows). See also the variant A039598 for the relation with the Chebychev U-polynomials.

Q-analogs

A standard statistic, the major index, appears in this section as the q-analog of the swinging factorial, the extended Catalan numbers and the oscillating orbitals.

The major index of an orbital is the sum of the positions of steps which are immediately followed by a step with strictly smaller value. The major index of the swinging factorial coincides with the q-analog of the swinging factorial; the same is true for the extended Catalan numbers and the oscillating orbitals.

But what are q-analogs? I cite form Peter Webb's A course in finite group representation theory.

"In combinatorics, an active topic is to obtain 'q-analogs' of enumerative results, exemplified by replacing binomial coefficients (which count subsets of a set) by q-binomial coefficients (which count subspaces of vector spaces over F_q). Structures permuted by a symmetric group are replaced by linear structures acted on by a general linear group, thereby giving representations in positive characteristic."

It's good to have this as a perspective; fortunately we do not need to understand it fully to define our sequences. The table below compiles some important q-analogs in the OEIS.

A000142 factorial	A274887 q-factorial
A007318 binomial	A275216 q-binomial
A000984 central binomial	A063746 q-central-binomial
A056040 swinging factorial	A274888 q-swinging factorial
A212303 binom1	A274885 q-binom1
A000108 Catalan	A129175 q-Catalan
A057977 extended Catalan	A274886 q-extended Catalan
A232500 oscillating orbitals	A275332 q-oscillating orbitals
A001263 Narayana	A275215 q-Narayana

SageMath implementation

Let's first look how the major index of orbitals, q-Catalan numbers, q-extended_Catalan numbers and oscillating orbitals can be counted. The function unit_orbitals is already defined above.

def orbitals_major_index_by_type(n, type):
    S = [0]*(((n+1)//2)^2 + ((n+1) % 2))
    for u in filter(type, unit_orbitals(n)):
        L = [i+1 if u[i+1] < u[i] else 0 for i in (0..n-2)]
        S[sum(L)] += 1
    while len(S) > 1 and S[-1] == 0: del S[-1]    
    return S 

The types are defined as

def is_orbital(u): return true
def is_catalan(u): return is_even(len(u)) and all(x ≤ 0 for x in accumulate(u)) 
def is_ext_catalan(u): return all(x ≤ 0 for x in accumulate(u)) 
def is_oscillating(u): return any(x > 0 for x in accumulate(u)) 
                          and any(x < 0 for x in accumulate(u))

We see that the only difference between the q-Catalan and q-extendedCatalan numbers is that the requirement that the obital has even length is dropped in the case of the extended Catalan numbers.

For example to compute the major index for the extended Catalan numbers we can write:

for n in(0..8): print orbitals_major_index_by_type(n, is_ext_catalan)

This approach to count the orbitals is of course only the low-level approach. Now lets base the functions on basic q-analogs like the q-binomial (also called Gaussian coefficient or Gaussian polynomial). For example the q-analog of the Catalan numbers can be computed as q-binomial(2*n, n) / q-binomial(n+1, 1).

from sage.combinat.q_analogues import q_binomial
def qCatalan(n): return (q_binomial(2*n, n)//q_binomial(n+1, 1)).list()

for n in (0..8):  
    print qCatalan(n)
    # print orbitals_major_index_by_type(2*n, is_catalan) # for comparison

The q-analog of the extended Catalan numbers is q-binom1(n) / q-binomial(n+1, 1) where q_binom1(n) plays the role of the central binomial q_binomial(2*n, n) in the standard case.

from sage.combinat.q_analogues import q_binomial
def qExtendedCatalan(n): return (q_binom1(n)//q-binomial(n+1, 1)).list()

for n in (0..8):  
    print qExtendedCatalan(n)
    # print orbitals_major_index_by_type(n, is_ext_catalan) # for comparison

The sequence of these polynomials starts:

1
1
1
q^2 + q + 1
q^2 + 1
(q^2 + 1)*(q^4 + q^3 + q^2 + q + 1)
(q^2 - q + 1)*(q^4 + q^3 + q^2 + q + 1)
(q^2 - q + 1)*(q^4 + q^3 + q^2 + q + 1)*(q^6 + q^5 + q^4 + q^3 + q^2 + q + 1).

The q-binom1(n) polynomials have, like their couterparts q-binomial(2*n, n) (given in A063746), a quite independent significance. They are defined in A274885 via q-factorials as:

from sage.combinat.q_analogues import q_factorial
def q_binom1(n): 
    return (q_factorial(n+1) // (q_factorial(n//2)*q_factorial((n+2)//2)))
    
for n in (0..5): print [n], q_binom1(n).list()

These are the first few polynomials:

[0] 1
[1] q + 1
[2] q^2 + q + 1
[3] (q + 1) * (q^2 + 1) * (q^2 + q + 1)
[4] (q^2 + 1) * (q^4 + q^3 + q^2 + q + 1)
[5] (q + 1)*(q^2 - q + 1)*(q^2 + 1)*(q^2 + q + 1)*(q^4 + q^3 + q^2 + q + 1).

The de-q'ed form of q_binom1 is described in A212303.

Q-swing

Last not least we look at the q_analogs of the swinging factorials, which generate the class of all orbitals. They are defined as

q-swing_factorial(n) = q-multinomial([floor(n/2), n mod 2, floor(n/2)]),

or equivalently as:

from sage.combinat.q_analogues import q_factorial
def q_swing_factorial(n, q=None):
    return q_factorial(n) // q_factorial(n//2)^2
    
for n in (0..8): print q_swing_factorial(n).list()

The first few polynomials are:

[0] 1
[1] 1
[2] q + 1
[3] (q + 1) * (q^2 + q + 1)
[4] (q^2 + 1) * (q^2 + q + 1)
[5] (q^2 + 1) * (q^2 + q + 1) * (q^4 + q^3 + q^2 + q + 1)
[6] (q + 1) * (q^2 - q + 1) * (q^2 + 1) * (q^4 + q^3 + q^2 + q + 1)

The swing polynomials have a product formula without any reference to q-functions:

def q_swing(n):
    q = var('q')
    a = mul((q^(n-i)-1)/(q^(i+1)-1) for i in (0..(n//2-1)))
    b = ((q^(n//2+1)-1)/(q-1))^((1-(-1)^n)/2)
    return (simplify(a*b).factor())

for n in (0..9): print q_swing(n)

The swing polynomials can also be computed recursively:

def q_swing_rec(n, q):
    if n == 0: return 1
    r = (1+q^(n//2))/q_int(n//2, q) if is_even(n) else q_int(n, q) 
    return r*q_swing_rec(n-1, q)

for n in (0..9): print q_swing_rec(n, q).factor()

It can be be easily seen that

     q_swing(n) = q_extended_catalan(n) * q_int(n//2 + 1).  

Note that some authors (and Maple) call the q-integers q_int the q-brackets.

Both the q-analog of the factorial and of the swinging factorial can also be computed via cyclotomic polynomials.

R, q = ZZ['q'].objgen()

def q_factorial(n):
    return mul(R.cyclotomic_polynomial(k)^(n//k) for k in (2..n))

def q_swing_factorial(n):
    return mul(R.cyclotomic_polynomial(k)^(n//k-2*(n//(2*k))) for k in (2..n))

From the last formula one can deduce that the q-swing_factorials have at least floor(n/2) irreducible factors. (The seq-fan might also notice that sum((n//k) for k in (2..n)) is A002541 and sum((n//k - 2*(n//(2*k))) for k in (2..n)) is A275495.)

Permutations and Orbitals

For $n\in \mathbb {N} =\{1,2,3,\ldots \}$ let $[n]=\{z\in \mathbb {Z} \mid 1\leq z\leq n\}$. The permutations of $[n]$ are defined as ${\mathcal {P}}_{n}=\{p:[n]\rightarrow [n]\mid p{\text{ bijective}}\}$. For $p\in {\mathcal {P}}_{n}$ let ${\tilde {p}}$ denote its complement which is defined as the permutation sending each $i$ to $n+1-p_{i}$. For permutations $p,q\in {\mathcal {P}}_{n}$ let $p-q$ denote the mapping $i$ to $p_{i}-q_{i}$.

For a permutation $p\in {\mathcal {P}}_{n}$ we define its orbital as

$\omega _{p}:\,i\mapsto \operatorname {sgn} (p-{\tilde {p}}){\text{ for }}i\in [n].$

The set of all orbitals over $n$ will be denoted by ${\mathcal {O}}_{n}$,

${\mathcal {O}}_{n}=\{\omega _{p}\ \mid \ p\in {\mathcal {P}}_{n}\}.$

Writing ${\hat {1}}$ for $\displaystyle -1$ we have for instance for ${\mathcal {P}}_{3}$:

$\quad 123\mapsto {\hat {1}}01,\qquad 231\mapsto 01{\hat {1}},\qquad 132\mapsto {\hat {1}}10,$

$\quad 312\mapsto 1{\hat {1}}0,\qquad 213\mapsto 0{\hat {1}}1,\qquad 321\mapsto 10{\hat {1}}.$

Theorem 1 The orbital of a permutation sums to $0$.

Proof: By the definition of an orbital for each $i\in [n]$ there is exactly one $j\in [n]$ such that $\displaystyle \omega _{i}=-\omega _{j}$. Therefore $\sum _{i}{\omega _{i}}=0{\text{ and }}\sum _{i}\operatorname {sgn} (\omega _{i})=0.$ $\diamond$

Different permutations can have the same orbital. Two permutations $p$ and $q$ are called orbital-equivalent if they have the same orbital,

$p\sim q\Leftrightarrow \omega _{p}=\omega _{q}.$

For instance the permutations $13452,\,13542,\,23451,\,23541$ all have the orbital ${\hat {1}}011{\hat {1}}.$ Counting the classes ${\mathcal {P}}_{n}\,/\sim$ and their cardinalities one finds:

Theorem 2 The permutations of $[n]$ under the orbital equivalence distribute into $n!/\lfloor n/2\rfloor !^{2}$ equivalence classes each of cardinality $\lfloor n/2\rfloor !^{2}$.

Proof: $p-{\tilde {p}}$ must have $\lfloor n/2\rfloor$ negative values and $\lfloor n/2\rfloor$ positive values; further the $0$ appears depending on the parity of $n$ $[n\ \operatorname {odd} ]$ times ($[b]$ is the Iverson bracket). This is described by a trinomial coefficient which is equal to the claimed formula.

${\binom {n}{\lfloor n/2\rfloor ,\left[n\ \operatorname {odd} \right],\lfloor n/2\rfloor }}={\frac {n!}{\lfloor n/2\rfloor !^{2}}}\quad \diamond$

Orbital permutations $\Leftrightarrow$ Orbitals

In each equivalence classes we fix the lexicographic smallest permutation as its representative. We denote by $\displaystyle [p]_{\sim }$ the equivalence classes of $p$ and by $\displaystyle [p]$ the representative of $p$. So we can write

$[p]={\min\{q\,\mid \,p\ \sim \ q\}},$

with min taken in ${\mathcal {P}}_{n}$ with respect to lex-order.

For example $\displaystyle [21345]_{\sim }=\{12345,12354,21345,21354\}$ and $[21345]=12345$.

The system of representatives of ${\mathcal {P}}_{n}\,/\sim$ will be denoted ${\tilde {\mathcal {P}}}_{n}$.

${\tilde {\mathcal {P}}}_{n}=\{[p]\mid p\in {\mathcal {P}}_{n}\}.$

We will call a $p\in {\tilde {\mathcal {P}}}_{n}$ an orbital permutation. For instance for $n=4$ we get:

${\tilde {\mathcal {P}}}_{4}=\{1234,\,1324,\,1342,\,3124,3142,\,3412\}.$

Theorem 3: The association $p\mapsto \operatorname {sgn} (p-{\tilde {p}})$ constitutes a bijection ${\tilde {\mathcal {P}}}_{n}\rightarrow {\mathcal {O}}_{n}$.

Proof: Injective: Since $p,q\in {\tilde {\mathcal {P}}}_{n}$ with $\displaystyle p\neq q$ are in different equivalence classes they have different orbitals.

Surjective: Given an orbital $\omega \in {\mathcal {O}}_{n}$ we can recover an orbital permutation $p\in {\tilde {\mathcal {P}}}_{n}$ by the following procedure: Set $n=1$. Scanning $\omega$ from left to right replace an occurrence of $-1$ by $n$, increase $n$ by one, and repeat until no $-1$ is in $\omega$. If there is an occurrence of $0$ replace it by $n$ and increase $n$ by one. Scanning $\omega$ from left to right replace an occurrence of $1$ by $n$, increase $n$ by one, and repeat until no $1$ is in $\omega$.

It is clear that this procedure generates a permutation $p$ of $\{1,2,\ldots ,n\}$. We have to show that this permutation is the lexicographic smallest in its equivalence class. So assume $q$ is a permutation which comes in the lex-order before $p$. We will show that $q$ has necessarily a different orbital than $p$. Let $i$ be the first index such that $q_{i}<p_{i}$ and assume that $\omega _{q}i=\omega _{p}i$. This means that by construction of $p$ the value $q_{i}$ appears in $p$ as $p_{k}$ for some $k<i$. Since $q_{j}=p_{j}$ for $j<i$ we now have two different indices $i$ and $k$ with $q_{i}=q_{k}$ which contradicts that $q$, being a permutation, is injective. $\diamond$

Orbital Catalan permutations

Using the bijection given in theorem 3 we can of course also restrict the orbitals under consideration to those which are Catalan (in our extended sense). An orbital $\omega$ is Catalan if and only if all $x$ in the list of partial sums of $\omega$ are ≤ 0.

This way we find the orbital Catalan permutations (counted by A057977). The first few are:

n = 3:  123, 132, 213.
n = 4:  1234, 1324.
n = 5:  12345, 12435, 12453, 13245, 13425, 
        14235, 14253, 14325, 31245, 31425.
n = 6:  123456, 124356, 124536, 142356, 142536. 

We may further restrict this subclass by considering only those orbitals which additionally begin with zero. In this case we get this list:

n = 0:
n = 1: 1.
n = 2: 
n = 3: 213.
n = 4:
n = 5: 31245, 31425.
n = 6:
n = 7: 4123567, 4125367, 4125637, 4152367, 4152637.
n = 8: 
n = 9: 512346789, 512364789, 512367489, 512367849, 512634789, 
       512637489, 512637849, 512673489, 512673849, 516234789, 
       516237489, 516237849, 516273489, 516273849.

Counting the permutations we find the sequence $0,1,0,1,0,2,0,5,0,14,\ldots$. Surprise, surprise, we get the Catalan numbers back, this time interspersed by zeros at even positions. This gives a nice combinatorial interpretation of A126120, which counts orbitals over $n+1$ sectors which start with a 0-step. Thus the zeros in A126120 just reflect the fact that for even $n$ there are no orbitals with a $0$-step.

SageMath functions for orbital/permutation conversion

def orb_to_perm(o):
    n = 1
    l = len(o)
    p = [0]*l
    for j in [-1, 0, 1]:
        for i in range(l):
            if o[i] == j: 
                p[i] = n
                n += 1
    return p

def is_orbital(p):
    q = p.complement()
    o = [sign(p[i] - q[i]) for i in range(len(p))]
    r = orb_to_perm(o)
    return p == r

[p for p in Permutations(6) if is_orbital(p)] 

def orbitals_to_permutations(n):
    for o in Orbitals(n): 
        p = orb_to_perm(o)
        print o, "→", p
        yield p

print list(orbitals_to_permutations(4))
            
list(orbitals_to_permutations(4))

def permutations_to_orbitals(n):
    for p in Permutations(n):
        q = p.complement()
        o = [sgn(p[i] - q[i]) for i in range(n)]
        r = orb_to_perm(o)
        if p == r:  # if is_orbital(p)
            print p, "→", o
            yield o
        
list(permutations_to_orbitals(4)) 

def orbital_catalan_permutations(n):
    for o in Orbitals(n):
        if is_ext_catalan(o): 
            yield orb_to_perm(o)
        
oc = orbital_catalan_permutations(5)
for p in oc: print p

The poset of orbitals

We give an example how to make use of the bijection between orbitals and orbital permutations. Permutations can be partially ordered by the right permutohedron order (aka weak order). $v\leq w$ are in weak order if and only if the inversion sets $I_{v}$ and $I_{w}$ satisfy $I_{v}\subseteq I_{w}$. $I_{w}=\{(w_{i},w_{j})\in [n]^{2}\,\colon \,i<j{\text{ and }}w_{i}>w_{j}\}$ (In somewhat antiquated German this is called "die Menge der Fehlstände der Vertauschungen", a concept which goes back to Gabriel Cramer's "Introduction à l′analyse des lignes courbes algébriques" from 1750.) In fact the set of permutations on n items is a lattice.

Now we transfer this order to the orbitals: For orbitals a, b we define $a\leq b$ if and only if $\pi (a)\leq \pi (b)$ where $\pi$ denotes the bijection in theorem 3. The plot below shows the poset of orbitals over six sectors defined by this order.

Poset of orbitals over six sectors

In some other symbolic form the various symmetries involved can be seen better, here in the poset of orbitals over five sectors:

Poset of orbitals over five sectors

Recall now the fact that the number of orbitals shown in these posets is counted by the swinging factorial. It is thus natural to ask whether the posets also reflect the p-swinging factorial. And indeed they do.

Let's call the rank of an orbital in the poset the length of the chain connecting the orbital with the minimal element. Then the number of orbitals with the same rank (the cardinality of a given rank level) are the coefficients of the polynomials representing the q-swinging factorial.

For instance in the above poset of orbitals over five sectors the rank levels have the cardinalities 1, 2, 4, 5, 6, 5, 4, 2, 1. And from the examples in A274888 we get for n=5 the polynomial $(q^{2}+1)*(q^{2}+q+1)*(q^{4}+q^{3}+q^{2}+q+1)$ which has coefficients [1, 2, 4, 5, 6, 5, 4, 2, 1].

We can summarize that the p-swinging factorials are the generating functions for the inversion statistic of orbitals. For a formal proof one might notice that this is a special case of a result of L. Carlitz in "Sequences and inversions", Duke Math. 1970.

Counting Orbitals

For concreteness we list the first five cases. Note the case n = 0 which counts the empty orbital which is Catalan (and hence is not oscillating).

n	0	1	2	3	4
All	Ø	*	~+   +~	~*+   ~+*   *~+   *+~   +~*   +*~	~~++   ~+~+   ~++~   +~~+   +~+~   ++~~
Catalan	Ø	*	~+	~*+   ~+*   *~+	~~++   ~+~+
Oscillating					~++~   +~~+

The generating functions of the various orbital classes are listed below. Let U(x) = (1-4*x^2)^(3/2) and Ik(x) = Bessel_I(k,2*x).

• All orbitals [A056040].

  [OGF] a(n) = [x^n] (x+1-4*x^2)/U(x).
  
  [EGF] a(n) = n! [x^n] (1+x)*I0(x). 
      
  [SEQ] 1, 1, 2, 6, 6, 30, 20, 140, 70, 630, ...
  

• Catalan orbitals [A057977].

  [OGF] a(n) = [x^n] ((1-x)-(1-4*x^2)*(1-4*x^2-x)/U(x))/(2*x^2).
  
  [EGF] a(n) = n! [x^n] (1+1/x)*I1(x).
      
  [SEQ] 1, 1, 1, 3, 2, 10, 5, 35, 14, 126, 42, ...
  

• Oscillating orbitals [A232500 for n≥2].

  [OGF] a(n) = [x^n] ((x^2+x^3+x-1)+(-7*x^2+5*x^3+12*x^4-x+1)/U(x))/x^2.
  
  [EGF] a(n) = n! [x^n] (1+x)*(1+I2(x))-(1+1/x)*I1(x).
      
  [SEQ] 0, 0, 0, 0, 2, 10, 10, 70, 42, 378, 168, ...
  

• Orbitals which are Catalan or oscillating [A237884 for n≥2].

  [OGF] a(n) = [x^n] ((2*x^3+2*x^2+x-1)+(8*x^4+6*x^3-6*x^2-x+1)/U(x))/(2*x^2).
  
  [EGF] a(n) = n! [x^n] (1+x)*(1+I2(x)).
      
  [SEQ] 1, 1, 1, 3, 4, 20, 15, 105, 56, 504, 210, ...
  

We better check this with Maple:

OrbitalSeries := proc(len, class, typ) local U;
if typ = 'egf' then
    if class = 'all' then 
       (1+x)*BesselI(0, 2*x) 
    elif class = 'cat' then
       (1+1/x)*BesselI(1, 2*x)  
    elif class = 'osc' then
       (1+x)*(1+BesselI(2, 2*x)) - (1+1/x)*BesselI(1, 2*x) 
    elif class = 'cat_or_osc' then
       (1+x)*(1 + BesselI(2, 2*x)) fi;
    series(%, x, len+4);
    return seq(n!*coeff(%, x, n), n=0..len);
fi;
if typ = 'ogf' then
    U := proc(x) (1-4*x^2)^(3/2) end:
    if class = 'all' then 
       (x+1-4*x^2)/U(x)
    elif class = 'cat' then
       ((1-x)-(1-4*x^2)*(1-4*x^2-x)/U(x))/(2*x^2) 
    elif class = 'osc' then
       ((x^2+x^3+x-1)+(-7*x^2+5*x^3+12*x^4-x+1)/U(x))/x^2 
    elif class = 'cat_or_osc' then
       ((2*x^3+2*x^2+x-1)+(8*x^4+6*x^3-6*x^2-x+1)/U(x))/(2*x^2) fi;
    series(%, x, len+4);
    return seq(coeff(%, x, n), n=0..len);
fi;
end:

for class in ['all', 'cat', 'osc', 'cat_or_osc'] do
    for typ in ['egf', 'ogf'] do
        print(OrbitalSeries(16, class, typ)) od od;

We can summarize as follows: The swinging factorial numbers A056040 count all orbitals over n sectors, the extended Catalan numbers A057977 count the low and the high orbitals. A232500 counts the oscillating orbitals over n sectors and A237884 the orbitals which are either Catalan or oscillating, in these cases with the exception of n = 0 and n = 1.

The bulk of orbitals are oscillating orbitals. ( ⌊n/2⌋ − 1 ) / ( ⌊n/2⌋ + 1 ) of the orbitals over n sectors are oscillating and only 1 / ( ⌊n/2⌋ + 1 ) are Catalan.

A simple asymptotic approximation to the number of orbitals over n sectors is 2^n*(n/2+1/4)^(-cos(Pi*n)/2)/sqrt(Pi). This approximation is actually quite good (the remainder is O(n^(-2)). Rounded to the nearest integer the formula computes the first eleven values exactly. From this formula we derive that asymptotically there are 2^N/((n+1)^m*sqrt(Pi*(2*N+1))) Catalan orbitals where m = (n+1) mod 2 and N = n + 1 + m. Rounded to the nearest integer this formula computes the first thirteen values exactly.

Statistics on orbitals

Some simple statistics on orbitals are given in the table below.

	Statistic	Sub- and super-Δ	Column 0
Catalan decomposition	A275325		A241543
Integral	A274706		A241810
Peak	A274708	A097692 (sub)	A025565 (even)
Height	A274709	A189231 (super)	A057977 A063549
Turn	A274710	A152659 (sub)
Span	A274878
Return	A274879	A108747 (sub)	A241543
Restart	A274880	A118920 (sub)
Ascent	A274881
Break	A275333	A063746 (sub)
First zero crossing	A241477		A126869

These statistics were generated by simple counting scripts given in their respective OEIS entry. The reader is invited to contribute closed form representations or recurrences.

Summary

Statistic	Permutations	Orbitals
Cardinality	card(Pn) = n!, factorial	card(On) = n≀, swinging-factorial
q-polynomial	F(n) = q-factorial of n	f(n) = q-swinging-factorial of n
Major index	M(n) = ∑σ ∈ Pn q^maj(σ)	m(n) = ∑ω ∈ On q^maj(ω)
Inversion index	I(n) = ∑σ ∈ Pn q^inv(σ)	i(n) = ∑ω ∈ On q^inv(ω)
Theorem	F(n) = M(n) = I(n)	f(n) = m(n) = i(n)

The theorem F(n) = M(n) = I(n) sketched in the table above is the fundamental example for permutation statistics and q-analogs and a major result of classical combinatorics due to O. Rodrigues (Jour. de Mathématiques 4 (1839), 236-240) and P. A. MacMahon (Amer. J. Math. 35 (1913), no. 3, 281-322).

The orbital model extends the classical Catalan model to the case of odd n. The acceptance depends to a certain extent on whether one considers the Geschlossenheitsbedingung, the condition that an orbital is a closed curve with a minimum number of exceptions in the jump condition as a natural one. Conversely, looking from the orbital point of view, an extended-Catalan orbital is simply defined by all(j ≤ 0 for j in accumulate(o)) (in Python parlance, see the full functions above) whereas the classical Catalan orbital is an extended-Catalan orbital which length is even; this additional constraint appears here as arbitrary and artificial.

At least three arguments suggest accepting the orbital model as a natural extension of the Catalan model:

• Classical combinatorial objects like Dyck paths ending on the horizontal line or crossing-free chording of points in the plane find their extensions.
• Analytic representations of the Catalan numbers like the Penson/Sixdeniers integral find a satisfactory corollary.
• The relationship between central binomial coefficients and the Catalan numbers is preserved and extended in the relationship between the swinging factorials and the extended Catalan numbers.

A more pragmatic consideration is: Why develop a theory which is only half of the cake when you can get the whole cake for a small amount of additional effort?

There is a famous list describing more than 200 objects which are counted by the Catalan numbers; there is nothing comparable for their odd counterparts though it would be certainly nice to know more about them. Or about objects which cover both the even and the odd case, like the orbitals.

A dictionary

The table below compares the enumeration of the classical objects with the enumeration of the extended objects.

Objects \ Type	classical	extended
All	central binomial A000984	swinging factorial A056040
Catalan	A000108	A057977
Oscillating	A000984 − 2*A000108 = A276666	A056040 − 2*A057977 = A232500
Catalan or oscillating	A000984 − A000108 = A001791	A056040 − A057977 = A237884

We talk here about objects, not orbitals. The reason is that orbitals constitute only one class of combinatorial objects which are counted this way. In the next blog post we will translate the language of the orbitals into the language of the trees.

References

A good place to start the study of the Catalan numbers: Igor Pak, Catalan Numbers Page.

---

Figure 2: ­ Orbitals over 6 sectors