**Bridged graphs sequence**


$g(n) =$ "Number of simple connected bridged graphs on $n+2$ nodes".


We have $g(n)=1, 3, 10, 52, 351, 3714,\dots$ from [*A052446*](https://oeis.org/A052446).


  

**Number formation sequence**


We also have $f(n) =$ "Largest $N$ such that all numbers $1,\dots, N$ can be made using basic operations $+,-,\times,\div$ and parentheses $(\space)$, given optimal set of $n$ digits (to be defined for each $n$) such that all digits are used exactly once." 


The conjectured solutions are: $f(n)=1, 3, 10, 52, 351$ so far for $n=1,\dots,5$.


The first three values are true and not hard to prove. The second two values are given by:


$f(4)\ge 52$ since (optimal?) digits $d=\{2,3,4,22\}$ can make numbers $1,\dots,52$.


$f(5)\ge 351$ since (optimal?) digits $d=\{3,6,8,12,37\}$ can make numbers $1,\dots,351$, which can be [seen by clicking here](https://pastebin.com/0AAVXCKc). Note that solutions per $N\_0\in[1,N]$ are not necessarily unique.


I conjecture these two are equalities based on computations. That is, I couldn't find a better digit set that would make larger $N$ possible in either case.


  

**Question**


Notice that so far I have a conjecture pattern:


$$f(n)=g(n)$$



> 
> Is this a coincidence or is there a connection between these two problems?
> 
> 
> That is, can we provide arguments for either case?
> 
> 
> 


I don't see a clear connection and would think this is just a coincidence. Can we prove this is just a coincidence? That is, find $n$ and $d$ such that $f(n)\gt g(n)$? Or prove for some $n$ that for every $d$ we have $f(n)\lt g(n)$?


Or is this not a coincidence? Can we provide arguments why could these two problems be connected? It would be amazing if we could translate number formation to graphs and find optimal $d$ for some $n$ with graph theory.


Can we perhaps find $d$ such that $f(6)=3714$, and continue this pattern? My simple brute force `c++` code is too slow to find significant records for $n\ge 6$. The best I have by sampling random digit cases is $f(6)\ge 2200$, so far.


  

**Lower bound on $f(n)$**


It can be shown $f(n)\gt 2^n,n\gt 2$, using $d=\{2^0,2^1,\dots,2^{n-1}\}$. 


But this is not the best lower bound for this digit set. We have:


$f(n)\ge f\_d(n)=1,3,10,26,76,596,2472,\dots$. 


Notice this is a weak lower bound and is not sharp. Example: $f(6)\ge2200\gt f\_d(6)=596$.


Notice $f(n)=f\_d(n)$ for $n\le 3$. Better digit sets might give better bounds for $n\ge 4$.



Number formation and bridged graphs, connection or coincidence?
Coincidence.


$f(n)$ is not larger than the number of expressions on $n$ numbers. The expressions are in bijection with $n$-leaf rooted binary trees, where its non-leaf vertices are labeled with $\{+,-,×,÷\}$ and its leaves are in bijection with the optimal set of digits. The number of such binary trees is $4^{n-1}\text{Catalan}(n-1)n!$, which is $O(\exp(c n\log n))$ for some constant $c$. 


The binary tree $T$ corresponding to a expression $d$ is constructed as follows:


$d$ takes the form $d\_1⊕d\_2$, where $d\_1$ and $d\_2$ are expressions, and $⊕$ is a operator. Label the root of $T$ with $⊕$, construct two subtrees $T\_1$ and $T\_2$ corresponding to $d\_1$ and $d\_2$, respectively. Let $T\_1$ and $T\_2$ be the two children of $T$. [This is a bijection](https://en.wikipedia.org/wiki/Binary_tree#Combinatorics).


The (labeled) binary tree can be determined by the following information: 


* The structure of the binary tree ($\text{Catalan}(n-1)$ types)
* The labels ($4$ choices for each non-leaf node)
* The leaves ($n!$ bijections from the optimal digit set)


So the number of trees is $4^{n-1}\text{Catalan}(n-1)n!$.


But the number of bridged graphs on $n$ vertices is at least the number of graphs on $n/2$ vertices: just connect two graphs with an edge. The number of graphs on $n$ vertices is roughly $2^{\frac{n^2}2}$, which is faster than $\exp(c n\log n)$, so the number of bridged graphs eventually dominates $f(n)$. 


