A395691 Triangle read by rows: T(n,k) = number of labeled 2-multigraphs on n vertices with clique number exactly k.

1, 1, 2, 1, 18, 8, 1, 248, 416, 64, 1, 6264, 36080, 15680, 1024, 1, 294986, 6434528, 6536000, 1050624, 32768, 1, 25126170, 2555681112, 5913294912, 1833638912, 130514944, 2097152, 1, 3796366064, 2319538554560, 12579916621184, 7064248705024, 878237581312, 30786191360, 268435456

Offset

1,3

Comments

A 2-multigraph allows edge multiplicities 0, 1, or 2. Clique number is defined on the underlying simple graph (edges with multiplicity >=1).

Part of the family T_p(n,k) = Sum_{G: omega(G)=k} p^{e(G)}. Row sums give 3^(n*(n-1)/2).

The range p=1..5 covers typical transportation network interlining depths (metro/tram systems). See cross-references for other p values.

Values computed by weighting simple graph enumeration with 2^{e(G)}; verified for n<=7.

Links

Sean A. Irvine, Table of n, a(n) for n = 1..66

Alejandro Zarzuelo Urdiales, Clique-Size Dominance Threshold Distribution Enumerating Labeled Graphs by Clique Number and the Minimum Coding Clique Size, Zenodo, 2026.

Alejandro Zarzuelo Urdiales, Python verification code and Lean 4 formalization, GitHub.

Formula

T(n,k) = Sum_{G: omega(G)=k} 2^{e(G)}, where e(G) is the number of edges in the underlying simple graph G.

Row sum: Sum_{k=1..n} T(n,k) = 3^(n*(n-1)/2).

Example

Triangle begins:
  n=1: 1
  n=2: 1, 2
  n=3: 1, 18, 8
  n=4: 1, 248, 416, 64
  n=5: 1, 6264, 36080, 15680, 1024
  n=6: 1, 294986, 6434528, 6536000, 1050624, 32768
  n=7: 1, 25126170, 2555681112, 5913294912, 1833638912, 130514944, 2097152

Crossrefs

Cf. A395684 (p=1, simple graphs), A395692 (p=3), A395693 (p=4), A395694 (p=5), A395695 (cumulative), A006125 (labeled simple graphs), A000088 (unlabeled simple graphs).

Sequence in context: A335024 A270927 A089512 * A300956 A089014 A063426

Adjacent sequences: A395682 A395683 A395684 * A395692 A395693 A395694

Keyword

tabl,nonn

Author

Alejandro Zarzuelo Urdiales, May 04 2026

Extensions

a(29)-a(36) from Pontus von Brömssen, May 23 2026

Status

approved