A396770 Number of unlabeled connected nonnegative partially ordered sets ("posets") of size n and Dynkin type A.

1, 1, 3, 5, 11, 21, 42, 81, 161, 312, 616, 1209, 2389, 4711, 9344, 18497, 36743, 72955, 145116, 288633, 574729, 1144449, 2280526, 4544941, 9061735, 18069964, 36044048, 71906735, 143482301, 286339916, 571524114, 1140868089, 2277666987, 4547647110, 9080853526

Offset

1,3

Comments

a(n) is the number of distinct isomorphism classes of connected nonnegative posets of size n and Dynkin type A.

A poset I of size n is nonnegative if its symmetric Gram matrix G_I = (C_I + C_I^T)/2 is positive semidefinite, where C_I is the n X n relation matrix of the poset (with entries c_ij = 1 if i <= j, and 0 otherwise). Every such poset has a unique Dynkin type, defined as the simply-laced Dynkin diagram associated with the Z-congruence class of G_I (Simson, 2013).

For proof, see Gąsiorek (2022).

References

D. Simson, A Coxeter-Gram classification of positive simply laced edge-bipartite graphs, SIAM Journal on Discrete Mathematics, 27 (2013), 827-854.

Links

Table of n, a(n) for n=1..35.

Marcin Gąsiorek, Structure of non-negative posets of Dynkin type A_n, arXiv:2205.15032 [math.CO], 2022.

Formula

a(n) = (1/(2*n)) * Sum_{d|n} (2^(n/d) * phi(d)) + floor(2^(n-2) + 2^(ceiling(n/2 - 2)) - (n+1)/2), where phi is the Euler totient function (A000010).

Maple

anum := proc(n::integer)
    local d, term1, term2;
    if n < 1 then
        return 0;
    end if;
    term1 := iquo(add(2^iquo(n, d) * NumberTheory:-Totient(d), d in NumberTheory:-Divisors(n)), (2 * n));
    term2 := floor(2^(n - 2) + 2^ceil(n / 2 - 2) - (n + 1) / 2);
    return term1 + term2;
end proc;

Mathematica

anum[n_Integer?Negative] := 0;
anum[0] := 0;
anum[n_Integer?Positive] := DivisorSum[n, 2^(n/#) EulerPhi[#] &]/(2 n) + Floor[(2^n + 2^Ceiling[n/2])/4 - (n + 1)/2];

Prog

(Python)
from sympy import Integer, Rational, divisors, totient, ceiling, floor
def anum(n: int) -> int:
    if n < 1:
        return 0
    n = Integer(n)
    term1 = sum(2**(n // d) * totient(d) for d in divisors(n)) // (2 * n)
    term2 = floor(2**(n - 2) + 2**ceiling(n / 2 - 2) - Rational(n + 1, 2))
    return int(term1 + term2)
(SageMath)
def anum(n):
    if n < 1:
        return 0
    term1 = sum(2^(n // d) * euler_phi(d) for d in divisors(n) ) // (2 * n)
    term2 = floor(2^(n - 2) + 2^ceil(n/2 - 2) - (n + 1)/2)
    return term1 + term2

Crossrefs

Cf. A000010.

Sequence in context: A192664 A122997 A146042 * A291219 A284358 A283584

Adjacent sequences: A396767 A396768 A396769 * A396771 A396772 A396776

Keyword

nonn,easy

Author

Marcin Gąsiorek, Jun 05 2026

Status

approved