A397925 Number of bicolored multigraphs on n unlabeled vertices with vertex degrees at most 3.

1, 2, 6, 14, 38, 94, 250, 648, 1756, 4770, 13412, 38220, 112225, 335468, 1030376, 3226530, 10359124, 33908070, 113571902, 387562846, 1350820250, 4792328042, 17335765926, 63766055568, 238793853401, 908391462060, 3513396532338, 13790906177294, 54973361303680, 222204923547144, 911176919187308, 3785813537404906, 15943082918454581

Offset

0,2

Comments

The color classes are not interchangeable and edges may not connect vertices of the same color (so loops are not allowed).

An n vertex bicolored multigraph with p > 0 vertices of one color and q > 0 vertices of the other can be represented as a p X q nonnegative integer matrix. Each entry gives the multiplicity of an edge. Row and column sums correspond to the vertex degrees and will be at most 3. In addition, it is possible for all vertices to have the same color.

Links

Table of n, a(n) for n=0..32.

Formula

G.f.: B(x)/(1 - x)^2 where B(x) is the g.f. of A397924.

Euler transform of A397917.

Example

The a(3) = 14 = 1 + 6 + 6 + 1 since there are 6 graphs with 1 vertex in one part and 2 in the other (2 cases). The other 2 cases are for when all vertices are in just one of the parts. The 6 cases that correspond to 2 X 1 matrices are:
   [0]  [0]  [0]  [0]  [1]  [1]
   [0]  [1]  [2]  [3]  [1]  [2]

Crossrefs

Cf. A397917 (connected case), A397924 (without isolated vertices).

Sequence in context: A026597 A122112 A190788 * A168259 A275208 A000634

Adjacent sequences: A397922 A397923 A397924 * A397926 A397927 A397929

Keyword

nonn,new

Author

Andrew Howroyd, Jul 15 2026

Status

approved