A380890 Triangle T(n,k) read by rows: the number of graphs with n nodes which are enriched cycles (necklaces) and the elements in the cycle are marked linear chains up to length k.

1, 1, 2, 1, 2, 4, 1, 3, 5, 7, 1, 3, 7, 9, 12, 1, 5, 14, 18, 21, 24, 1, 5, 19, 29, 35, 38, 42, 1, 8, 35, 56, 71, 77, 81, 85, 1, 10, 60, 100, 133, 148, 156, 160, 165, 1, 15, 107, 192, 264, 297, 317, 325, 330, 335, 1, 19, 187, 361, 511, 586, 630, 650, 660, 665, 671, 1, 31, 352, 714, 1041, 1206, 1306, 1350, 1375, 1385, 1391, 1397

Offset: 1

Author

R. J. Mathar, Feb 07 2025

Keywords

• nonn
• tabl

Comments

The number of marked/rooted linear chains (linear trees) with up to k nodes has the generating function x+ x^2 +2*x^3 +2*x^4 + 3*x^5 +3*x^6+...+floor((k+1)/2)*x^k, a truncated version of A110654. [The node in the chain that is marked can be at the end of the chain, penultimate node etc up to the middle node, which gives floor((k+1)/2) ways; marking any of the other nodes does not generate more marked chains because the entire chain can be flipped over.] A multiset of such marked chains defines an "enriched" necklace if m marked nodes are arranged in a circle and a chord is wired through these nodes. That chord is the only cycle in the graph. The total number n of nodes in that graph is the sum over the individual chain lengths of the m chains.

In Bower's nomenclatures the columns approach the CIK transform of A110654 for k->oo: 1, 2, 4, 7, 12, 24, 42, 85, 165, 335, 671, 1397,...

If the total number of nodes n is fixed, the number of graphs T(n,k) stays constant in the rows at k>n, because chains longer than n are never used due to the limit imposed on n.

The book of Bona (edt.) shows on page 1002 a graph with a cycle constructed with 5 linear chains up to length k=4 (1 chain of length 1, 2 chains of length 2, 1 chain of length 3, 1 chain of length 4) and n=12 nodes in total. It seems the "pointed operation" there creates more chains than enumeration of rooted linear trees here.

Examples

			The full array starts
   1    1    1    1    1    1    1    1    1    1    1    1
   1    2    2    2    2    2    2    2    2    2    2    2
   1    2    4    4    4    4    4    4    4    4    4    4
   1    3    5    7    7    7    7    7    7    7    7    7
   1    3    7    9   12   12   12   12   12   12   12   12
   1    5   14   18   21   24   24   24   24   24   24   24
   1    5   19   29   35   38   42   42   42   42   42   42
   1    8   35   56   71   77   81   85   85   85   85   85
   1   10   60  100  133  148  156  160  165  165  165  165
   1   15  107  192  264  297  317  325  330  335  335  335
   1   19  187  361  511  586  630  650  660  665  671  671
   1   31  352  714 1041 1206 1306 1350 1375 1385 1391 1397
The sequence gathers only the non-trivial lower left triangle up to the diagonal.
T(1,k)=1 means whatever the set of variable-length linear chains is, if the total number of nodes is 1 only the linear chain of length 1 (ring of a single element) is a necklace.
T(n,1)=1 means the only available element in the necklace are simple (marked) nodes. To generate a enriched necklace with n nodes in total can only be done by putting that node n times repeated on a circle.
T(4,3)=5 means the available chains up to length k=3 are x, x-o, x-o-o and o-x-o; x denotes the marked node. The 5 cycles/necklaces with n=4 nodes are: [x]-[x]-[x]-[x], [x]-[x]-[x-o], [x-o]-[x-o], [x]-[x-o-o], and [x]-[o-x-o], where [...] is the a linear node in the circle.
		

Links

• Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, pages 1001-1002.
• C. G. Bower, Transforms (2)
• Index entries for sequences related to necklaces

Crossrefs

Cf. A322059, A000358 (column k=2, binary necklace).

Programs

Maple

# Generating function of a marked linear chain
# (=rooted linear tree) up to n nodes.
# Essentially a truncated (polynomial) version of A110654.
# @param n Number of nodes
# @param x free variable in the o.g.f.
gLinChain := proc(n,x)
    add(floor((i+1)/2) *x^i,i=1..n) ;
end proc:
# k: max element in each chain
# n: number of total nodes in graph
A380890 := proc(n,k)
    local x,g ,cidx,d,gd,ncyc;
    # number of possible elements in the cycle
    g := gLinChain(k,x) ;
    # wrap g into the Polya cycle index of the cyclic group C_ncyc
    cidx := 0 ;
    for ncyc from 1 to n do
        for d in numtheory[divisors](ncyc) do
            gd := subs(x=x^d,g) ;
            cidx := cidx+1/ncyc*numtheory[phi](d)*gd^(ncyc/d) ;
        end do:
    end do:
    coeff(cidx,x^n) ;
end proc:
seq(seq(A380890(n,k),k=1..n),n=1..12) ;