Ludovic Schwob - cp's OEIS frontend

A384631 Number of self-inverse double cosets in D_n\S_n/D_n.

1, 2, 4, 8, 17, 52, 153, 482, 1623, 5879, 21926, 85436, 344998, 1444437, 6230232, 27704051, 126571091, 593974930, 2856031804, 14065575098, 70822693101, 364420818168, 1913609207886, 10249715874962, 55938458263035, 310915671908063, 1758452185453926, 10115287840489764

Offset: 3

Ludovic Schwob, Jun 05 2025

nonn

D_n is the dihedral group of order 2*n, seen as a subgroup of the symmetric group S_n.

Cosets in S_n/D_n are in bijection with polygons obtained by connecting cyclically n equally spaced points on a circle. Double cosets in D_n\S_n/D_n are in bijection with polygons up to rotation and reflection.

Ludovic Schwob, On the enumeration of double cosets and self-inverse double cosets, arXiv:2506.04007 [math.CO], 2025. See Proposition 4.2 p.9.

Cf. A001710 (polygons), A000940 (polygons up to rotation and reflection), A384630 (self-inverse cycles).

# From Proposition 4.2 in the reference:
from sympy import divisors, factorial, totient
def A384631(n):
    s = 0
    if n%2==0:
        for d in divisors(n//2):
            if d%2==0:
                s += totient(d)*factorial(n//d)*(d//2)**(n//2//d)//factorial(n//2//d)
            else:
                s += totient(d)*sum(factorial(n//d)*d**i//2**i//factorial(i)//factorial(n//d-2*i) for i in range(n//2//d+1))
        s += n//2*((n%4)//2+1)*factorial(2*(n//4))//factorial(n//4)
    else:
        for d in divisors(n):
            s += totient(d)*sum(factorial(n//d)*d**i//2**i//factorial(i)//factorial(n//d-2*i) for i in range(n//d//2+1))
        if n%4==1:
            s += n*factorial(n//2)//factorial(n//4)
    return s//n//2

A384630 Number of self-inverse double cosets in Z_n\S_n/Z_n.

Original entry on oeis.org

1, 1, 2, 3, 6, 14, 34, 98, 294, 952, 3246, 11698, 43732, 170752, 689996, 2888034, 12458784, 55406422, 253142182, 1187934740, 5712033368, 28131119956, 141645386202, 728841303696, 3827217750492, 20499431084644, 111876916526070, 621831335167486, 3516904353610572

Offset: 1

Ludovic Schwob, Jun 05 2025

nonn

Z_n is the cyclic group of order n, seen as a subgroup of the symmetric group S_n.

Cosets in S_n/Z_n are in bijection with cycles obtained by connecting cyclically n equally spaced points on a circle. Double cosets in Z_n\S_n/Z_n are in bijection with cycles up to rotation.

Ludovic Schwob, On the enumeration of double cosets and self-inverse double cosets, arXiv:2506.04007 [math.CO], 2025. See Proposition 4.1 p. 9.

Cf. A000142 (cycles), A002619 (cycles up to rotation), A384631 (self-inverse polygons).

# From Proposition 4.1 in the reference:
from sympy import factorial,divisors,totient
def A384630(n):
    s = 0
    if n%2==0:
        for d in divisors(n//2):
            if d%2==0:
                s += totient(d)*(d//2)**(n//2//d)*factorial(n//d)//factorial(n//2//d)
            else:
                s += totient(d)*sum(factorial(n//d)*d**i//2**i//factorial(i)//factorial(n//d-2*i) for i in range(n//2//d+1))
    else:
        for d in divisors(n):
            s += totient(d)*sum(factorial(n//d)*d**i//2**i//factorial(i)//factorial(n//d-2*i) for i in range(n//d//2+1))
    return s//n

A383895 Number of spiny partitions with exactly n parts.

Original entry on oeis.org

1, 1, 2, 4, 9, 20, 47, 111, 267, 646, 1582, 3892, 9636, 23961, 59871, 150128, 377738, 953029, 2410626, 6111055, 15524013, 39508683, 100719223, 257150952, 657454544, 1683042629, 4313582090, 11067748352, 28426813910, 73082880708, 188059428289, 484330230117, 1248338233493

Offset: 0

Ludovic Schwob, May 14 2025

nonn

An integer partition is said to be spiny if for all parts k having multiplicity m the number of parts <= k is >= m*k.

Arborescent partitions (cf. A383894) are spiny partitions.

			The 20 spiny partitions corresponding to a(5) = 20 are:
  (11111),  (21111),  (22111),  (31111),  (32111),
  (32211),  (41111),  (42111),  (42211),  (43111),
  (43211),  (51111),  (52111),  (52211),  (53111),
  (53211),  (54111),  (54211),  (54311),  (54321).
The partition (42221) is not spiny because the part 2 has multiplicity 3 but the number of parts <=2 is 4 < 3*2.
The only spiny partition of length 5 which does not correspond to an arborescent partition is (42211), i.e. there is no tree whose multiset of subtree sizes is {6, 4, 2, 2, 1, 1} (cf. A383894).

Alois P. Heinz, Table of n, a(n) for n = 0..200

Cf. A382440, A383894.

def A383895(n): #generator of terms a(0) to a(n)
    L = [[1]]
    for k in range(1,n+2):
        l = [0]
        for i in range(1,k+1):
            l.append(sum(L[a][b] for a in range(k-(k//i),k) for b in range(i)))
        L.append(l)
        yield l[-1]

A384133 Triangle read by rows: T(n,k) is the number of linear intervals of height k in the Tamari lattice Tam_n (0 <= k < n).

Original entry on oeis.org

1, 2, 1, 5, 5, 2, 14, 21, 12, 2, 42, 84, 56, 14, 2, 132, 330, 240, 72, 16, 2, 429, 1287, 990, 330, 90, 18, 2, 1430, 5005, 4004, 1430, 440, 110, 20, 2, 4862, 19448, 16016, 6006, 2002, 572, 132, 22, 2, 16796, 75582, 63648, 24752, 8736, 2730, 728, 156, 24, 2

Offset: 1

Ludovic Schwob, May 20 2025

An interval is linear of height k if it is isomorphic to the total order on k+1 elements.

			Triangle begins:
   1;
   2,    1;
   5,    5,    2;
  14,   21,   12,    2;
  42,   84,   56,   14,    2;
 132,  330,  240,   72,   16,    2;
 ...

Clément Chenevière, Linear Intervals in the Tamari and the Dyck Lattices and in the alt-Tamari Posets, arXiv:2209.00418 [math.CO], 2022.

Cf. A000108, A000260, A344136.

T[n_,k_]:=If[k==0, Binomial[2*n,n]/(n+1), If[k==1, Binomial[2*n-1,n-2], 2*Binomial[2*n-k,n-k-1]]]; Table[T[n,k],{n,10},{k,0,n-1}]//Flatten (* Stefano Spezia, May 26 2025 *)

Row sums give A344136.

T(n,0) = C(2*n,n)/(n+1), T(n,1) = C(2*n-1,n-2) and T(n,k) = 2*C(2*n-k,n-k-1) if k>1.

A383894 Number of arborescent partitions with exactly n parts.

Original entry on oeis.org

1, 1, 2, 4, 9, 19, 44, 96, 220, 489, 1115, 2483, 5646, 12571, 28343, 63152, 141621, 314330, 701327, 1552149, 3445128, 7599990, 16789039, 36908077

Offset: 1

Ludovic Schwob, May 14 2025

Equivalently, multisets of subtree sizes of rooted trees with n nodes.
The multiset of subtree sizes of a rooted tree T is the multiset containing the number of nodes of the subtrees rooted at each node of T. Integer partitions obtained this way are called arborescent partitions.
All arborescent partitions are spiny partitions (cf. A383895).

			The following rooted tree has its multiset of subtree sizes equal to {8, 7, 3, 2, 1, 1, 1, 1}:
              o
              |
              o
             /|\
            / | \
           o  o  o
          / \    |
         o   o   o
The 9 arborescent partitions corresponding to a(5) = 9 are:
  (51111),   (52111),   (52211),
  (53111),   (53211),   (54111),
  (54211),   (54311),   (54321).
The following two non-isomorphic trees have the same multiset of subtree sizes, which is {6, 3, 2, 1, 1, 1}:
           o                 o
          / \               /|\
         o   o             o o o
        / \   \            |
       o   o   o           o
                           |
                           o

Sean A. Irvine, Java program (github)

Cf. A000081 (number of rooted trees), A382440 (subtree sizes of binary trees), A383895 (spiny partitions).

a(18)-a(24) from Sean A. Irvine, May 25 2025

A383370 Number of partial orders on {1,2,...,n} that are contained in the usual linear order, whose dual is given by the relabelling k -> n+1-k.

Original entry on oeis.org

1, 1, 2, 3, 12, 25, 172, 482, 5318, 19675, 333768, 1609846, 40832554, 254370640, 9459449890, 75546875426, 4061670272088

Offset: 0

Ludovic Schwob, Apr 24 2025

a(n) is the number of n X n upper triangular Boolean matrices B with all diagonal entries 1 such that B = B^2, which are symmetric about the antidiagonal. These matrices can be seen as closed sets of inversions (pairs (i,j) with 1 <= i < j <= n). A set of inversions E is closed if for all i < j < k, if E contains (i,j) and (j,k) then it contains (i,k).

			The Boolean matrices corresponding to a(4) = 12:
  1 0 0 0    1 0 0 1    1 0 0 0    1 0 0 1
  0 1 0 0    0 1 0 0    0 1 1 0    0 1 1 0
  0 0 1 0    0 0 1 0    0 0 1 0    0 0 1 0
  0 0 0 1    0 0 0 1    0 0 0 1    0 0 0 1
.
  1 0 1 0    1 0 1 1    1 0 1 0    1 0 1 1
  0 1 0 1    0 1 0 1    0 1 1 1    0 1 1 1
  0 0 1 0    0 0 1 0    0 0 1 0    0 0 1 0
  0 0 0 1    0 0 0 1    0 0 0 1    0 0 0 1
.
  1 1 0 0    1 1 0 1    1 1 1 1    1 1 1 1
  0 1 0 0    0 1 0 0    0 1 0 1    0 1 1 1
  0 0 1 1    0 0 1 1    0 0 1 1    0 0 1 1
  0 0 0 1    0 0 0 1    0 0 0 1    0 0 0 1

Cf. A006455, A037223.

def a(n):
    S = set()
    for P in Posets(n):
        if P.is_isomorphic(P.dual()):
            for l in P.linear_extensions():
                t = tuple(tuple(int(P.is_lequal(l[j],l[i])) for j in range(i)) for i in range(1,len(l)))
                if all(t[j][i]==t[n-i-2][n-j-2] for i in range((n-1)//2) for j in range(i,n-i-2)):
                    S.add(t)
    return len(S)

a(10)-a(16) from Christian Sievers, May 02 2025

A383372 Number of centrally symmetric Baxter permutations of length n.

Original entry on oeis.org

1, 1, 2, 2, 6, 8, 26, 38, 130, 202, 712, 1152, 4144, 6904, 25202, 42926, 158442, 274586, 1022348, 1796636, 6736180, 11974360, 45154320, 81040720, 307069360, 555620080, 2113890560, 3851817920, 14705955008, 26960013552, 103245460226

Offset: 0

Ludovic Schwob, Apr 24 2025

nonn

For all n > 0, a(n) is the number of triples of non-intersecting lattice paths of length n-1.

a(n) is the number of symmetric twin pairs of full binary trees with n internal nodes.

			The Baxter permutations corresponding to a(4) = 6 are 1234, 1324, 2143, 3412, 4231, and 4321.

Stefan Felsner, Eric Fusy, Marc Noy, and David Orden, Bijections for Baxter families and related objects, J. Combin. Theory Ser. A, 118(3):993-1020, 2011.
Kevin Dilks, Involutions on Baxter Objects, arXiv:1402.2961 [math.CO], 2014.

Cf. A001181.

For all n>0, a(n) = Sum_{k=0...n-1} Theta_{k,n-k-1}, where Theta_{k,l} is equal to:
  - C(a+b+1,a+1)*C(a+b+1,a)*C(a+b,a)/(a+b+1) if k and l are even with k = 2*a and l = 2*b;
  - C(a+b+1,a+1)^2*C(a+b+1,a)/(a+b+1) if k is odd and l is even with k = 2*a+1 and l = 2*b;
  - Theta(l,k) if k is even and l is odd;
  - 0 if k and l are odd.

A382829 Number of distinct rank vectors of distributive lattices of height n.

Original entry on oeis.org

1, 1, 2, 5, 15, 51, 197, 864, 4325, 24922

Offset: 0

Ludovic Schwob, Apr 06 2025

Distributive lattices are ranked posets, and we define the rank vector of a ranked poset P as the vector whose k-th coordinate (starting at k = 0) is the number of elements of rank k in P.

By Birkhoff's representation theorem, elements of a finite distributive lattice L are in bijection with lower sets of the poset of join-irreducible elements of L, an element of rank k corresponding to a lower of set size k.

			The rank vectors corresponding to a(4) = 15 are:
  (1, 1, 1, 1, 1),   (1, 1, 1, 2, 1),   (1, 1, 2, 1, 1),
  (1, 1, 2, 2, 1),   (1, 1, 3, 3, 1),   (1, 2, 1, 1, 1),
  (1, 2, 1, 2, 1),   (1, 2, 2, 1, 1),   (1, 2, 2, 2, 1),
  (1, 2, 3, 2, 1),   (1, 2, 3, 3, 1),   (1, 3, 3, 1, 1),
  (1, 3, 3, 2, 1),   (1, 3, 4, 3, 1),   (1, 4, 6, 4, 1).
Two non-isomorphic distributive lattices have for rank vector (1, 2, 2, 2, 1).

Cf. A000112, A006982.

A382507 Number of half turn symmetric lattice congruences of the weak order on the symmetric group S_n.

Original entry on oeis.org

1, 2, 3, 16, 66, 13726, 11547029

Offset: 1

Ludovic Schwob, Mar 30 2025

For all permutations p of {1,2,...,n}, let C(p) be the permutation n+1-p(n),...,n+1-p(1). A lattice congruence of the weak order on S_n is said to be half turn symmetric if for all p ~ q we have C(p) ~ C(q).

Half turn symmetric lattice congruences of the weak order form a sublattice of the lattice of all congruences of the weak order, hence they form a distributive lattice.

			The lattice congruence of the weak order whose quotient is the lattice of Baxter permutations is half turn symmetric. Lattice congruences giving the Tamari lattice are not half turn symmetric.

Cf. A091687.

A382440 Number of rooted full binary trees with n internal nodes, up to their multiset of subtree sizes.

Original entry on oeis.org

1, 1, 2, 3, 6, 11, 23, 45, 95, 194, 414, 863, 1850, 3910, 8413, 17887, 38517, 82249, 177133, 378871, 815265, 1745006, 3750385, 8024725, 17219142, 36817113

Offset: 1

Ludovic Schwob, Mar 25 2025

The multiset of subtree sizes of a binary tree T is the multiset containing the number of internal nodes of the subtrees rooted at each internal node of T.

Isomorphic binary trees have the same multiset of subtree sizes. More precisely, binary trees giving rectangle tilings with the same shapes (cf. A247139) have the same multiset of subtree sizes.

			The following binary tree has its multiset of subtree sizes equal to {4, 3, 1, 1}:
            o
           / \
          o   \
         / \   \
        /   \   \
       /     \   \
      o       o   \
     / \     / \   \
    o   o   o   o   o
The 6 multisets of subtree sizes corresponding to a(5) = 6 are:
  {5, 3, 1, 1, 1},   {5, 2, 2, 1, 1},   {5, 3, 2, 1, 1},
  {5, 4, 2, 1, 1},   {5, 4, 3, 1, 1},   {5, 4, 3, 2, 1}.

Cf. A000108, A001190, A247139.

cp's OEIS Frontend

User: Ludovic Schwob

A384631 Number of self-inverse double cosets in D_n\S_n/D_n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

A384630 Number of self-inverse double cosets in Z_n\S_n/Z_n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

A383895 Number of spiny partitions with exactly n parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

A384133 Triangle read by rows: T(n,k) is the number of linear intervals of height k in the Tamari lattice Tam_n (0 <= k < n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A383894 Number of arborescent partitions with exactly n parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A383370 Number of partial orders on {1,2,...,n} that are contained in the usual linear order, whose dual is given by the relabelling k -> n+1-k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

SageMath

Extensions

A383372 Number of centrally symmetric Baxter permutations of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A382829 Number of distinct rank vectors of distributive lattices of height n.

Views

Author

Keywords

Comments

Examples

Crossrefs

A382507 Number of half turn symmetric lattice congruences of the weak order on the symmetric group S_n.

Views

Author

Keywords