User:Peter Luschny/Orbitals

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

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

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

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

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

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

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

${\displaystyle \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 ${\displaystyle 0}$.

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

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

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

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

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

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

${\displaystyle {\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 ${\displaystyle \Leftrightarrow }$ Orbitals

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

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

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

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

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

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

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

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

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

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

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

It is clear that this procedure generates a permutation ${\displaystyle p}$ of ${\displaystyle \{1,2,\ldots ,n\}}$. We have to show that this permutation is the lexicographic smallest in its equivalence class. So assume ${\displaystyle q}$ is a permutation which comes in the lex-order before ${\displaystyle p}$. We will show that ${\displaystyle q}$ has necessarily a different orbital than ${\displaystyle p}$. Let ${\displaystyle i}$ be the first index such that ${\displaystyle q_{i}<p_{i}}$ and assume that ${\displaystyle \omega _{q}i=\omega _{p}i}$. This means that by construction of ${\displaystyle p}$ the value ${\displaystyle q_{i}}$ appears in ${\displaystyle p}$ as ${\displaystyle p_{k}}$ for some ${\displaystyle k<i}$. Since ${\displaystyle q_{j}=p_{j}}$ for ${\displaystyle j<i}$ we now have two different indices ${\displaystyle i}$ and ${\displaystyle k}$ with ${\displaystyle q_{i}=q_{k}}$ which contradicts that ${\displaystyle q}$, being a permutation, is injective. ${\displaystyle \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 ${\displaystyle \omega }$ is Catalan if and only if all ${\displaystyle x}$ in the list of partial sums of ${\displaystyle \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 ${\displaystyle 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 ${\displaystyle n+1}$ sectors which start with a 0-step. Thus the zeros in A126120 just reflect the fact that for even ${\displaystyle n}$ there are no orbitals with a ${\displaystyle 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). ${\displaystyle v\leq w}$ are in weak order if and only if the inversion sets ${\displaystyle I_{v}}$ and ${\displaystyle I_{w}}$ satisfy ${\displaystyle I_{v}\subseteq I_{w}}$. ${\displaystyle 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 ${\displaystyle a\leq b}$ if and only if ${\displaystyle \pi (a)\leq \pi (b)}$ where ${\displaystyle \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 ${\displaystyle (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.

1. ↑ Peter Luschny, Divide, swing and conquer the factorial and the lcm{1,2,..,n}, preprint April 2008.
2. ↑ K. A. Penson and J.-M. Sixdeniers, Integral Representations of Catalan and Related Numbers. Journal of Integer Sequences, 4, 2001.
3. ↑ Peter Luschny, The lost Catalan numbers

---

Figure 2: ­ Orbitals over 6 sectors