Graph Likelihood

Author

Eric W. Weisstein
August 2, 2026

This notebook downloaded from https://mathworld.wolfram.com/notebooks/GraphTheory/GraphLikelihood.nb.

For more information, see Eric's MathWorld entry https://mathworld.wolfram.com/GraphLikelihood.html.

©2026 Wolfram Research, Inc. except for portions noted otherwise

Construction

Explicit lists (generate list with full expansion and probability for each expansion)

LikelihoodStep[{g_System`Graph,p_}]:=Module[{n=VertexCount[g]},
(Function[s,{EdgeAdd[VertexAdd[g,n+1],UndirectedEdge[#,n+1]&/@s],p/Binomial[n,Length[s]]/(n+1)}]/@Subsets[Range[n]])
]

(*
LikelihoodStep[l_]:={#[[1,1]],Total[#[[All,2]]]}&/@SplitBy[SortBy[(* bug(260322) *)
Flatten[LikelihoodStep/@l,1],
EdgeList[#[[1]]]&
],First]
*)
LikelihoodStep[l_]:={#[[1,2]],Total[#[[All,-1]]]}&/@
SplitBy[Sort[{CanonicalForm[#[[1]]],#[[1]],#[[2]]}&/@Flatten[LikelihoodStep/@l,1]],First]
g[1]={{System`Graph[{1},{}],1}};
g[n_]:=g[n]=LikelihoodStep[g[n-1]]

Save

Do[Print[{i,Length[g[i]]//Timing,MaxMemoryUsed[]/10^9. GB}];
Put[g[i],"/home/usr2/eww/mma/Graphs/Nodes/Likelihood/Graphs_"<>ToString[i]<>".m"] n,{i,9}]

Recognize

Do[Print[{i,rec=Map[If[GraphQ[#],RecognizeGraph[Evaluate@#,"Indexed"->False],#]&,g[i],{-1}];//Timing}];
Put[DeleteCases[rec,{{},_}],"/home/usr2/eww/mma/Graphs/Nodes/Likelihood/GraphNames_"<>ToString[i]<>".m"],{i,8}]

Arrays (store probabilities in-place)

counts={1,2,4,11,34,156,1044,12346,274668,12005168};

LikelihoodStep[g_System`Graph]:=Module[{n=VertexCount[g],p},p=like[n][[GraphIndex[g]]];
Function[s,array[[GraphIndex[EdgeAdd[VertexAdd[g,n+1],UndirectedEdge[#,n+1]&/@s]]]]+=p/Binomial[n,Length[s]]/(n+1)]/@Subsets[Range[n]];]

like[1]={1};
Do[array=ConstantArray[0,counts[[n]]];
Print[
{
n,
First[LikelihoodStep/@Graphs[n-1];//Timing],
MaxMemoryUsed[]/10^9. GB,
like[n]=array;Length[like[n]],
ByteCount[like[n]]/10^9.GB,
Through[{Min,Max,Total}[like[n]]]
}
];
Put[like[n],"/home/usr2/eww/mma/Graphs/Nodes/Likelihood/Likelihoods_"<>ToString[n]<>".m"],
{n,2,9}
]

Total/@Array[like,9,2]

nodes10=(ind=Cases[GraphData[#,"StandardNames"],{10,x_}:>x][[1]];{#,like[10][[ind]]})&/@GraphData[10];

Length[nodes10]

Put[nodes10,"/home/usr2/eww/mma/Graphs/Nodes/Likelihood/GraphNames_10.m"]

Attempt at path algorithm

AllAdjacencyMatrices2[g_System`Graph]:=Module[{n=VertexCount[g],e=EdgeList[g],p},If[(p=Quiet[Check[Permutations[Range[n]],$Failed]])===$Failed,Return[p]];
Normal[AdjacencyMatrix[System`Graph[Range[n],e/.Thread[Range[n]->#]]]]&/@p]

{#,Tally[AllAdjacencyMatrices2[GraphData[#]]][[All,2]]}&/@GraphData[4]//Column

(#->GraphData[#,"|Aut|"])&/@GraphData[4]//Column

Grid[{#,GraphData[#,"|Aut|"],GraphData[#,"Likelihood"],MatrixForm/@Normal/@GraphData[#,"AdjacencyMatrices"]}&/@GraphData[4],Dividers->All,Alignment->Left]

(Subscript[P, 3])

GraphData["P3","Likelihood"]

GraphData["P3","Degrees"]

MatrixForm/@(a=AllAdjacencyMatrices[GraphData["P3"]])

MatrixPlot/@a

(1/(3!))((1/2)+1+(1/2))

1/Binomial[2,{1,2,1}]

Claw

GraphData["ClawGraph","Likelihood"]

GraphData["ClawGraph","Degrees"]

MatrixPlot/@(a=AllAdjacencyMatrices[GraphData["ClawGraph"]])

(1/(4!))((1/3)+(1/2)+(1/2)+(1/3))

(4,2)

GraphData[{4,2},"Likelihood"]

GraphData[{4,2},"Degrees"]

MatrixPlot/@(a=AllAdjacencyMatrices[GraphData[{4,2}]])

(1/(4!))(1+1+1)

(4,6)

GraphData[{4,6},"Likelihood"]

GraphData[{4,6},"Degrees"]

MatrixPlot/@(a=AllAdjacencyMatrices[GraphData[{4,6}]])

(1/(4!))((1/2)+(1/3)+(1/3)+(1/2))

(1/2)+(1/3)+(1/3)+(1/2)

(1/(4!))((1/2)+(1/2)+(1/2))

1/Binomial[3,{2,0,2,2}]

{(1/6),1,(1/6),(1/6)}//Total

Binomial[0,4]

Visualization

GraphicsGrid[Map[Show[GraphPlot[GraphData[#[[1]]],"VertexColor"->Directive[AbsolutePointSize[5],Red],"EdgeColor"->Black],PlotLabel->TextCell[Row[{Style[GraphData[#[[1]],"Name"],FontFamily->"Times",FontSlant->Italic]," ","(",#[[2]],")"},BaseStyle->FontFamily->"Times"],TextAlignment->Center,PageWidth->100]]&,Flatten[Partition[#,6,6,{1,1},{}]&/@Take[rec,4],1],{2}],Dividers->All,ImageSize->620]

Co-likely

Column[({#[[1,1]],#[[All,2]]}&/@Select[SplitBy[Sort[Reverse/@#],First],Length[#]>1&])&/@Take[rec,5]]

Inequality

Select[GraphData["Likelihood","Defined"],!({n,aut,L}=GraphData[#,{"V","AutomorphismCount","Likelihood"}];1/(aut Product[Binomial[i-1,Floor[(i-1)/2]],{i,n}])≤L≤1/aut)&]

Product[Binomial[i-1,Floor[(i-1)/2]],{i,n}]

Table[Product[Binomial[i-1,Floor[(i-1)/2]],{i,n}],{n,8}]

Refine[Floor[(i-1)/2],Mod[i,2]==0]//Simplify

Product[Binomial[i-1,(1/2) (-2+i)],{i,n}]

Refine[Floor[(i-1)/2],Mod[i,2]==1]//Simplify

Product[Binomial[i-1,(1/2) (-1+i)],{i,n}]

GraphDataCountTable

<<MathWorld`Graphs`

table=GraphDataCountTable["Likelihood",{"CocktailParty"->{394956,397599},"Complete"->{000012,000142},"Empty"->{000012,000142},"LadderRung"->{394956,397599},"Star"->{293458,010796}}]

TextGrid[OEISUpdates[table],Dividers->All]

Parametrized families

Alkane

seq=Table[GraphData[{"Alkane",n},"Likelihood"],{n,10}]

AlternatingGroupGraph

seq=Table[GraphData[{"AlternatingGroupGraph",n},"Likelihood"],{n,2,6}]

Andrasfai

seq=Table[GraphData[{"Andrasfai",n},"Likelihood"],{n,20}]

Formula search

FindSequenceFunction[DeleteMissing@seq,n]//Head//Timing

FindGeneratingFunction[DeleteMissing@seq,x]//Head//Timing

Computation

Do[Print[{gn={"Andrasfai",n},TimeConstrained[GraphLikelihood[GraphData[gn]],60]//AbsoluteTiming}],{n,10}]

Antelope n×n

seq=Table[GraphData[{"Antelope",{n,n}},"Likelihood"],{n,20}]

Antelope m×n

Quiet[DeleteCases[Flatten[Table[{{m,n},GraphData[{"Antelope",{m,n}},"Likelihood"],XXX},{n,20},{m,n}],1],{_,x_,x_}|{_,_GraphData,_}]]

Antiprism

Entity["Graph",{"Antiprism",n}]["Likelihood"]

seq=Table[GraphData[{"Antiprism",n},"Likelihood"],{n,3,25}]

Formula search

FindSequenceFunction[DeleteMissing@seq,n]//Head//Timing

FindGeneratingFunction[DeleteMissing@seq,x]//Head//Timing

Computation

Do[Print[{gn={"Antiprism",n},GraphLikelihood[GraphData[gn],TimeConstraint->60]//AbsoluteTiming}],{n,3,25}]

Computation using subset-DP 1

graphLikelihoodFromAdjacency[adj_List, aut_Integer] := Module[
  {m = Length[adj], full, dp, next, b, new},
  full = 2^Length[adj] - 1;
  dp = <|0 -> 1|>;

  Do[
    next = <||>;
    KeyValueMap[
      Function[{mask, val},
        Do[
          If[BitGet[mask, v] == 0,
            b = Total[BitGet[mask, #] & /@ adj[[v + 1]]];
            new = mask + 2^v;
            next[new] = Lookup[next, new, 0] + val/Binomial[s, b]
          ],
          {v, 0, m - 1}
        ]
      ],
      dp
    ];
    dp = next,
    {s, 0, m - 1}
  ];

  Lookup[dp, full]/(aut Factorial[m])
];

antiprismAdjacency[n_Integer?Positive] /; n >= 3 := Table[
  Sort @ DeleteDuplicates @ Mod[v + {1, -1, 2, -2}, 2 n],
  {v, 0, 2 n - 1}
];

antiprismAutOrder[n_Integer?Positive] /; n >= 3 :=
  If[n == 3, 48, 4 n];

antiprismLikelihood[n_Integer?Positive] /; n >= 3 :=
  graphLikelihoodFromAdjacency[
    antiprismAdjacency[n],
    antiprismAutOrder[n]
  ];

Do[Print[{gn={"Antiprism",n},TimeConstrained[antiprismLikelihood[n],60]//AbsoluteTiming}],{n,3,25}]

Computation using subset-DP 2

ClearAll[antiprismLikelihoodOrbitDP];

antiprismLikelihoodOrbitDP[n_Integer?Positive] /; n >= 3 := Module[
  {
    m = 2 n, bitPowers, bitMasks, full, aut, neighbors, binom,
    rotate, reflect, canon, reflectCache = <||>, canonCache = <||>,
    dp, next, s
  },

  bitPowers = 2^Range[0, m - 1];
  bitMasks = 2^Range[0, m] - 1;
  full = bitMasks[[m + 1]];

  (* Aut(A_3) is the octahedral graph automorphism group; otherwise dihedral. *)
  aut = If[n == 3, 48, 4 n];

  neighbors = Table[
    Mod[v + {-2, -1, 1, 2}, m],
    {v, 0, m - 1}
  ];

  binom = Table[
    Binomial[s, b],
    {s, 0, m - 1}, {b, 0, 4}
  ];

  rotate[mask_Integer, r_Integer] := Module[
    {rr = Mod[r, m], low, high},
    If[rr == 0,
      mask,
      low = BitAnd[mask, bitMasks[[m - rr + 1]]];
      high = BitShiftRight[mask, m - rr];
      BitOr[BitShiftLeft[low, rr], high]
    ]
  ];

  reflect[mask_Integer] := If[
    KeyExistsQ[reflectCache, mask],
    reflectCache[mask],
    With[
      {
        res = Module[{x = mask, i = 0, y = 0},
          While[x > 0,
            If[OddQ[x], y += bitPowers[[Mod[-i, m] + 1]]];
            x = BitShiftRight[x, 1];
            i++
          ];
          y
        ]
      },
      AssociateTo[reflectCache, mask -> res];
      res
    ]
  ];

  canon[mask_Integer] := If[
    KeyExistsQ[canonCache, mask],
    canonCache[mask],
    With[
      {
        res = Module[{rfl = reflect[mask]},
          Min[
            Join[
              Table[rotate[mask, r], {r, 0, m - 1}],
              Table[rotate[rfl, r], {r, 0, m - 1}]
            ]
          ]
        ]
      },
      AssociateTo[canonCache, mask -> res];
      res
    ]
  ];

  dp = <|0 -> 1|>;

  Do[
    next = <||>;

    KeyValueMap[
      Function[{mask, val},
        Do[
          If[BitGet[mask, v] == 0,
            With[
              {
                b = Total[BitGet[mask, #] & /@ neighbors[[v + 1]]],
                new = canon[BitOr[mask, bitPowers[[v + 1]]]]
              },
              next[new] = Lookup[next, new, 0] + val/binom[[s + 1, b + 1]]
            ]
          ],
          {v, 0, m - 1}
        ]
      ],
      dp
    ];

    dp = next,
    {s, 0, m - 1}
  ];

  Lookup[dp, full]/(aut Factorial[m])
]

Do[Print[{gn={"Antiprism",n},TimeConstrained[antiprismLikelihoodOrbitDP[n],60]//AbsoluteTiming}],{n,3,10}]

ChatGPT 5.5 Heavy thinking 1

For `GraphData[{"Antiprism", n}]`, the cleanest exact form I find is a finite construction-order sum, not a simple hypergeometric/special-function closed form.

MathWorld defines the graph likelihood by the random vertex-adjoining process, and lists the antiprism values beginning with your sequence. It also states that the `n`-antiprism graph has `2 n` vertices, `4 n` edges, and is isomorphic to the circulant graph `Ci_(2n)(1,2)`. ([MathWorld][1])

Let `A_n` be the `n`-antiprism graph, `n >= 3`, with vertices `Z/(2 n) Z` and edges between vertices differing by `+-1` or `+-2` modulo `2 n`. Then

```text
L(A_n) =
  1/(a_n (2 n)!) Sum[
    Product[
      1/Binomial[j - 1, b_j(pi)],
      {j, 2, 2 n}
    ],
    {pi in Permutations[Range[0, 2 n - 1]]}
  ]
```

where

```text
a_n = 48     if n == 3
a_n = 4 n    if n >= 4
```

and

```text
b_j(pi) =
  Count[
    pi[[1 ;; j - 1]],
    x_ /; Mod[pi[[j]] - x, 2 n] in {1, 2, 2 n - 1, 2 n - 2}
  ].
```

This is independent of `GraphData`; it is just the likelihood definition summed over all construction orders. The factor `a_n` is the automorphism group order of `A_n`.

A useful derived reduction is this. If `v` is any vertex of `A_n`, then

```text
L(A_n) = L(VertexDelete[A_n, v])/(2 n Binomial[2 n - 1, 4]).
```

This follows because `A_n` is vertex-transitive and 4-regular, and

```text
|Aut(A_n - v)|/|Aut(A_n)| = 1/(2 n).
```

For implementation/checking, here is exact reusable WL code:

```wl
ClearAll[graphLikelihoodFromAdjacency, antiprismAdjacency,
  antiprismAutOrder, antiprismLikelihood];

graphLikelihoodFromAdjacency[adj_List, aut_Integer] := Module[
  {m = Length[adj], full, dp, next, b, new},
  full = 2^Length[adj] - 1;
  dp = <|0 -> 1|>;

  Do[
    next = <||>;
    KeyValueMap[
      Function[{mask, val},
        Do[
          If[BitGet[mask, v] == 0,
            b = Total[BitGet[mask, #] & /@ adj[[v + 1]]];
            new = mask + 2^v;
            next[new] = Lookup[next, new, 0] + val/Binomial[s, b]
          ],
          {v, 0, m - 1}
        ]
      ],
      dp
    ];
    dp = next,
    {s, 0, m - 1}
  ];

  Lookup[dp, full]/(aut Factorial[m])
];

antiprismAdjacency[n_Integer?Positive] /; n >= 3 := Table[
  Sort @ DeleteDuplicates @ Mod[v + {1, -1, 2, -2}, 2 n],
  {v, 0, 2 n - 1}
];

antiprismAutOrder[n_Integer?Positive] /; n >= 3 :=
  If[n == 3, 48, 4 n];

antiprismLikelihood[n_Integer?Positive] /; n >= 3 :=
  graphLikelihoodFromAdjacency[
    antiprismAdjacency[n],
    antiprismAutOrder[n]
  ];
```

Check against built-in values:

```wl
Table[
  {n, antiprismLikelihood[n], GraphData[{"Antiprism", n}, "Likelihood"]},
  {n, 3, 9}
]
```

This also gives the first missing value:

```wl
antiprismLikelihood[10]
```

```wl
75637875718562046471964574285507/
 18533383145863441025931564892776494742411946229760000000000000000
```

So my honest conclusion is: there is a rigorous all-`n` finite-sum closed form and an exact DP implementation, but I do not see a compact scalar closed form analogous to the known complete/empty/star/isolated-edge/path-related cases listed on MathWorld/Banerji--Mansour--Severini. The published graph-likelihood paper explicitly gives algorithms and closed formulas for only some infinite classes, with general complexity left open. ([arxiv.org][2])

[1]: https://mathworld.wolfram.com/GraphLikelihood.html "Graph Likelihood -- from Wolfram MathWorld"
[2]: https://arxiv.org/abs/1304.3600 "[1304.3600] A notion of graph likelihood and an infinite monkey theorem"

ChatGPT 5.5 Heavy thinking 2

Yes -- your timing comparison is fair. My earlier `antiprismLikelihood` was a raw subset DP over all `2^(2 n)` vertex subsets. It was meant as an independent evaluator, not as a competitive implementation. The rectangular closed-limit sum is even worse: it has `(2 n)^(2 n - 1)` rectangular terms before the distinctness factor kills repeats.

A better antiprism-specific evaluator is to quotient the subset DP by the dihedral symmetry of `Ci_(2n)(1,2)`. MathWorld gives the relevant model: the `n`-antiprism graph has `2 n` vertices and is `Ci_(2n)(1,2)`, so vertices can be taken modulo `2 n` with edges of differences `+-1,+-2`. MathWorld's likelihood definition is the vertex-adjoining construction being summed over construction orders. cite

The recurrence is:

```wl
F[{}] = 1

F[T] = Sum[
  F[DeleteCases[T, v]]/
    Binomial[Length[T] - 1, Length[Intersection[Neighbors[v], DeleteCases[T, v]]]],
  {v, T}
]
```

and then

```wl
Likelihood[A_n] = F[Range[0, 2 n - 1]]/(AutOrder[A_n] (2 n)!)
```

Here is the dihedral-orbit version. It stores total weight over each orbit of subsets, not each subset.

```wl
ClearAll[antiprismLikelihoodOrbitDP];

antiprismLikelihoodOrbitDP[n_Integer?Positive] /; n >= 3 := Module[
  {
    m = 2 n, bitPowers, bitMasks, full, aut, neighbors, binom,
    rotate, reflect, canon, reflectCache = <||>, canonCache = <||>,
    dp, next, s
  },

  bitPowers = 2^Range[0, m - 1];
  bitMasks = 2^Range[0, m] - 1;
  full = bitMasks[[m + 1]];

  (* Aut(A_3) is the octahedral graph automorphism group; otherwise dihedral. *)
  aut = If[n == 3, 48, 4 n];

  neighbors = Table[
    Mod[v + {-2, -1, 1, 2}, m],
    {v, 0, m - 1}
  ];

  binom = Table[
    Binomial[s, b],
    {s, 0, m - 1}, {b, 0, 4}
  ];

  rotate[mask_Integer, r_Integer] := Module[
    {rr = Mod[r, m], low, high},
    If[rr == 0,
      mask,
      low = BitAnd[mask, bitMasks[[m - rr + 1]]];
      high = BitShiftRight[mask, m - rr];
      BitOr[BitShiftLeft[low, rr], high]
    ]
  ];

  reflect[mask_Integer] := If[
    KeyExistsQ[reflectCache, mask],
    reflectCache[mask],
    With[
      {
        res = Module[{x = mask, i = 0, y = 0},
          While[x > 0,
            If[OddQ[x], y += bitPowers[[Mod[-i, m] + 1]]];
            x = BitShiftRight[x, 1];
            i++
          ];
          y
        ]
      },
      AssociateTo[reflectCache, mask -> res];
      res
    ]
  ];

  canon[mask_Integer] := If[
    KeyExistsQ[canonCache, mask],
    canonCache[mask],
    With[
      {
        res = Module[{rfl = reflect[mask]},
          Min[
            Join[
              Table[rotate[mask, r], {r, 0, m - 1}],
              Table[rotate[rfl, r], {r, 0, m - 1}]
            ]
          ]
        ]
      },
      AssociateTo[canonCache, mask -> res];
      res
    ]
  ];

  dp = <|0 -> 1|>;

  Do[
    next = <||>;

    KeyValueMap[
      Function[{mask, val},
        Do[
          If[BitGet[mask, v] == 0,
            With[
              {
                b = Total[BitGet[mask, #] & /@ neighbors[[v + 1]]],
                new = canon[BitOr[mask, bitPowers[[v + 1]]]]
              },
              next[new] = Lookup[next, new, 0] + val/binom[[s + 1, b + 1]]
            ]
          ],
          {v, 0, m - 1}
        ]
      ],
      dp
    ];

    dp = next,
    {s, 0, m - 1}
  ];

  Lookup[dp, full]/(aut Factorial[m])
]
```

Check against the built-in values:

```wl
Table[
  With[
    {
      a = antiprismLikelihoodOrbitDP[n],
      b = GraphData[{"Antiprism", n}, "Likelihood"]
    },
    {n, a, b, a === b}
  ],
  {n, 3, 9}
]
```

For your computed missing values, it should also give:

```wl
Table[antiprismLikelihoodOrbitDP[n], {n, 10, 11}]
```

```wl
{
  75637875718562046471964574285507/
    18533383145863441025931564892776494742411946229760000000000000000,

  372569114515873909778991657584290843/
    11285789223032616705992691314043033578536720262844383232000000000000000000
}
```

So the summary is:

* Built-in/known small values: your `GraphData` sequence for `n = 3..9`.
* Computed values: your `GraphLikelihood` values for `n = 10, 11`.
* Mathematical reduction: exact DP over dihedral orbits of subsets of `Z/(2 n) Z`; this is still exponential, but it replaces roughly `2^(2 n)` subset states by binary-bracelet-type orbit states.

Apollonian

seq=Table[GraphData[{"Apollonian",n},"Likelihood"],{n,6}]

Barbell

seq=Table[GraphData[{"Barbell",n},"Likelihood"],{n,3,20}]

Formula

ClearAll[barbellLikelihoodExact];

barbellLikelihoodExact[n_Integer?Positive] :=
 Module[{m = n - 1, f},
  Clear[f];

  f[l_, r_, a_, b_] /; l == m && r == m && a == 1 && b == 1 := 1;

  f[l_, r_, a_, b_] :=
    f[l, r, a, b] =
      Module[{s = l + r + a + b},
        Total@Join[
          If[l < m, {f[l + 1, r, a, b]/Binomial[s, l + a]}, {}],
          If[r < m, {f[l, r + 1, a, b]/Binomial[s, r + b]}, {}],
          If[a == 0, {f[l, r, 1, b]/Binomial[s, l + b]}, {}],
          If[b == 0, {f[l, r, a, 1]/Binomial[s, r + a]}, {}]
        ]
      ];

  f[0, 0, 0, 0]/(2 Factorial[2 n])
]

seq=Table[barbellLikelihoodFormula[n],{n,3,20}]

Formula search

FindSequenceFunction[DeleteMissing@seq,n]//Head//Timing

FindGeneratingFunction[DeleteMissing@seq,x]//Head//Timing

Computation

Do[Print[{gn={"Barbell",n},TimeConstrained[GraphLikelihood[GraphData[gn]],60]//AbsoluteTiming}],{n,3,10}]

ChatGPT 5.5 Heavy thinking 1

Yes. I do not see a simple hypergeometric-style one-term closed form, but there is a clean finite closed form / state-collapsed recurrence that is much faster than general `GraphLikelihood` and matches your values.

Using the MathWorld convention, `{"Barbell", n}` is two copies of `K_n` connected by a bridge; this is also the convention MathWorld says is used by `GraphData[{"Barbell", n}]`. ([MathWorld][1]) Graph likelihood is the probability of obtaining the graph under the random vertex-addition process where at step `t` one chooses `k in {0,...,t-1}` uniformly and then chooses the `k` previous neighbors uniformly. ([MathWorld][2])

For `n >= 2`, let `L` and `R` be the two non-bridge vertex types, and `A`, `B` the two bridge endpoints. If a typed birth word has counts before the current position

```wl
{l, r, a, b}
```

where `l,r` count already-born non-bridge vertices on the two sides and `a,b` are `0` or `1`, then the backward degrees are

```wl
L : l + a
R : r + b
A : l + b
B : r + a
```

So the exact formula is

```wl
ClearAll[barbellLikelihoodWeight, barbellLikelihoodFormula];

barbellLikelihoodWeight[n_Integer?Positive] :=
  barbellLikelihoodWeight[n] =
    Module[{m = n - 1, f},
      Clear[f];

      f[l_, r_, a_, b_] /; l == m && r == m && a == 1 && b == 1 := 1;

      f[l_, r_, a_, b_] :=
        f[l, r, a, b] =
          Module[{s = l + r + a + b},
            Total @ Join[
              If[l < m, {f[l + 1, r, a, b]/Binomial[s, l + a]}, {}],
              If[r < m, {f[l, r + 1, a, b]/Binomial[s, r + b]}, {}],
              If[a == 0, {f[l, r, 1, b]/Binomial[s, l + b]}, {}],
              If[b == 0, {f[l, r, a, 1]/Binomial[s, r + a]}, {}]
            ]
          ];

      f[0, 0, 0, 0]
    ];

barbellLikelihoodFormula[n_Integer?Positive] :=
  barbellLikelihoodWeight[n]/(2 Factorial[2 n]);
```

Check against your values:

```wl
Table[
  {n, GraphData[{"Barbell", n}, "Likelihood"],
   barbellLikelihoodFormula[n]},
  {n, 3, 10}
]
```

should give identical third column entries:

```wl
{97/129600,
 79/282240000,
 3527/370355328000000,
 120872989/2788888326373416960000000,
 446254883/15608378974475115989198438400000,
 143794240658106769/53748875717956964290102354057258598400000000000,
 25611962972025696976693/720414345572828324500409762939785936784012083200000000000000,
 41752310912120147934657493/614779621517505312219943864990290404878887132739802234880000000000000000}
```

Why the final denominator is `2 Factorial[2 n]`: the product of the uniform step factors contributes `(2 n)!`; the non-bridge vertex labels cancel the `(n - 1)!^2` part of the automorphism group; the remaining automorphism is the left-right swap. Thus

```wl
L[Barbell[n]] == W[n]/(2 (2 n)!)
```

where `W[n]` is exactly the memoized four-state sum above.

So: **yes, there is a nice exact recurrence/finite closed form**, but probably not a simple `FindSequenceFunction`-type closed form. This is also a good candidate for a GraphData formula implementation because it is structural and not fit from stored likelihood values.

[1]: https://mathworld.wolfram.com/BarbellGraph.html "Barbell Graph -- from Wolfram MathWorld"
[2]: https://mathworld.wolfram.com/GraphLikelihood.html "Graph Likelihood -- from Wolfram MathWorld"

ChatGPT 5.5 Heavy thinking 2

Yes. I can get a nonrecursive finite-sum closed form. I would call this a legitimate closed form, though not a simple one-term hypergeometric expression.

MathWorld/GraphData use `{"Barbell", n}` for two copies of `K_n` joined by a bridge, and graph likelihood is the probability from the random vertex-addition process with uniform choice of backward degree and uniform choice of that neighbor set. ([MathWorld][1])

Let `X = {x1 < ... < xn}` be the positions occupied by the left clique among the `2 n` birth positions, and let `Y = {y1 < ... < yn}` be its complement. Define

```wl
p[x_, y_, n_] :=
  Product[
    1/(Binomial[x[[i]] - 1, i - 1] Binomial[y[[i]] - 1, i - 1]),
    {i, n}
  ]
```

and let the initial one-side run length be

```wl
h[x_, y_] := If[First[x] == 1, First[y] - 1, First[x] - 1]
```

Then the closed form is:

```wl
ClearAll[barbellLikelihoodClosed];

barbellLikelihoodClosed[n_Integer?Positive] :=
 Module[{r = Range[2 n]},
  Total[
    Function[x,
      Module[{y = Complement[r, x], run},
        run = If[First[x] == 1, First[y] - 1, First[x] - 1];

        (n (n + 1) - run (run + 1)/2)/
          Product[
            Binomial[x[[i]] - 1, i - 1]*
             Binomial[y[[i]] - 1, i - 1],
            {i, n}
          ]
      ]
    ] /@ Subsets[r, {n}]
  ]/(2 Factorial[2 n])
]
```

Equivalently, in mathematical terms:

```wl
L[Barbell[n]] ==
  1/(2 (2 n)!) Sum[
    Product[
      1/(Binomial[x_i - 1, i - 1] Binomial[y_i - 1, i - 1]),
      {i, 1, n}
    ] (n (n + 1) - h (h + 1)/2),
    {X subset Range[2 n], Length[X] == n}
  ]
```

where `Y = Complement[Range[2 n], X]`, both sorted increasingly, and

```wl
h = If[x_1 == 1, y_1 - 1, x_1 - 1].
```

Check:

```wl
Table[
  {n, GraphData[{"Barbell", n}, "Likelihood"],
   barbellLikelihoodClosed[n]},
  {n, 3, 10}
]
```

should return no disagreements.

The key simplification is this. For a fixed left/right interleaving `X,Y`, ignore the bridge first. The base clique weight is

```wl
Product[
  1/(Binomial[x[[i]] - 1, i - 1] Binomial[y[[i]] - 1, i - 1]),
  {i, n}
]
```

Now choose which left vertex and which right vertex are the bridge endpoints. If the `i`th left vertex is born after the `j`th right vertex, the bridge multiplies the base weight by

```wl
i/(x[[i]] - i)
```

and similarly in the other direction. Summing over all endpoint choices collapses to

```wl
n (n + 1) - h (h + 1)/2
```

where `h` is exactly the initial run length before the first switch from one side to the other. The final factor `2 Factorial[2 n]` comes from the universal degree-choice product `(2 n)!` and the remaining left-right automorphism.

[1]: https://mathworld.wolfram.com/BarbellGraph.html?utm_source=chatgpt.com "Barbell Graph -- from Wolfram MathWorld"

ChatGPT 5.5 Heavy thinking 3

You're right. That was mathematical notation, not valid WL. Here is the same formula in WL-valid form only:

```wl
ClearAll[barbellLikelihoodClosed];

barbellLikelihoodClosed[n_Integer?Positive] :=
 Module[{positions = Range[2 n]},
  Total[
    Function[xs,
      Module[{ys, run, denom},
        ys = Complement[positions, xs];

        run = If[First[xs] == 1,
          First[ys] - 1,
          First[xs] - 1
        ];

        denom = Product[
          Binomial[xs[[i]] - 1, i - 1]*
            Binomial[ys[[i]] - 1, i - 1],
          {i, n}
        ];

        (n (n + 1) - run (run + 1)/2)/denom
      ]
    ] /@ Subsets[positions, {n}]
  ]/(2 Factorial[2 n])
]
```

Check:

```wl
Table[
  {n, GraphData[{"Barbell", n}, "Likelihood"], barbellLikelihoodClosed[n]},
  {n, 3, 10}
]
```

Or just the disagreement test:

```wl
Select[
  Table[
    {n, GraphData[{"Barbell", n}, "Likelihood"], barbellLikelihoodClosed[n]},
    {n, 3, 10}
  ],
  #[[2]] =!= #[[3]] &
]
```

should return

```wl
{}
```

The WL-valid closed form is therefore:

```wl
1/(2 Factorial[2 n]) *
 Total[
   ((n (n + 1) - run (run + 1)/2)/
      Product[
        Binomial[xs[[i]] - 1, i - 1]*
          Binomial[ys[[i]] - 1, i - 1],
        {i, n}
      ])
 ]
```

with `xs` ranging over `Subsets[Range[2 n], {n}]`, `ys = Complement[Range[2 n], xs]`, and

```wl
run = If[First[xs] == 1, First[ys] - 1, First[xs] - 1]
```

ChatGPT 5.5 Heavy thinking 4

Correct. I overstated it.

What I derived is an **exact finite combinatorial sum**, not a closed form in the usual sense. Since the number of summation terms grows like

```wl
Binomial[2 n, n]
```

it is not meaningfully different from a collapsed enumeration. Under the usual hypergeometric/closed-form sense for discrete functions, one expects something with rational shift quotients or standard factorial/binomial/Pochhammer factors, not a variable-size subset sum. MathWorld’s “closed form” entry uses that hypergeometric-type criterion for discrete terms. ([MathWorld][1])

So the honest status is:

```wl
Barbell likelihood:
  closed form: not obtained
  exact finite sum: yes
  exact low-dimensional recurrence: yes
  empirical simple sequence formula: no evidence from FindSequenceFunction / FindGeneratingFunction
```

The best clean formulation I currently have is the recurrence, not a closed form:

```wl
ClearAll[barbellLikelihoodExact];

barbellLikelihoodExact[n_Integer?Positive] :=
 Module[{m = n - 1, f},
  Clear[f];

  f[l_, r_, a_, b_] /; l == m && r == m && a == 1 && b == 1 := 1;

  f[l_, r_, a_, b_] :=
    f[l, r, a, b] =
      Module[{s = l + r + a + b},
        Total@Join[
          If[l < m, {f[l + 1, r, a, b]/Binomial[s, l + a]}, {}],
          If[r < m, {f[l, r + 1, a, b]/Binomial[s, r + b]}, {}],
          If[a == 0, {f[l, r, 1, b]/Binomial[s, l + b]}, {}],
          If[b == 0, {f[l, r, a, 1]/Binomial[s, r + a]}, {}]
        ]
      ];

  f[0, 0, 0, 0]/(2 Factorial[2 n])
]
```

For GraphData purposes, I would describe this as an **exact recurrence / dynamic programming formula**, not as a closed form. The remaining obstruction is essentially the weighted sum over left/right interleavings of the two cliques; I do not currently see a standard simplification of that sum to factorials, binomials, or hypergeometric terms.

[1]: https://mathworld.wolfram.com/ClosedForm.html?utm_source=chatgpt.com "Closed Form -- from Wolfram MathWorld"

BipartiteKneser

({#1,q=GraphData[#1,"NotationRules","BipartiteKneser"],XXX,GraphData[#1,"Likelihood"]}&)/@GraphData["BipartiteKneser"]

Bishop n×n

seq=Table[GraphData[{"Bishop",{n,n}},"Likelihood"],{n,10}]

Bishop m×n

Quiet[DeleteCases[Flatten[Table[{{m,n},GraphData[{"Bishop",{m,n}},"Likelihood"],XXX},{n,20},{m,n}],1],{_,x_,x_}|{_,_GraphData,_}]]

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"Likelihood"],{n,10}]

BlackBishop m×n

Quiet[DeleteCases[Flatten[Table[{{m,n},GraphData[{"BlackBishop",{m,n}},"Likelihood"],XXX},{n,20},{m,n}],1],{_,x_,x_}|{_,_GraphData,_}]]

Book

seq=Table[GraphData[{"Book",n},"Likelihood"],{n,20}]

Bruhat

seq=Table[GraphData[{"Bruhat",n},"Likelihood"],{n,6}]

Camel n×n

seq=Table[GraphData[{"Camel",{n,n}},"Likelihood"],{n,20}]

Camel m×n

Entity["Graph",{"Camel",{m,n}}]["Likelihood"]

Cameron

seq=Table[GraphData[{"Cameron",n},"Likelihood"],{n,20}]

Centipede

seq=Table[GraphData[{"Centipede",n},"Likelihood"],{n,10}]

CocktailParty

A394956/A397599

seq=Table[GraphData[{"CocktailParty",n},"Likelihood"],{n,20}]

FindSequenceFunction[DeleteMissing@seq,n]//Head//Timing

FindGeneratingFunction[DeleteMissing@seq,x]//Head//Timing

SeriesCoefficient[InverseErf[Sqrt[2/Pi] z]^2, {z, 0, 2 n}]/(2 n - 1)!

Table[SeriesCoefficient[InverseErf[Sqrt[2/Pi] z]^2, {z, 0, 2 n}]/(2 n - 1)!,{n,20}]

Bell-polynomial version, avoiding SeriesCoefficient of an inverse function:

aBell[n_Integer?Positive]:=If[n==1,1/2,Module[{r=n-1},Sum[Binomial[-2 n,k] k! BellY[r,k,Table[(-1)^j/(2 j+1),{j,r-k+1}]],{k,1,r}]/(2^n n (2 n-1)! r!)]]

Table[aBell[n],{n,20}]

Lagrange–Bürmann:

a[n_Integer?Positive]:=SeriesCoefficient[Hypergeometric1F1[1/2,3/2,-u]^(-2 n),{u,0,n-1}]/(2^n n (2 n-1)!);

Table[a[n],{n,20}]

Codex 5.5 High

The cocktail party graph is the complement of a matching. The graph likelihood process is invariant under graph complementation: at a step with t - 1 earlier vertices, choosing a set S and choosing its complement have the same probability because Binomial[t - 1, |S|] = Binomial[t - 1, t - 1 - |S|]. Therefore the likelihood of the cocktail party graph on 2 n vertices is the likelihood of the matching on n edges. For the matching, the exponential generating function of the perfect-matching likelihood numerators is InverseErf[Sqrt[2/Pi] z]^2, giving Likelihood = SeriesCoefficient[InverseErf[Sqrt[2/Pi] z]^2, {z, 0, 2 n}]/(2 n - 1)!.

ChatGPT 5.5 Pro Standard

The cocktail party graph on 2 n vertices is the complement of the matching with n edges, so complement invariance gives the same likelihood as the n-rung ladder-rung graph. With

A_n = [z^(2 n)] InverseErf[Sqrt[2/Pi] z]^2/(2 n - 1)!,

set x = z^2 and u = InverseErf[Sqrt[2/Pi] z]^2. Since x = 2 u Hypergeometric1F1[1/2, 3/2, -u]^2, Lagrange-Buermann inversion gives the compact coefficient form

A_n = SeriesCoefficient[Hypergeometric1F1[1/2, 3/2, -u]^(-2 n), {u, 0, n - 1}]/(2^n n (2 n - 1)!)

for n >= 1. Equivalently,

A_n = Derivative[n - 1][Function[u, Hypergeometric1F1[1/2, 3/2, -u]^(-2 n)]][0]/(2^n n (2 n - 1)! (n - 1)!).

The same value also has the exact finite-sum form

A_n = 1/(2 n)! Sum[Product[(i_j - (2 j - 1))/(i_j - 1), {j, 1, n}], 2 <= i_1 < i_2 < ... < i_n <= 2 n],

where the last display is shorthand for summing over all increasing n-tuples selected from {2,...,2 n}.

Complete

A000012/A000142

Entity["Graph",{"Complete",n}]["Likelihood"]

seq=Table[GraphData[{"Complete",n},"Likelihood"],{n,30}]

FullSimplify[FindSequenceFunction[seq,n]]

Table[(1/(n!)),{n,20}]

Formula search

FindSequenceFunction[DeleteMissing@seq,n]

FullSimplify[%]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

Options[SeriesCoefficient]

SeriesCoefficient[-1+(E^x),{x,0,n},Assumptions->n>0]

Computation

Do[Print[{gn={"Complete",n},TimeConstrained[GraphLikelihood[GraphData[gn]],60]//AbsoluteTiming}],{n,20}]

ChatGPT 5.5 Heavy thinking

For `{"Complete", n}`, the closed form is just

```wl
completeLikelihood[n_Integer?Positive] := 1/n!
```

or, if you want a symbolic GraphData-style guard,

```wl
completeLikelihood[n_] :=
  Piecewise[
    {{1/n!, Element[n, PositiveIntegers]}},
    Missing["Unknown"]
  ]
```

**Derivation, non-circular.** Graph likelihood starts from `K_1`. To obtain `K_m` from `K_(m-1)` at step `m`, the construction must choose `k == m - 1`; then the chosen vertex subset is forced. Since `k` is chosen uniformly from `{0, 1, ..., m - 1}`, that step has probability `1/m`. Therefore

```wl
Product[1/m, {m, 2, n}]
```

which simplifies to

```wl
1/n!
```

for positive integer `n`.

This matches the MathWorld likelihood construction, where step `n` chooses `k` uniformly from `{0, ..., n - 1}` and adds a new vertex adjacent to `k` selected existing vertices; it also matches the MathWorld/GraphData convention that `{"Complete", n}` is `K_n`, the graph with every pair of vertices adjacent. ([MathWorld][1])

Your generating-function check is also clean:

```wl
seq = Table[GraphData[{"Complete", n}, "Likelihood"], {n, 30}];

gf = x FindGeneratingFunction[seq, x]
(* -1 + E^x *)

SeriesCoefficient[gf, {x, 0, n}, Assumptions -> n > 0]
(* 1/n! *)
```

The `Pochhammer` form is equivalent but less transparent:

```wl
FullSimplify[1/Pochhammer[2, -1 + n], n ∈ PositiveIntegers]
(* 1/n! *)
```

[1]: https://mathworld.wolfram.com/GraphLikelihood.html "Graph Likelihood -- from Wolfram MathWorld"

CompleteBipartite n×n

Entity["Graph",{"CompleteBipartite",{n,n}}]["Likelihood"]

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"Likelihood"],{n,20}]

Formula search

FindSequenceFunction[DeleteMissing@seq,n]//Head//Timing

FindGeneratingFunction[DeleteMissing@seq,x]//Head//Timing

Formula

ClearAll[kbbWeightSum, completeBipartiteSquareLikelihood];

kbbWeightSum[0, 0] = 1;

kbbWeightSum[a_Integer?NonNegative, b_Integer?NonNegative] /; a + b > 0 :=
  kbbWeightSum[a, b] =
    If[a > 0,
      kbbWeightSum[a - 1, b]/Binomial[a + b - 1, a - 1],
      0
    ] +
    If[b > 0,
      kbbWeightSum[a, b - 1]/Binomial[a + b - 1, a],
      0
    ];

completeBipartiteSquareLikelihood[n_Integer?Positive] :=
  kbbWeightSum[n, n]/(2 (2 n)!);

Table[completeBipartiteSquareLikelihood[n],{n,10}]

Computation

Do[Print[{gn={"CompleteBipartite",{n,n}},TimeConstrained[GraphLikelihood[GraphData[gn]],60]//AbsoluteTiming}],{n,20}]

ChatGPT 5.5 Heavy thinking 1

Yes. A clean closed form is a finite weighted lattice-path sum.

Using the MathWorld/GraphData definition of graph likelihood: at step `m`, choose `k` uniformly from `0,...,m-1`, then choose a `k`-subset of existing vertices uniformly, add the new vertex with exactly that neighborhood, and merge isomorphic outcomes by summing probabilities. GraphData documents `"Likelihood"` as this random number/subset-picking probability, with unavailable values returned as `Missing["NotAvailable"]`. ([MathWorld][1])

For `K_{n,n}`, let `P` be the set of birth positions of one bipartition class among positions `1,...,2 n`. Define

```wl
s[P_, j_] := Count[P, x_ /; x <= j]
```

Then

```wl
L(K_{n,n}) =
  1/(2 (2 n)!) Sum[
    Product[1/Binomial[j, s[P, j]], {j, 0, 2 n - 1}],
    {P, Subsets[Range[2 n], {n}]}
  ]
```

Equivalently, avoiding the factor `1/2` by choosing the representative side whose first vertex is born at position 1,

```wl
L(K_{n,n}) =
  1/((2 n)!) Sum[
    Product[1/Binomial[j, s[P, j]], {j, 0, 2 n - 1}],
    {P, Subsets[Range[2, 2 n], {n - 1}] /. q_ :> Prepend[q, 1]}
  ]
```

A faster reusable WL version is the dynamic recurrence:

```wl
ClearAll[kbbWeightSum, completeBipartiteSquareLikelihood];

kbbWeightSum[0, 0] = 1;

kbbWeightSum[a_Integer?NonNegative, b_Integer?NonNegative] /; a + b > 0 :=
  kbbWeightSum[a, b] =
    If[a > 0,
      kbbWeightSum[a - 1, b]/Binomial[a + b - 1, a - 1],
      0
    ] +
    If[b > 0,
      kbbWeightSum[a, b - 1]/Binomial[a + b - 1, a],
      0
    ];

completeBipartiteSquareLikelihood[n_Integer?Positive] :=
  kbbWeightSum[n, n]/(2 (2 n)!);
```

Check:

```wl
Table[completeBipartiteSquareLikelihood[n], {n, 12}]
```

returns

```wl
{
  1/2,
  1/36,
  23/259200,
  319/15240960000,
  76441/145179288576000000,
  20692621/11155553305493667840000000,
  368997387881/386307379618259120732661350400000000,
  7628328998218493/107497751435913928580204708114517196800000000000,
  2200453451294991512083/2881657382291313298001639051759143747136048332800000000000000,
  745390385554039789980124061/619697858489645354717703415910212728117918229801720652759040000000000000000,
  26371843450387020511682155949071009/94032118175260993296436805774086542843112614399957352061552059755667862323200000000000000000,
  93204800293484607644262865138522250824183/9530220158764476401007774296922107925307004516911521891170301602125681555174551475791593472000000000000000000
}
```

Proof sketch: for a fixed birth order, the probability contribution is

```wl
Product[1/i, {i, 1, 2 n}] *
Product[1/Binomial[i - 1, earlierOppositeCount[i]], {i, 1, 2 n}]
```

The first product is `1/(2 n)!`. For `K_{n,n}`, if `P` records one side, then at prefix length `j = i - 1`, the number of earlier vertices on that side is `s[P, j]`, so the relevant subset denominator is

```wl
Binomial[j, s[P, j]]
```

using symmetry of binomial coefficients. Finally, the two bipartition classes can be swapped, giving the factor `1/2` in the all-subsets version. No GraphData values are used in the derivation; they are only consistency checks.

[1]: https://mathworld.wolfram.com/GraphLikelihood.html "Graph Likelihood -- from Wolfram MathWorld"

ChatGPT 5.5 Heavy thinking 2

Probably not in any useful one-variable classical special-function form.

What I can give is a more “special-function-like” finite form.  Let

```wl
r[i_, a_, b_] := Product[1/Binomial[j, i], {j, a, b}]
```

or, using Barnes `G`,

```wl
rBarnes[i_, a_, b_] :=
  Piecewise[{
    {1, b < a},
    {Gamma[i + 1]^(b - a + 1) BarnesG[b - i + 2] BarnesG[a + 1]/
      (BarnesG[a - i + 1] BarnesG[b + 2]), b >= a}
  }]
```

Then an exact closed form for `K_{n,n}` is

```wl
ClearAll[completeBipartiteSquareLikelihoodClosed];

completeBipartiteSquareLikelihoodClosed[n_Integer?Positive] :=
 Module[{p},
  Sum[
    Product[
      rBarnes[i, p[i], p[i + 1] - 1],
      {i, 1, n}
    ],
    Evaluate @ Sequence @@ Table[{p[i], p[i - 1] + 1, 2 n - n + i}, {i, 2, n}]
  ] /. {p[1] -> 1, p[n + 1] -> 2 n} / (2 n)!
 ]
```

But honestly, this is not better than the lattice-path recurrence. It is just the same path sum with each run-product collapsed using `Gamma`/`BarnesG`.

The more compact exact form I would actually use is:

```wl
ClearAll[invPascalStep, kbbLikelihood];

invPascalStep[p_, m_, x_] :=
  (1 + x) Sum[Coefficient[p, x, r]/Binomial[m, r] x^r, {r, 0, m}];

kbbLikelihood[n_Integer?Positive] :=
  Coefficient[
    Fold[invPascalStep[#1, #2, x] &, 1, Range[0, 2 n - 1]],
    x, n
  ]/(2 n)!;
```

This is equivalent to the operator form

```text
L(K_{n,n}) = [x^n] P_{2 n}(x)/(2 n)!,
P_0(x) = 1,
P_{m+1}(x) = (1 + x) Gamma[theta + 1] Gamma[m - theta + 1]/Gamma[m + 1] P_m(x),
theta = x D_x.
```

So: **yes**, it can be packaged using `Gamma`/`BarnesG` or a beta/inverse-Pascal operator; **no**, I do not see a genuine simplification to `HypergeometricPFQ`, `MeijerG`, a gamma product, or a fixed named special function.

That also matches the literature situation I found: MathWorld lists closed forms for complete, empty, star, isolated-edge families, etc., but not for the complete bipartite minimum-likelihood family; the paper it cites says closed formulas are known only for some infinite classes and leaves complexity open. ([MathWorld][1]) The `K_{floor(n/2),ceil(n/2)}` values are recorded as the minimum-likelihood sequence in OEIS, again without a closed special-function formula. ([oeis.org][2])

[1]: https://mathworld.wolfram.com/GraphLikelihood.html?utm_source=chatgpt.com "Graph Likelihood -- from Wolfram MathWorld"
[2]: https://oeis.org/A234234?utm_source=chatgpt.com "A234234"

Codex 5.5 High

This is the equal-part specialization of the complete bipartite recurrence. With W(a, b) as in the complete bipartite proof, the two parts have equal size and are interchangeable, so the likelihood is W(n, n)/(2 (2 n)!).

CompleteBipartite m×n

Entity["Graph",{"CompleteBipartite",{m,n}}]["Likelihood"]

completeBipartiteLikelihood[n_Integer?Positive,2]:=If[n===2,1/2,1]*Sum[2^c (n-c)! Sum[k!,{k,0,n-c}],{c,0,n}]/((n+2)! n! (n+1)!);
completeBipartiteLikelihood[n_,m_]:=Missing["NotAvailable"]

Sum[k!,{k,0,n-c}]//FullSimplify

Sum[2^c (n-c)! Sum[k!,{k,0,n-c}],{c,0,n}]

Sort@DeleteCases[
Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"Likelihood"],
completeBipartiteLikelihood[m,n]
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]

Codex 5.5 High

Let the complete bipartite graph have part sizes m and n. By complement invariance, its likelihood is the likelihood of the disjoint union of two complete graphs of sizes m and n. If W(a, b) denotes the sum of the nonuniversal binomial factors for labeled parts, then W(0, 0) = 1 and W(a, b) = If[a > 0, W(a - 1, b)/Binomial[a + b - 1, a - 1], 0] + If[b > 0, W(a, b - 1)/Binomial[a + b - 1, b - 1], 0]. The universal step factors contribute 1/(m + n)!, and equal part sizes have been labeled twice in W, so the final value is W(m, n)/((m + n)! Times @@ (Factorial /@ Values[Counts[{m, n}]]))).

ChatGPT 5.6 Codex Sol High

For n >= 1, let q(r) = Sum[k!, {k, 0, r}] and let e(n) be 1/2 when n = 2 and 1 otherwise. Then

L(K_(2,n)) = e(n)/((n + 2)! n! (n + 1)!) Sum[2^c (n - c)! q(n - c), {c, 0, n}].

Proof. Graph likelihood is invariant under complementation, so it is enough to compute the likelihood of the disjoint union K_2 union K_n. For n != 2, group vertex orders by their word in the two vertex types A and B; the 2! n! labeled orders represented by each word cancel the automorphism factor 2! n!. When n = 2, interchanging the two equal clique components gives the additional factor e(2) = 1/2.

Write a type word uniquely as B^a A B^b A B^c, where a + b + c = n. Before the first A, each new B is adjacent to every earlier vertex and contributes binomial factor 1. Between the two A vertices, the B contributions multiply to a!/(a + b)!. The second A contributes 1/(a + b + 1). After the second A, the B contributions multiply to 2^c (a + b)! (a + b + 1)!/(n! (n + 1)!). Thus the product of reciprocal binomial factors for this word is

2^c a! (a + b)!/(n! (n + 1)!).

For fixed c, a + b = n - c, so summing over a gives (n - c)! q(n - c)/(n! (n + 1)!). Multiplication by the universal 1/(n + 2)! construction factor and summation over c proves the formula.

CompleteTripartite n×n×n

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["Likelihood"]

seq=Table[GraphData[{"CompleteTripartite",{n,n,n}},"Likelihood"],{n,10}]

FindSequenceFunction[DeleteMissing@seq,n]

Codex 5.5 High

This is the equal-part specialization of the complete tripartite recurrence. With W(a, b, c) for labeled parts, the three equal parts are interchangeable, so the likelihood is W(n, n, n)/(6 (3 n)!).

CompleteTripartite k×m×n

Entity["Graph",{"CompleteTripartite",{k,m,n}}]["Likelihood"]

completeTripartiteLikelihood[1, 1, 1]:=1/6;
completeTripartiteTkelihood[n_Integer?Positive,1,n]/;n>=2:=Sum[2^c (n-c+1)! Sum[k!,{k,0,n-c}],{c,0,n}]/((n+2)! n! (n+1)!);
completeTripartiteLikelihood[_,_,_]:=Missing["NotAvailable"]

DeleteCases[
Flatten[Table[{
{k,m,n},
GraphData[{"CompleteTripartite",{k,m,n}},"Likelihood"],
XXX
},{n,10},{m,n},{k,m}],2],
{_,x_,x_}|{_,_GraphData,_}]

Codex 5.5 High

Let the complete tripartite graph have part sizes k, m, and n. Complementing gives a disjoint union of three complete graphs. For labeled parts, set W(0, 0, 0) = 1 and W(a, b, c) equal to the sum over positive coordinates x of W(a, b, c) with that coordinate decreased by one, divided by Binomial[a + b + c - 1, x - 1]. The factor appears because a newly inserted vertex in a part with x - 1 earlier vertices in the complement must choose exactly those x - 1 earlier vertices. The universal factors give 1/(k + m + n)!, and equal-sized parts are unlabeled by dividing by Times @@ (Factorial /@ Values[Counts[{k, m, n}]]).

ChatGPT 5.6 Codex Sol High

For n >= 2, let q(r) = Sum[k!, {k, 0, r}]. Then

L(K_(1,1,n)) = 1/((n + 2)! n! (n + 1)!) Sum[2^c (n - c + 1)! q(n - c), {c, 0, n}].

The exceptional value is L(K_(1,1,1)) = L(K_3) = 1/6.

Proof. By complement invariance, compute the likelihood of K_n union 2 K_1. For n >= 2 its automorphism group has order n! 2!, so grouping labeled vertex orders by a word with n clique letters C and two indistinguishable isolate letters I cancels this automorphism factor. Write such a word uniquely as C^a I C^b I C^c, where a + b + c = n. Clique vertices before the first I contribute 1. Those between the isolates contribute a!/(a + b)!, and those after both isolates contribute 2^c (a + b)! (a + b + 1)!/(n! (n + 1)!). The isolate vertices themselves contribute 1. Hence the reciprocal-binomial weight of the word is

2^c a! (a + b + 1)!/(n! (n + 1)!).

For fixed c, a + b = n - c, and summing over a gives (n - c + 1)! q(n - c)/(n! (n + 1)!). The universal construction factor 1/(n + 2)! gives the stated formula. For n = 1 all three complement vertices are indistinguishable, so the separate exceptional value is required.

CompleteTripartiteMinusPerfectMatching

seq=Table[GraphData[{"CompleteTripartiteMinusPerfectMatching",{2 n,2 n,2 n}},"Likelihood"],{n,10}]

Coprime

seq=Table[GraphData[{"Coprime",n},"Likelihood"],{n,20}]

CossidentePenttila

({#1,q=GraphData[#1,"NotationRules","CossidentePenttila"],XXX,GraphData[#1,"Likelihood"]}&)/@GraphData["CossidentePenttila"]

CrossedPrism

seq=Table[GraphData[{"CrossedPrism",2 n},"Likelihood"],{n,2,12}]

Crown

seq=Table[GraphData[{"Crown",n},"Likelihood"],{n,3,20}]

FindSequenceFunction[DeleteMissing@seq,n-2]//Head//Timing

FindGeneratingFunction[DeleteMissing@seq,x]//Head//Timing

CubeConnectedCycle

(Entity[(RowDefault["n", "\[Hyphen]cube\[Hyphen]connected cycle graph"]), Entity["Graph",{"CubeConnectedCycle",n}], "Entity[\"Graph\", {\"CubeConnectedCycle\", n}]", "graph"])["Likelihood"]

Cycle

Entity["Graph",{"Cycle",n}]["Likelihood"]

seq=Table[GraphData[{"Cycle",n},"Likelihood"],{n,3,30}]

Through[{Numerator,Denominator}[seq]]

FindSequenceFunction[DeleteMissing@seq,n-2]//Head//Timing

FindGeneratingFunction[DeleteMissing@seq,x]//Head//Timing

CycleComplement

seq=Table[GraphData[{"CycleComplement",n},"Likelihood"],{n,3,20}]

DiagonalIntersection

seq=Table[GraphData[{"DiagonalIntersection",n},"Likelihood"],{n,3,14}]

Dipyramid

seq=Table[GraphData[{"Dipyramid",n},"Likelihood"],{n,3,20}]

DorogovtsevGoltsevMendes

seq=Table[GraphData[{"DorogovtsevGoltsevMendes",n},"Likelihood"],{n,0,7}]

DoubleCone

seq=Table[GraphData[{"DoubleCone",n},"Likelihood"],{n,3,20}]

Empty

A000012/A000142

Entity["Graph",{"Empty",n}]["Likelihood"]

seq=Table[GraphData[{"Empty",n},"Likelihood"],{n,30}]

FindSequenceFunction[seq,n]//FullSimplify

ErectedPolygon

DeleteCases[(Module[{n,r},{#1,{n,r}=GraphData[#1,"NotationRules","ErectedPolygon"],XXX,GraphData[#1,"Likelihood"]}]&)/@GraphData["ErectedPolygon"],{__,x_,x_}]

FibonacciCube

seq=Table[GraphData[{"FibonacciCube",n},"Likelihood"],{n,15}]

Fiveleaper n×n

seq=Table[GraphData[{"Fiveleaper",{n,n}},"Likelihood"],{n,20}]

Fiveleaper m×n

Entity["Graph",{"Fiveleaper",{m,n}}]["Likelihood"]

Flower

seq=Table[GraphData[{"Flower",n},"Likelihood"],{n,5,20}]

FoldedCube

seq=Table[GraphData[{"FoldedCube",n},"Likelihood"],{n,2,10}]

Gear

seq=Table[GraphData[{"Gear",n},"Likelihood"],{n,3,20}]

Giraffe n×n

seq=Table[GraphData[{"Giraffe",{n,n}},"Likelihood"],{n,20}]

Giraffe m×n

Entity["Graph",{"Fiveleaper",{m,n}}]["Likelihood"]

Goldberg

seq=Table[GraphData[{"Goldberg",n},"Likelihood"],{n,3,20}]

Grid n×n

Entity["Graph",{"Grid",{n,n}}]["Likelihood"]

seq=Table[GraphData[{"Grid",{n,n}},"Likelihood"],{n,20}]

Formula search

FindSequenceFunction[DeleteMissing@seq,n]//Head//Timing

FindGeneratingFunction[DeleteMissing@seq,x]//Head//Timing

Formula

gridSquareLikelihoodDP[n_Integer?Positive] := Module[
  {
    nv = n^2, adjMask, vals, all, mask, s, low, v, prev,
    k, d, total, i, j, w, aut
  },

  adjMask = ConstantArray[0, n^2];

  Do[
    v = 1 + (i - 1) n + (j - 1);

    If[i > 1,
      w = 1 + (i - 2) n + (j - 1);
      adjMask[[v]] = BitOr[adjMask[[v]], BitShiftLeft[1, w - 1]]
    ];

    If[i < n,
      w = 1 + i n + (j - 1);
      adjMask[[v]] = BitOr[adjMask[[v]], BitShiftLeft[1, w - 1]]
    ];

    If[j > 1,
      w = 1 + (i - 1) n + (j - 2);
      adjMask[[v]] = BitOr[adjMask[[v]], BitShiftLeft[1, w - 1]]
    ];

    If[j < n,
      w = 1 + (i - 1) n + j;
      adjMask[[v]] = BitOr[adjMask[[v]], BitShiftLeft[1, w - 1]]
    ],
    {i, n}, {j, n}
  ];

  all = 2^nv - 1;
  vals = ConstantArray[0, 2^nv];
  vals[[1]] = 1;

  Do[
    k = DigitCount[mask, 2, 1];
    total = 0;
    s = mask;

    While[s != 0,
      low = BitAnd[s, -s];
      v = 1 + IntegerExponent[low, 2];
      prev = BitXor[mask, low];

      d = DigitCount[BitAnd[adjMask[[v]], prev], 2, 1];

      total += vals[[prev + 1]]/(k Binomial[k - 1, d]);
      s = BitXor[s, low];
    ];

    vals[[mask + 1]] = total,
    {mask, 1, all}
  ];

  aut = If[n == 1, 1, 8];
  vals[[all + 1]]/aut
]

Do[Print[{gn={"Grid",{n,n}},TimeConstrained[gridSquareLikelihoodDP[n],60]//AbsoluteTiming}],{n,10}]

Computation

Do[Print[{gn={"Grid",{n,n}},TimeConstrained[GraphLikelihood[GraphData[gn]],60]//AbsoluteTiming}],{n,10}]

ChatGPT 5.5 Heavy thinking 1

Fair. It should not have taken a general graph for this problem.

I used a general helper because it was a quick way to check arbitrary `GraphData` values, but for `Grid[n,n]` that is unnecessary clutter. The square-grid version should take only `n`.

No `ClearAll`, no `BitCount`, no general graph argument:

```wl
gridSquareLikelihoodDP[n_Integer?Positive] := Module[
  {
    nv = n^2, adjMask, vals, all, mask, s, low, v, prev,
    k, d, total, i, j, w, aut
  },

  adjMask = ConstantArray[0, n^2];

  Do[
    v = 1 + (i - 1) n + (j - 1);

    If[i > 1,
      w = 1 + (i - 2) n + (j - 1);
      adjMask[[v]] = BitOr[adjMask[[v]], BitShiftLeft[1, w - 1]]
    ];

    If[i < n,
      w = 1 + i n + (j - 1);
      adjMask[[v]] = BitOr[adjMask[[v]], BitShiftLeft[1, w - 1]]
    ];

    If[j > 1,
      w = 1 + (i - 1) n + (j - 2);
      adjMask[[v]] = BitOr[adjMask[[v]], BitShiftLeft[1, w - 1]]
    ];

    If[j < n,
      w = 1 + (i - 1) n + j;
      adjMask[[v]] = BitOr[adjMask[[v]], BitShiftLeft[1, w - 1]]
    ],
    {i, n}, {j, n}
  ];

  all = 2^nv - 1;
  vals = ConstantArray[0, 2^nv];
  vals[[1]] = 1;

  Do[
    k = DigitCount[mask, 2, 1];
    total = 0;
    s = mask;

    While[s != 0,
      low = BitAnd[s, -s];
      v = 1 + IntegerExponent[low, 2];
      prev = BitXor[mask, low];

      d = DigitCount[BitAnd[adjMask[[v]], prev], 2, 1];

      total += vals[[prev + 1]]/(k Binomial[k - 1, d]);
      s = BitXor[s, low];
    ];

    vals[[mask + 1]] = total,
    {mask, 1, all}
  ];

  aut = If[n == 1, 1, 8];
  vals[[all + 1]]/aut
]
```

Check:

```wl
Table[gridSquareLikelihoodDP[n], {n, 4}]
```

should return your four known values.

Mathematically this is the exact recurrence

```text
F(S) = Sum[
  F(S \ {v})/(|S| Binomial[|S| - 1, deg_{S \ {v}}(v)]),
  {v, S}
]
```

specialized to `S` being a subset of the `n^2` square-grid vertices, with final division by `8` for the square-grid automorphism group when `n >= 2`.

ChatGPT 5.5 Heavy thinking 2

Yes. That is a fair criticism.

The subset recurrence I gave is **not** a useful replacement for `GraphLikelihood`. It is only a transparent exact recurrence. For `Grid[n,n]`, your timings show exactly that:

```wl
n = 4:
  my subset recurrence: 5.40 s
  GraphLikelihood:      3.93 s
```

So it should be discarded as a computational improvement.

The right summary is:

```text
For Grid[n,n], I do not currently have a compact closed form in n.

The exact formulas I gave are:
  1. a permutation/order-sum formula, factorial size;
  2. a subset recurrence, exponential size.

Neither is better than the built-in GraphLikelihood implementation.
```

The reason the subset version loses is mostly WL-level overhead: it loops over all `2^(n^2)` subsets, does exact rational arithmetic at every state, and does many `DigitCount`/bit operations interpreted in WL. `GraphLikelihood` is already a specialized built-in and is apparently better optimized.

So the honest status is:

```wl
Entity["Graph", {"Grid", {n, n}}]["Likelihood"]
```

has no symbolic formula available, and from the data

```wl
{1, 1/36,
 2136467/11522165760000,
 2332821161628113887217/
   8549350222742186969547826790400000000000}
```

I would **not** claim a closed form.

The best exact mathematical statement I can defend is still the order-sum formula

```text
L(G) = 1/|Aut(G)| Sum_pi Product_t
  1/(t Binomial[t - 1, b_t(pi)])
```

specialized to `G = Grid[n,n]`, with

```text
b_t(pi) = number of earlier neighbors of pi_t.
```

But that is a definition-level closed expression, not a useful closed form in `n`.

Grid m×n

Entity["Graph",{"Grid",{m,n}}]["Likelihood"]

Grid n×n×n

Entity["Graph",{"Grid",{n,n,n}}]["Likelihood"]

seq=Table[GraphData[{"Grid",{n,n,n}},"Likelihood"],{n,10}]

Grid k×m×n

Entity["Graph",{"Grid",{k,m,n}}]["Likelihood"]

HalvedCube

seq=Table[GraphData[{"HalvedCube",n},"Likelihood"],{n,10}]

Hanoi

seq=Table[GraphData[{"Hanoi",n},"Likelihood"],{n,5}]

Helm

seq=Table[GraphData[{"Helm",n},"Likelihood"],{n,3,20}]

Hypercube

Entity["Graph",{"Hypercube",n}]["Likelihood"]

seq=Table[GraphData[{"Hypercube",n},"Likelihood"],{n,0,10}]

FindSequenceFunction[DeleteMissing@seq,n+1]//Head//Timing

FindGeneratingFunction[DeleteMissing@seq,x]//Head//Timing

Computation

Do[Print[{gn={"Hypercube",n},TimeConstrained[GraphLikelihood[GraphData[gn]],60]//AbsoluteTiming}],{n,0,10}]

Computation using subset-DP

HypercubeLikelihoodRecurrence[d_Integer?NonNegative]:=Module[{n=2^d,neigh,f,verticesInMask,full},neigh=Table[Table[BitXor[v,2^j],{j,0,d-1}],{v,0,2^d-1}];
verticesInMask[mask_Integer]:=Select[Range[0,n-1],BitGet[mask,#]==1&];
f[1]=1;(*fix first vertex 0*)f[mask_Integer]/;BitGet[mask,0]==1:=f[mask]=Module[{m=DigitCount[mask,2,1]},Total[Table[If[v==0&&mask!=1,0,With[{prev=BitClear[mask,v]},f[prev]/(m Binomial[m-1,Count[neigh[[v+1]],u_/;BitGet[prev,u]==1]])]],{v,verticesInMask[mask]}]]];
full=2^n-1;
f[full]/Factorial[d]]

Do[Print[{gn={"Hypercube",n},TimeConstrained[HypercubeLikelihoodRecurrence[n],60]//AbsoluteTiming}],{n,0,10}]

ChatGPT 5.5 Heavy thinking 1

The best all-`n` formula I see is an exact finite ordering sum, not a simpler special-function closed form.

MathWorld defines graph likelihood by adding one vertex at a time, choosing `k` uniformly from `{0,...,n-1}`, then choosing the `k` neighbors uniformly; it also lists the hypercube values `1, 1/2, 1/36, 11/40642560, ...`. The Banerji--Mansour--Severini paper gives closed forms for some families and leaves computational complexity open, so I would not assume a simple hypercube closed form exists. ([MathWorld][1])

Let

```text
V_d = {0,1}^d,   N = 2^d.
```

For an ordering `sigma = (x_1,...,x_N)` of `V_d`, define

```text
b_i(sigma) = #{j < i : HammingDistance[x_i, x_j] == 1}.
```

Then

```text
L(Q_d) =
  1/(2^d d!) Sum[
    Product[1/(i Binomial[i - 1, b_i(sigma)]), {i, 2, 2^d}],
    {sigma, permutations of V_d}
  ].
```

Equivalently,

```text
L(Q_d) =
  1/(2^d d! (2^d)!) Sum[
    Product[1/Binomial[i - 1, b_i(sigma)], {i, 2, 2^d}],
    {sigma, permutations of V_d}
  ].
```

Reason: for a fixed vertex birth ordering, at step `i` the new vertex must choose exactly its `b_i` earlier hypercube neighbors, which has probability

```text
1/(i Binomial[i - 1, b_i]).
```

Summing over birth orderings gives labeled histories, and division by

```text
|Aut(Q_d)| = 2^d d!
```

passes to the unlabeled graph.

Executable WL check:

```wl
ClearAll[HypercubeLikelihoodExact];

HypercubeLikelihoodExact[d_Integer?NonNegative] := Module[
  {n = 2^d, neigh, verticesInMask, f, full},

  neigh = Table[
    Table[BitXor[v, 2^j], {j, 0, d - 1}],
    {v, 0, 2^d - 1}
  ];

  verticesInMask[mask_Integer] :=
    Select[Range[0, n - 1], BitGet[mask, #] == 1 &];

  f[0] = 1;

  f[mask_Integer?Positive] := f[mask] = Module[{m = DigitCount[mask, 2, 1]},
    Total[
      Table[
        With[{prev = BitClear[mask, v]},
          f[prev]/(
            m Binomial[
              m - 1,
              Count[neigh[[v + 1]], u_ /; BitGet[prev, u] == 1]
            ]
          )
        ],
        {v, verticesInMask[mask]}
      ]
    ]
  ];

  full = 2^n - 1;
  f[full]/(n Factorial[d])
];

Table[HypercubeLikelihoodExact[d], {d, 0, 4}]
```

This returns

```wl
{1, 1/2, 1/36, 11/40642560,
 6585751453088443/7344669054992151532929723924480000000000}
```

matching your GraphData values.

[1]: https://mathworld.wolfram.com/GraphLikelihood.html "Graph Likelihood -- from Wolfram MathWorld"

KC

DeleteCases[Flatten[Table[{{m,n},GraphData[{"KC",{m,n}},"Likelihood"],XXX},{n,3,10},{m,10}],1],{_,x_,x_}]

Keller

Entity["Graph",{"Keller",n}]["Likelihood"]

seq=Table[GraphData[{"Keller",n},"Likelihood"],{n,5}]

King n×n

seq=Table[GraphData[{"King",{n,n}},"Likelihood"],{n,10}]

King m×n

Quiet[Sort[DeleteCases[Flatten[Table[{{m,n},GraphData[{"King",{m,n}},"Likelihood"],XXX},{n,20},{m,n}],1],{_,x_,x_}|{_,_GraphData,_}]]]

Kneser

({#1,q=GraphData[#1,"NotationRules","Kneser"],XXX,GraphData[#1,"Likelihood"]}&)/@GraphData["Kneser"]

Knight n×n

Entity["Graph",{"Knight",{n,n}}]["Likelihood"]

seq=Table[GraphData[{"Knight",{n,n}},"Likelihood"],{n,20}]

FindSequenceFunction[DeleteMissing@seq,n]

Knight m×n

Entity["Graph",{"Knight",{m,n}}]["Likelihood"]

KP

Quiet[DeleteCases[Flatten[Table[{{m,n},GraphData[{"KP",{m,n}},"Likelihood"],XXX},{n,10},{m,10}],1],{_,x_,x_}|{_,_GraphData,_}]]

Ladder

Entity["Graph",{"Ladder",n}]["Likelihood"]

seq=Table[GraphData[{"Ladder",n},"Likelihood"],{n,20}]

FindSequenceFunction[DeleteMissing@seq,n]

LadderRung

A394956/A397599

seq=Table[GraphData[{"LadderRung",n},"Likelihood"],{n,20}]

SeriesCoefficient[InverseErf[Sqrt[2/Pi] z]^2, {z, 0, 2 n}]/(2 n - 1)!

Table[((SeriesCoefficient[((InverseErf[(Sqrt[(2/π)]) z])^2),{z,0,2 n}])/((2 n-1)!)),{n,20}]

Bell-polynomial version, avoiding SeriesCoefficient of an inverse function:

aBell[n_Integer?Positive]:=If[n==1,1/2,Module[{r=n-1},Sum[Binomial[-2 n,k] k! BellY[r,k,Table[(-1)^j/(2 j+1),{j,r-k+1}]],{k,1,r}]/(2^n n (2 n-1)! r!)]]

Table[aBell[n],{n,20}]

Lagrange–Bürmann:

a[n_Integer?Positive]:=SeriesCoefficient[Hypergeometric1F1[1/2,3/2,-u]^(-2 n),{u,0,n-1}]/(2^n n (2 n-1)!);

Table[a[n],{n,20}]

Computation

Print[{#,GraphLikelihood[GraphData[#]]//AbsoluteTiming}]&/@SortBy[GraphData["LadderRung"],GraphData[#,"V"]&];

Closed form

SeriesCoefficient[InverseErf[Sqrt[2/Pi] z]^2,{z,0,2 n}]/(2 n-1)!

Table[%,{n,20}]

ChatGPT 5.5 Heavy thinking 1

Yes. For `{"LadderRung", n}`, MathWorld’s convention is the graph `n P_2`, the disjoint union of `n` copies of `P_2`, so it has `2 n` vertices and `n` isolated edges. MathWorld’s Graph Likelihood page already gives the general isolated-edge formula; specializing to `N = 2 n`, `s = n` gives exactly your sequence. ([MathWorld][1])

For `n >= 1`:

```wl
LadderRungLikelihoodClosed[n_Integer?Positive] :=
  Sum[
    Product[(i[[j]] - (2 j - 1))/(i[[j]] - 1), {j, n}],
    {i, Subsets[Range[2, 2 n], {n}]}
  ]/Factorial[2 n]
```

More efficient recurrence form:

```wl
ClearAll[isolatedEdgeLikelihoodMass, LadderRungLikelihood];

isolatedEdgeLikelihoodMass[m_Integer?Positive, s_Integer?NonNegative] :=
  isolatedEdgeLikelihoodMass[m, s] = Which[
    s == 0, 1,
    2 s > m, 0,
    m == 1, 0,
    True,
      isolatedEdgeLikelihoodMass[m - 1, s] +
        (m - 2 s + 1)/(m - 1) isolatedEdgeLikelihoodMass[m - 1, s - 1]
  ];

LadderRungLikelihood[n_Integer?Positive] :=
  isolatedEdgeLikelihoodMass[2 n, n]/Factorial[2 n]
```

Here `isolatedEdgeLikelihoodMass[m, s]` is `m!` times the likelihood of the graph consisting of `s` isolated edges and `m - 2 s` isolated vertices.

Verification against your available GraphData values:

```wl
Table[LadderRungLikelihood[n], {n, 19}] ===
  Table[GraphData[{"LadderRung", n}, "Likelihood"], {n, 19}]
```

This should return `True`.

The currently missing `n = 20` value is:

```wl
7920018531190455855677535969131/
30273338299480073565463033645514572000429394320538625017078887219200000000000000000
```

Proof sketch: in the Banerji--Mansour--Severini likelihood process, to build the graph `H[m,s] = s P_2 + (m - 2 s) K_1`, the new vertex can only either be isolated, coming from `H[m - 1, s]`, or attach to exactly one previously isolated vertex, coming from `H[m - 1, s - 1]`. Thus

```text
L[m,s] = L[m - 1,s]/m + ((m - 2 s + 1)/(m (m - 1))) L[m - 1,s - 1].
```

Multiplying by `m!` gives the recurrence above, and unrolling it gives the indexed-sum closed form. The Graph Likelihood definition and the isolated-edge formula are given on MathWorld; GraphData’s docs state that `GraphData[entity, property]` returns the specified graph property value. ([MathWorld][2])

[1]: https://mathworld.wolfram.com/LadderRungGraph.html "Ladder Rung Graph -- from Wolfram MathWorld"
[2]: https://mathworld.wolfram.com/GraphLikelihood.html "Graph Likelihood -- from Wolfram MathWorld"

ChatGPT 5.5 Heavy thinking 2

Yes: there is a much more compact coefficient-extraction closed form.

For `n >= 1`,

```wl
GraphData[{"LadderRung", n}, "Likelihood"] ==
  SeriesCoefficient[
    InverseErf[Sqrt[2/Pi] z]^2,
    {z, 0, 2 n}
  ]/(2 n - 1)!
```

So the closed form is

```text
L(n P_2) = [z^(2 n)] InverseErf[Sqrt[2/Pi] z]^2 / (2 n - 1)!
```

Equivalently,

```text
InverseErf[Sqrt[2/Pi] z]^2 =
  Sum[(2 n - 1)! L(n P_2) z^(2 n), {n, 1, Infinity}].
```

This is not a simple product/binomial/gamma closed form, but it is a genuine one-variable generating-function closed form and avoids the `n`-fold sum.

Provenance: MathWorld defines graph likelihood by the Banerji--Mansour--Severini vertex-addition process and gives the finite-sum formula for `L(n P_2)`; MathWorld’s Ladder Rung Graph page identifies the ladder rung graph as `n P_2`. ([MathWorld][1])

Reusable WL:

```wl
ClearAll[LadderRungLikelihoodClosed];

LadderRungLikelihoodClosed[n_Integer?Positive] :=
  SeriesCoefficient[
    InverseErf[Sqrt[2/Pi] z]^2,
    {z, 0, 2 n}
  ]/(2 n - 1)!
```

Verification:

```wl
Table[LadderRungLikelihoodClosed[n], {n, 19}] ===
  Table[GraphData[{"LadderRung", n}, "Likelihood"], {n, 19}]
```

The `n = 20` value from this formula is

```wl
7920018531190455855677535969131/
30273338299480073565463033645514572000429394320538625017078887219200000000000000000
```

Sketch of derivation. Let `G[m, s]` be the graph with `s` isolated edges and `m - 2 s` isolated vertices, and set

```text
A[m, s] = m! L(G[m, s]).
```

The isolated-edge recurrence is

```text
A[m, s] = A[m - 1, s] + (m - 2 s + 1)/(m - 1) A[m - 1, s - 1).
```

Now set `D[m, s] = (m - 1)! A[m, s]`, and reindex by the number `r = m - 2 s` of isolated vertices. If

```text
P_m(y) = Sum[E[m, r] y^r, r >= 0],
```

then

```text
P_1(y) = y,
P_(m + 1)(y) = D[P_m(y), y] + m y P_m(y).
```

Solving the exponential generating function PDE gives

```text
Sum[P_m(0) t^m/m!, {m, 1, Infinity}]
  = InverseErf[Sqrt[2/Pi] t]^2.
```

Since `P_(2 n)(0) = (2 n)! (2 n - 1)! L(n P_2)`, the coefficient formula follows.

[1]: https://mathworld.wolfram.com/GraphLikelihood.html "Graph Likelihood -- from Wolfram MathWorld"

ChatGPT 5.5 heavy thinking 3

Right: **probably no useful single-term closed form** in the usual gamma/Pochhammer/hypergeometric sense.

What we can get rigorously is a **Lagrange-Bürmann coefficient form** that removes `InverseErf`, but it is still a coefficient extraction:

```wl
LadderRungLikelihood[n_Integer?Positive] :=
  SeriesCoefficient[
    Sum[(-1)^j t^j/(j! (2 j + 1)), {j, 0, n - 1}]^(-2 n),
    {t, 0, n - 1}
  ]/(2^n n (2 n - 1)!)
```

This is equivalent to

```text
L(n P_2) =
  1/(2^n n (2n - 1)!) [t^(n - 1)]
    (Sum[(-1)^j t^j/(j! (2j + 1)), {j, 0, Infinity}])^(-2n).
```

That comes directly from Lagrange inversion applied to

```text
z = Sqrt[2] Integrate[Exp[-u^2], {u, 0, y}],
y = InverseErf[Sqrt[2/Pi] z].
```

The DLMF treats inverse-erf power-series coefficients by recurrence, and MathWorld/OEIS likewise list recurrence/series data rather than a hypergeometric closed form, which is a strong clue that no standard compact closed form is known. ([DLMF][1])

A fully explicit finite partition/Bell-polynomial form is possible, but I would not call it an improvement:

```wl
ClearAll[LadderRungLikelihoodBell];

LadderRungLikelihoodBell[n_Integer?Positive] :=
  Sum[
    (-1)^k Pochhammer[2 n, k] *
      BellY[n - 1, k, Table[(-1)^j/(2 j + 1), {j, n - 1}]],
    {k, 0, n - 1}
  ]/(2^n n (2 n - 1)! (n - 1)!)
```

with the caveat that for `n == 1`, depending on WL version, you may want to special-case `BellY[0,0,{}]`:

```wl
LadderRungLikelihoodBell[1] = 1/2;
```

So my conclusion would be:

```text
No simple known hypergeometric/gamma closed form appears to exist.
The cleanest exact form is the InverseErf coefficient form; the cleanest
InverseErf-free form is the Lagrange-Bürmann coefficient form above.
```

For a GraphData rule, I would probably store the compact version:

```wl
SeriesCoefficient[
  InverseErf[Sqrt[2/Pi] z]^2,
  {z, 0, 2 n}
]/(2 n - 1)!
```

rather than the Bell-polynomial expansion, because it is much clearer and less error-prone.

[1]: https://dlmf.nist.gov/7.17 "DLMF: §7.17 Inverse Error Functions ‣ Properties ‣ Chapter 7 Error Functions, Dawson’s and Fresnel Integrals"

Codex 5.5 High

The n-rung ladder-rung graph is the matching on n edges. Let A(m, s) be m! times the likelihood of a graph with s isolated edges and m - 2 s isolated vertices. Considering the last vertex gives A(m, s) = A(m - 1, s) + (m - 2 s + 1) A(m - 1, s - 1)/(m - 1). The perfect-matching terms of this recurrence have exponential generating function InverseErf[Sqrt[2/Pi] z]^2, hence the likelihood of n isolated edges is SeriesCoefficient[InverseErf[Sqrt[2/Pi] z]^2, {z, 0, 2 n}]/(2 n - 1)!.

ChatGPT 5.5 Pro Standard

For the n-rung ladder-rung graph, equivalently the matching with n edges, write

A_n = [z^(2 n)] InverseErf[Sqrt[2/Pi] z]^2/(2 n - 1)!.

Set x = z^2 and u = InverseErf[Sqrt[2/Pi] z]^2. Then z = Sqrt[Pi/2] Erf[Sqrt[u]], hence

x = 2 u Hypergeometric1F1[1/2, 3/2, -u]^2.

Therefore u is the compositional inverse of 2 u Hypergeometric1F1[1/2, 3/2, -u]^2, and Lagrange-Buermann inversion gives

A_n = SeriesCoefficient[Hypergeometric1F1[1/2, 3/2, -u]^(-2 n), {u, 0, n - 1}]/(2^n n (2 n - 1)!)

for n >= 1. Equivalently,

A_n = Derivative[n - 1][Function[u, Hypergeometric1F1[1/2, 3/2, -u]^(-2 n)]][0]/(2^n n (2 n - 1)! (n - 1)!).

Since Hypergeometric1F1[1/2, 3/2, -u] = Sum[(-1)^j u^j/(j! (2 j + 1)), {j, 0, Infinity}], the same coefficient can also be written with partial Bell polynomials. The MathWorld finite-sum form is

A_n = 1/(2 n)! Sum[Product[(i_j - (2 j - 1))/(i_j - 1), {j, 1, n}], 2 <= i_1 < i_2 < ... < i_n <= 2 n],

where the last display is shorthand for summing over all increasing n-tuples selected from {2,...,2 n}.

LindgrenSousselier

seq=Table[GraphData[{"LindgrenSousselier",n},"Likelihood"],{n,11}]

LucasCube

seq=Table[GraphData[{"LucasCube",n},"Likelihood"],{n,15}]

MengerSponge

seq=Table[GraphData[{"MengerSponge",n},"Likelihood"],{n,3}]

MoebiusLadder

Entity["Graph",{"MoebiusLadder",n}]["Likelihood"]

seq=Table[GraphData[{"MoebiusLadder",n},"Likelihood"],{n,3,25}]

Mycielski

Entity["Graph",{"Mycielski",n}]["Likelihood"]

seq=Table[GraphData[{"Mycielski",n},"Likelihood"],{n,11}]

Necklace

seq=Table[GraphData[{"Necklace",n},"Likelihood"],{n,10}]

Odd

Entity["Graph",{"Odd",n}]["Likelihood"]

seq=Table[GraphData[{"Odd",n},"Likelihood"],{n,7}]

Paley

({#1,q=GraphData[#1,"NotationRules","Paley"],XXX,GraphData[#1,"Likelihood"]}&)/@GraphData["Paley"]

Pan

seq=Table[GraphData[{"Pan",n},"Likelihood"],{n,3,20}]

Path

Entity["Graph",{"Path",n}]["Likelihood"]

seq=Table[GraphData[{"Path",n},"Likelihood"],{n,20}]

FindSequenceFunction[DeleteMissing@seq,n]

PathComplement

seq=Table[GraphData[{"PathComplement",n},"Likelihood"],{n,20}]

Peisert

({#1,q=GraphData[#1,"NotationRules","Peisert"],XXX,GraphData[#1,"Likelihood"]}&)/@GraphData["Peisert"]

Pell

seq=Table[GraphData[{"Pell",n},"Likelihood"],{n,9}]

PlummerToft

seq=Table[GraphData[{"PlummerToft",n},"Likelihood"],{n,20}]

Prism

Entity["Graph",{"Prism",n}]["Likelihood"]

seq=Table[GraphData[{"Prism",n},"Likelihood"],{n,3,25}]

Queen n×n

seq=Table[GraphData[{"Queen",{n,n}},"Likelihood"],{n,10}]

Queen m×n

Quiet[Sort[DeleteCases[Flatten[Table[{{m,n},GraphData[{"Queen",{m,n}},"Likelihood"],XXX},{n,20},{m,n}],1],{_,x_,x_}|{_,_GraphData,_}]]]

Rook n×n

seq=Table[GraphData[{"Rook",{n,n}},"Likelihood"],{n,10}]

Rook m×n

Quiet[Sort[DeleteCases[Flatten[Table[{{m,n},GraphData[{"Rook",{m,n}},"Likelihood"],XXX},{n,20},{m,n}],1],{_,x_,x_}|{_,_GraphData,_}]]]

RookComplement n×n

seq=Table[GraphData[{"RookComplement",{n,n}},"Likelihood"],{n,10}]

RookComplement m×n

Quiet[Sort[DeleteCases[Flatten[Table[{{m,n},GraphData[{"RookComplement",{m,n}},"Likelihood"],XXX},{n,20},{m,n}],1],{_,x_,x_}|{_,_GraphData,_}]]]

SierpinskiCarpet

seq=Table[GraphData[{"SierpinskiCarpet",n},"Likelihood"],{n,4}]

SierpinskiGasket

seq=Table[GraphData[{"SierpinskiGasket",n},"Likelihood"],{n,5}]

SierpinskiTetrahedron

seq=Table[GraphData[{"SierpinskiTetrahedron",n},"Likelihood"],{n,6}]

Spoke n×n

seq=Table[GraphData[{"Spoke",{n,n}},"Likelihood"],{n,5}]

StackedBook n×n

seq=Table[GraphData[{"StackedBook",{n,n}},"Likelihood"],{n,10}]

StackedBook m×n

DeleteCases[Flatten[Table[{{m,n},GraphData[{"StackedBook",{m,n}},"Likelihood"],XXX},{n,10},{m,n}],1],{_,x_,x_}]

StackedPrism n×n

seq=Table[GraphData[{"StackedPrism",{n,n}},"Likelihood"],{n,3,5}]

StackedPrism m×n

Quiet[DeleteCases[Flatten[Table[{{m,n},GraphData[{"StackedPrism",{m,n}},"Likelihood"],XXX},{m,3,8},{n,5}],1],{_,x_,x_}|{_,_GraphData,_}]]

Star

A293458/A010796

Entity["Graph",{"Star",n}]["Likelihood"]

seq=Table[GraphData[{"Star",n},"Likelihood"],{n,25}]

FindSequenceFunction[DeleteMissing@seq,n]//Head//Timing

FindGeneratingFunction[DeleteMissing@seq,x]//Head//Timing

Closed form

Table[Sum[i!,{i,0,n-1}],{n,7}]

Sum[k!, {k, 0, n - 1}]

n/(n!)^2 Sum[k!,{k,0,n-1}]

FullSimplify[%,n∈Integers&&n>=1]

Table[Piecewise[{{1/2,n==2}},(n/(((n!))^2))Sum[i!,{i,0,n-1}]],{n,10}]

FullSimplify[(n/(((n!))^2))Sum[i!,{i,0,n-1}],n∈Integers&&n>0]

FullSimplify[#,n∈Integers&&n>0]&/@Apart[%]

(n/(((n!))^2))Sum[i!,{i,0,n-1}]

Table[-((n Subfactorial[-1])/(((n!))^2))+(((((-1))^n)  Subfactorial[-1-n])/((n-1)!)),{n,10}]//FullSimplify

FullSimplify[-((n Subfactorial[-1])/(((n!))^2))+(((((-1))^n)  Subfactorial[-1-n])/((n-1)!)),n∈Integers&&n>0]

Table[-((n Subfactorial[-1])/(((n!))^2))+(((((-1))^n)  Subfactorial[-1-n])/((n-1)!)),{n,25}]//FunctionExpand//FullSimplify

Computation

Do[Print[{gn={"Star",n},BiplanarGraphQ[GraphData[gn],TimeConstraint->10]//AbsoluteTiming}],{n,25}]

ChatGPT 5.5 Heavy thinking 1

Yes. For GraphData's convention that `{"Star", n}` is the star on `n` vertices, the clean closed form is

```wl
ClearAll[leftFactorial, starLikelihood];

leftFactorial[n_Integer?NonNegative] := Sum[k!, {k, 0, n - 1}];

starLikelihood[n_Integer?Positive] := Piecewise[
  {{1/2, n == 2}},
  n leftFactorial[n]/(n!)^2
]
```

Equivalently,

```wl
L(S_n) = Piecewise[{{1/2, n == 2}}, n/(n!)^2 Sum[k!, {k, 0, n - 1}]]
```

This is exactly the MathWorld/GraphData formula for graph likelihood of `S_n`; MathWorld defines graph likelihood by the vertex-adjoining random process and lists the star formula as `n/(n!)^2 Sum[k!, {k,0,n-1}]`, with the exceptional `n == 2` case. ([MathWorld][1])

A derivation is short. Let `L_n = L(S_n)`. For `n >= 4`, the last-added vertex in `S_n` is either:

* a leaf: previous graph `S_(n-1)`, choose `k = 1`, then choose the unique center, probability `1/(n (n - 1))`;
* the center: previous graph is the empty graph on `n - 1` vertices, whose likelihood is `1/(n - 1)!`, then choose `k = n - 1`, probability `1/n`.

So

```wl
L[n] == L[n - 1]/(n (n - 1)) + 1/n!
```

for `n >= 4`, with `L[3] == 1/3`. Now set

```wl
M[n] = (n!)^2 L[n]/n
```

Then the recurrence becomes

```wl
M[n] == M[n - 1] + (n - 1)!
```

and since `M[3] == 0! + 1! + 2!`, we get

```wl
M[n] == Sum[k!, {k, 0, n - 1}]
```

hence

```wl
L[n] == n Sum[k!, {k, 0, n - 1}]/(n!)^2.
```

The `n == 2` exception is real: generically the leaf/center cases are distinct, but `S_2 == K_2`, so the generic formula would give `1` while the actual likelihood is `1/2`.

A no-explicit-sum rewrite exists using the analytic continuation of `Subfactorial`, but I would not prefer it as the stored form:

```wl
starLikelihoodSubfactorial[n_Integer?Positive] := Piecewise[
  {{1/2, n == 2}},
  ((-1)^n n Subfactorial[-n - 1])/n! -
    (n Subfactorial[-1])/(n!)^2
]
```

That matches the MathWorld rewrite, but it relies on negative-argument `Subfactorial` analytic continuation, whereas the finite left-factorial sum is exact, transparent, and integer-domain natural. Wolfram documents `Subfactorial[n]` as derangements and gives the noninteger continuation via `Gamma[n + 1, -1]/E`. ([reference.wolfram.com][2])

[1]: https://mathworld.wolfram.com/GraphLikelihood.html "Graph Likelihood -- from Wolfram MathWorld"
[2]: https://reference.wolfram.com/mathematica/ref/Subfactorial.html "Subfactorial: Derangement number—Wolfram Documentation"

ChatGPT 5.5 Heavy thinking 2

For integer `n`, yes. The simplest WL form is probably:

```wl
leftFactorial[n_Integer?Positive] := Total[Range[0, n - 1]!]
```

So the star likelihood can be written as:

```wl
starLikelihood[n_Integer?Positive] := Piecewise[
  {{1/2, n == 2}},
  n Total[Range[0, n - 1]!]/(n!)^2
]
```

For symbolic `n`, keep the finite sum:

```wl
Sum[k!, {k, 0, n - 1}]
```

or, if you want it inert in `GraphData`-style output,

```wl
Inactive[Sum][k!, {k, 0, n - 1}]
```

I would **not** use the `Subfactorial` analytic-continuation form as the canonical WL definition, even though MathWorld gives such a rewrite for the left factorial / factorial sum. The finite sum is clearer and avoids relying on negative-index continuation of `Subfactorial`. MathWorld notes the ambiguity of “left factorial” terminology and gives the factorial-sum definition `Sum[k!, {k,0,n-1}]`. ([mathworld.wolfram.com][1])

[1]: https://mathworld.wolfram.com/LeftFactorial.html?utm_source=chatgpt.com "Left Factorial -- from Wolfram MathWorld"

Sun

seq=Table[GraphData[{"Sun",n},"Likelihood"],{n,3,20}]

Sunlet

seq=Table[GraphData[{"Sunlet",n},"Likelihood"],{n,3,20}]

Tetrahedral

seq=Table[GraphData[{"Tetrahedral",n},"Likelihood"],{n,6,10}]

TorusGrid n×n

seq=Table[GraphData[{"TorusGrid",{n,n}},"Likelihood"],{n,3,10}]

TorusGrid m×n

Quiet[Sort[DeleteCases[Flatten[Table[{{m,n},GraphData[{"TorusGrid",{m,n}},"Likelihood"],XXX},{n,3,20},{m,3,n}],1],{_,x_,x_}|{_,_GraphData,_}]]]

Transposition

Entity["Graph",{"Transposition",n}]["Likelihood"]

seq=Table[GraphData[{"Transposition",n},"Likelihood"],{n,6}]

Trapezohedron

(Entity[(RowDefault["n", "\[Hyphen]trapezohedral graph"]), Entity["Graph",{"Trapezohedron",n}], "Entity[\"Graph\", {\"Trapezohedron\", n}]", "graph"])["Likelihood"]

Triangular

seq=Table[GraphData[{"Triangular",n},"Likelihood"],{n,2,10}]

TriangularGrid

seq=Table[GraphData[{"TriangularGrid",n},"Likelihood"],{n,10}]

TriangularHoneycombAcuteKnight

seq=Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"Likelihood"],{n,20}]

TriangularHoneycombBishop

seq=Table[GraphData[{"TriangularHoneycombBishop",n},"Likelihood"],{n,20}]

TriangularHoneycombObtuseKnight

seq=Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"Likelihood"],{n,20}]

TriangularHoneycombQueen

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"Likelihood"],{n,20}]

TriangularHoneycombRook

seq=Table[GraphData[{"TriangularHoneycombRook",n},"Likelihood"],{n,20}]

TriangularSnake

seq=Table[GraphData[{"TriangularSnake",n},"Likelihood"],{n,1,20,2}]

TruncatedSquareLattice n×n

seq=Table[GraphData[{"TruncatedSquareLattice",{n,n}},"Likelihood"],{n,10}]

TruncatedSquareLattice m×n

Quiet[Sort[DeleteCases[Flatten[Table[{{m,n},GraphData[{"TruncatedSquareLattice",{m,n}},"Likelihood"],XXX},{n,20},{m,n}],1],{_,x_,x_}|{_,_GraphData,_}]]]

Web

seq=Table[GraphData[{"Web",n},"Likelihood"],{n,3,20}]

Wheel

Entity["Graph",{"Wheel",n}]["Likelihood"]

seq=Table[GraphData[{"Wheel",n},"Likelihood"],{n,4,20}]

FindSequenceFunction[DeleteMissing@seq,n-3]//Head//Timing

FindGeneratingFunction[DeleteMissing@seq,x]//Head//Timing

WheelComplement

seq=Table[GraphData[{"WheelComplement",n},"Likelihood"],{n,4,20}]

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"Likelihood"],{n,2,10}]

WhiteBishop m×n

Quiet[Sort[DeleteCases[Flatten[Table[{{m,n},GraphData[{"WhiteBishop",{m,n}},"Likelihood"],XXX},{n,20},{m,n}],1],{_,x_,x_}|{_,_GraphData,_}]]]

WhiteCamel n×n

seq=Table[GraphData[{"Bishop",{n,n}},"Likelihood"],{n,{5}}]

Zebra n×n

seq=Table[GraphData[{"Zebra",{n,n}},"Likelihood"],{n,20}]

Zebra m×n

Quiet[Sort[DeleteCases[Flatten[Table[{{m,n},GraphData[{"Zebra",{m,n}},"Likelihood"],XXX},{n,20},{m,n}],1],{_,x_,x_}|{_,_GraphData,_}]]]

Compute for n edges

Matching with n edges

nedges=Select[GraphData[All],MatchQ[DeleteCases[Tally[GraphData[#,"Degrees"]],{0,_}],{{1,_}}]&]

(#->GraphData[#])&/@nedges

SortBy[nedges,GraphData[#,"M"]&]

LikelihoodNEdges[n_,s_]:=Module[{a,i,solns},
a=Array[i,s];
solns=a/.{ToRules[Reduce[Inequality[2,LessEqual,Sequence@@Riffle[a,Less],LessEqual,n],a,Integers]]};
Total[Function[f,Times@@MapIndexed[((#+1-2#2[[1]])/(#-1))&,f]]/@solns]/n!
]

SolutionSet1[n_,s_]:=Module[{a,i,solns},
a=Array[i,s];
solns=a/.{ToRules[Reduce[Inequality[2,LessEqual,Sequence@@Riffle[a,Less],LessEqual,n],a,Integers]]}
]

SolutionSet2[n_,s_]:=Module[{a,i,solns},
a=Array[i,s];
Flatten[Table[a,{i[1],2,n-s+1},Evaluate[Sequence@@Table[{i[k],i[k-1]+1,n-s+k},{k,2,s}]]],s-1]
]

s1=SolutionSet1[9,4]

s2=SolutionSet2[9,4]

s1==s2

LikelihoodNEdgesReduce

Print[{#,GraphData[#,{"V","M"}],LikelihoodNEdges@@GraphData[#,{"V","M"}]//Timing,GraphData[#,"Likelihood"]}]&/@Take[SortBy[nedges,GraphData[#,"M"]&],All];

LikelihoodNEdgesTable (faster)

LikelihoodNEdges2[n_,s_]:=Module[{a,i,solns},
a=Array[i,s];
solns=Flatten[Table[a,{i[1],2,n-s+1},Evaluate[Sequence@@Table[{i[k],i[k-1]+1,n-s+k},{k,2,s}]]],s-1];
Total[Function[f,Times@@MapIndexed[((#+1-2#2[[1]])/(#-1))&,f]]/@solns]/n!
]

Print[{#,GraphData[#,{"V","M"}],LikelihoodNEdges2@@GraphData[#,{"V","M"}]//Timing,GraphData[#,"Likelihood"]}]&/@Cases[SortBy[nedges,GraphData[#,"M"]&],{"LadderRung",_}];

LikelihoodNEdgesLoop (still faster)

LikelihoodNEdgesLoop[n_,s_]:=Module[{i,k,sum=0},
Do[sum+=Times@@MapIndexed[((#+1-2#2[[1]])/(#-1))&,Array[i,s]],{i[1],2,n-s+1},Evaluate[Sequence@@Table[{i[k],i[k-1]+1,n-s+k},{k,2,s}]]
];
sum/n!
]

LikelihoodNEdgesLoop@@GraphData[{"LadderRung",11},{"V","M"}]//Timing

Print[{#,GraphData[#,{"V","M"}],LikelihoodNEdges2@@GraphData[#,{"V","M"}]//Timing,GraphData[#,"Likelihood"]}]&/@Cases[SortBy[nedges,GraphData[#,"M"]&],{"LadderRung",_}];

LikelihoodNEdgesLoopCompiled

cf=Compile[{{i,_Integer}},Times@@MapIndexed[((#+1-2#2[[1]])/(#-1))&,i]]

LikelihoodNEdgesLoopCompiled[n_,s_]:=Module[{i,k,sum=0},
Do[sum+=cf@Array[i,s],{i[1],2,n-s+1},Evaluate[Sequence@@Table[{i[k],i[k-1]+1,n-s+k},{k,2,s}]]
];
sum/n!
]

LikelihoodNEdgesLoopCompiled@@GraphData[{"LadderRung",2},{"V","M"}]//Timing

Print[{#,GraphData[#,{"V","M"}],LikelihoodNEdges2@@GraphData[#,{"V","M"}]//Timing,GraphData[#,"Likelihood"]}]&/@Cases[SortBy[nedges,GraphData[#,"M"]&],{"LadderRung",_}];

LikelihoodNEdgesParallelSum (can’t compile)

LikelihoodNEdgesParallelSum[n_,s_]:=Module[{i,k},
ParallelSum[Times@@MapIndexed[((#+1-2#2[[1]])/(#-1))&,Array[i,s]],{i[1],2,n-s+1},Evaluate[Sequence@@Table[{i[k],i[k-1]+1,n-s+k},{k,2,s}]]
]/n!
]

LikelihoodNEdgesParallelSum@@GraphData[{"LadderRung",6},{"V","M"}]//Timing

LikelihoodNEdges2[n_,s_]:=Module[{a,i,solns},
a=Array[i,s];
solns=Flatten[Table[a,{i[1],2,n-s+1},Evaluate[Sequence@@Table[{i[k],i[k-1]+1,n-s+k},{k,2,s}]]],s-1];
Total[Function[f,Times@@MapIndexed[((#+1-2#2[[1]])/(#-1))&,f]]/@solns]/n!
]

Print[{#,GraphData[#,{"V","M"}],LikelihoodNEdges2@@GraphData[#,{"V","M"}]//Timing,GraphData[#,"Likelihood"]}]&/@Cases[SortBy[nedges,GraphData[#,"M"]&],{"LadderRung",_}];

Matching with 1 edge

oneedge=Select[GraphData[All],DeleteCases[Tally[GraphData[#,"Degrees"]],{0,_}]==={{1,2}}&]

(#->GraphData[#])&/@oneedge

{#,GraphData[#,"Likelihood"],With[{n=GraphData[#,"V"]},((n-1)/(n!))]}&/@twoedges

Matching with 2 edges

twoedges=Select[GraphData[All],DeleteCases[Tally[GraphData[#,"Degrees"]],{0,_}]==={{1,4}}&]

GraphData/@twoedges

(1/(n!))Sum[-1-i+n+2 PolyGamma[0,i]-i PolyGamma[0,i]+i PolyGamma[0,1+i]-2 PolyGamma[0,n],{i,2,n-1}]//FullSimplify

FullSimplify[((6-7 n+(n^2)+4 (EulerGamma+PolyGamma[0,n]))/(2 n!)),n∈Integers&&n>0]

Factor[6-7 n+(n^2)]

(( (n-1)(n-6)+4 (EulerGamma+PolyGamma[0,n]))/(2 n!))/.n->5

{#,With[{n=GraphData[#,"V"]},((6-7 n+(n^2)+4 (EulerGamma+PolyGamma[0,n]))/(2 n!))]}&/@twoedges

Table[((6-7 n+(n^2)+4 (EulerGamma+PolyGamma[0,n]))/(2 n!)),{n,10}]

Table[(((n-1)(n-6)+4 HarmonicNumber[n-1])/(2 n!)),{n,10}]

FullSimplify[(((n-1)(n-6)+4 HarmonicNumber[n-1])/(2 n!))]

Matching with 3 edges

edges3=Select[GraphData[All],DeleteCases[Tally[GraphData[#,"Degrees"]],{0,_}]==={{1,6}}&]

GraphData/@edges3

With[{n=6,s=3},(1/(n!))Sum[((i2-3)/(i2-1))((i3-5)/(i3-1)),{i1,2,n-s+1},{i2,i1+1,n-s+2},{i3,i2+1,n}]]//Timing

GraphData[{"LadderRung",3},"Likelihood"]

With[{n=18,s=3},(1/(n!))Sum[((i2-3)/(i2-1))((i3-5)/(i3-1)),{i1,2,n-s+1},{i2,i1+1,n-s+2},{i3,i2+1,n}]]//Timing

GraphData[{"Fiveleaper",{3,6}},"Likelihood"]

(1/(n!))Sum[((i2-3)/(i2-1))((i3-5)/(i3-1)),{i1,2,n-s+1},{i2,i1+1,n-s+2},{i3,i2+1,n}]//FullSimplify//Timing

With[{s=3},Table[Sum[((i2-3)/(i2-1))((i3-5)/(i3-1)),{i1,2,n-s+1},{i2,i1+1,n-s+2},{i3,i2+1,n}],{n,10}]]

s==3

Sum[((i2-3)/(i2-1))((i3-5)/(i3-1)),{i3,i2+1,n}]//FullSimplify

Sum[-(((-3+i2) (i2-n-4 PolyGamma[0,i2]+4 PolyGamma[0,n]))/(-1+i2)),{i2,i1+1,n-1}]//Timing

Apart[-(((-3+i2) (i2-n-4 PolyGamma[0,i2]+4 PolyGamma[0,n]))/(-1+i2))]

Sum[(((-3+i2) (i2-n-4 PolyGamma[0,i2]))/(-1+i2)),{i2,i1+1,n-1}]

Sum[((4 (-3+i2) PolyGamma[0,n])/(-1+i2)),{i2,i1+1,n-1}]//FullSimplify

Sum[((i2-3)/(i2-1))((i3-5)/(i3-1)),{i1,2,n-s+1},{i2,i1+1,n-s+2},{i3,i2+1,n}]/

Distributions of  values

Length/@(likelihood=Prepend[Table[Get[FileNameJoin[{$GraphDataDirectory,"Nodes","Likelihood","Likelihoods_"<>ToString[n]<>".m"}]],{n,2,10}],{1}])//Timing

Table

n=12 computation completed Aug 2, 2026 around 7:50 pm

table={1->{"Minimum"->1,"MinimumGraphs"->{"@"},"Maximum"->1,"MaximumGraphs"->{"@"}},2->{"Minimum"->1/2,"MinimumGraphs"->{"A?","A_"},"Maximum"->1/2,"MaximumGraphs"->{"A?","A_"}},3->{"Minimum"->1/6,"MinimumGraphs"->{"B?","Bw"},"Maximum"->1/3,"MaximumGraphs"->{"BG","BW"}},4->{"Minimum"->1/36,"MinimumGraphs"->{"C`","Cr"},"Maximum"->13/72,"MaximumGraphs"->{"CB","CN"}},5->{"Minimum"->1/270,"MinimumGraphs"->{"DqK"},"Maximum"->307/4320,"MaximumGraphs"->{"D@[","DB{"}},6->{"Minimum"->23/259200,"MinimumGraphs"->{"Es\\o","EwCW"},"Maximum"->1927/86400,"MaximumGraphs"->{"E?Lw","E@^w"}},7->{"Minimum"->319/54432000,"MinimumGraphs"->{"F?~v_","FwCWw"},"Maximum"->39211/6804000,"MaximumGraphs"->{"F?GYw","FAl~w"}},8->{"Minimum"->319/15240960000,"MinimumGraphs"->{"Gs`zro","G~?GW["},"Maximum"->27797639/22861440000,"MaximumGraphs"->{"G??OX[","GAl~~{"}},9->{"Minimum"->76441/115221657600000,"MinimumGraphs"->{"H?B~vrw","H~?GW[N"},"Maximum"->15403847/64012032000,"MaximumGraphs"->{"H???Oge","Hhuz~~~"}},10->{"Minimum"->76441/145179288576000000,"MinimumGraphs"->{"IsaBzx{^?","I~{?GKF@w"},"Maximum"->219903017/4938071040000,"MaximumGraphs"->{"I????GICo","Ihuz~~~~w"}},11->{"Minimum"->20692621/2012184939663360000000,"MinimumGraphs"->{"J~{?GKF@wN_","J??F~z{~Fw?"},"Maximum"->7472883629/1140694410240000,"MaximumGraphs"->{"J?????A@OR?","Jhuz~~~~~~_"}},
12->{"Minimum"->20692621/11155553305493667840000000,"Maximum"->18096017946691/17566693917696000000,"MinimumGraphs"->{"KsaCB|}^b{No","K~~w?CB?wF_^"},"MaximumGraphs"->{"K????C?@?PAE","Kh~u||~~~~~~"}}
};

{"Minimum","Maximum"}/.{"Minimum"->1,"MinimumGraphs"->{"@"},"Maximum"->1,"MaximumGraphs"->{"@"}}

TextGrid[{#,Sequence@@({"Minimum","Maximum"}/.#2)}&@@@table,Alignment->Center,Dividers->All]

Minimum

A234234/A234235

Transpose@NumeratorDenominator["Minimum"/.table[[All,2]]]

Maximum

A234236/A234237

Transpose@NumeratorDenominator["Maximum"/.table[[All,2]]]

Plots of all values

GraphicsGrid[
Partition[ListPlot[Sort[likelihood[[#]]],PlotRange->All,PlotLabel->Style[n==#,FontFamily->"Times"],TicksStyle->FontFamily->"Times"]&/@Range[2,9],UpTo[3]],ImageSize->1000
]

Total

Total[likelihood,{2}]//Timing

Mean

https://oeis.org/A000088

(μ=Mean/@likelihood)//Timing

Through[{Numerator,Denominator}[μ]]

Min

New

"Minimum"/.table[[All,2]]

A234234/A234235

Transpose@NumeratorDenominator[%]

TextGrid[
{#,"Minimum"/.#2,Function[gs,RecognizeGraph@ImportString[gs,"Graph6"]]/@("MinimumGraphs"/.#2)}&@@@table,
Dividers->All]

Old

min=Min/@likelihood

Through[{Numerator,Denominator}[min]]

PickExtrema[n_,f_]:=Module[{l=likelihood[[n]],m},
m=f[l];
{n,m,Quiet[GraphData[{n,#},"#"]&/@Flatten[Position[l,m]]/.GraphData[x_,_]:>x]}
]

Grid[min=Table[PickExtrema[n,Min],{n,2,10}],Dividers->All,Alignment->{{Right,Center,Left},Automatic}]

Table[{Floor[n/2],Ceiling[n/2]},{n,2,10}]

Table[RecognizeGraph@System`CompleteGraph[{Floor[n/2],Ceiling[n/2]}],{n,2,10}]

Grid[{#[[1]],GraphData/@#[[3]]}&/@min/.GraphData[{n_,k_}]:>Graphs[n][[k]],Dividers->All,Alignment->{{Center,Left},Automatic}]//Quiet

Max

New

"Maximum"/.table[[All,2]]

A234236/A234237

Transpose@NumeratorDenominator[%]

TextGrid[
{#,"Maximum"/.#2,Function[gs,RecognizeGraph@ImportString[gs,"Graph6"]]/@("MaximumGraphs"/.#2)}&@@@table,
Dividers->All]

Old

max=Max/@likelihood

Through[{Numerator,Denominator}[max]]

Grid[max=Table[PickExtrema[n,Max],{n,2,10}],Dividers->All,Alignment->{{Right,Center,Left},Automatic}]

Grid[{#[[1]],GraphData/@#[[3]]}&/@max/.GraphData[{n_,k_}]:>Graphs[n][[k]],Dividers->All,Alignment->{{Center,Left},Automatic}]//Quiet