Pierre-Louis Giscard - cp's OEIS frontend

User: Pierre-Louis Giscard

Pierre-Louis Giscard has authored 2 sequences.

A348365 Number of connected realizable graphs on n vertices.

1, 1, 2, 5, 15, 58, 265

Offset: 1

Pierre-Louis Giscard, Oct 15 2021

a(n) is the number of realizable connected unlabelled graphs on n vertices. A realizable graph H is a graph for which there exists a (multi di)graph G such that the vertices of H are exactly the simple cycles of G and two vertices of H share an edge if the corresponding simple cycles in G share at least one vertex. Thus H encodes the "cycle skeleton" of G. Formally, H is the dependency graph of the trace monoid formed by the simple cycles on G equipped with the independency relation that two cycles commute if they are vertex-disjoint.

			For n = 4, a(4) = 5 because out of the 6 unlabelled connected graphs on 4 vertices only 1 is not realizable: the square.

Jean Fromentin, Pierre-Louis Giscard and Théo Karaboghossian, Why walks lead us astray in the study of graphs, arXiv:2110.15618 [math.CO], 2021.
Théo Karaboghossian, Pierre-Louis Giscard and Jean Fromentin, Trace monoids, hike monoids and number theory, slides, WACA (Calais, France 2021).

Compare with A001349 (all graphs), sequence close to A048192.

a(n) is strictly increasing, a(n+1)>a(n) and a(n) grows at least exponentially with n as n->infinity.

A244098 Total number of divisors of all the ordered prime factorizations of an integer.

Original entry on oeis.org

1, 2, 2, 3, 2, 5, 2, 4, 3, 5, 2, 9, 2, 5, 5, 5, 2, 9, 2, 9, 5, 5, 2, 14, 3, 5, 4, 9, 2, 16, 2, 6, 5, 5, 5, 19, 2, 5, 5, 14, 2, 16, 2, 9, 9, 5, 2, 20, 3, 9, 5, 9, 2, 14, 5, 14, 5, 5, 2, 35, 2, 5, 9, 7, 5, 16, 2, 9, 5, 16, 2, 34, 2, 5, 9, 9, 5, 16, 2, 20, 5, 5

Offset: 1

Pierre-Louis Giscard, Jun 20 2014

nonn

a(n) = total number of ordered prime factorizations dividing all possible ordered prime factorizations making up n.
Example: for n = 12; a(12) = 9 because 12 = 2*2*3 = 2*3*2 = 3*2*2 the divisors of which are 1, 2, 3, 2*2, 2*3, 3*2, 2*2*3, 2*3*2, 3*2*2. This makes 9 ordered prime factorizations dividing all those making up 12.
Dirichlet convolution of A008480 with A000012.

			For n = 6; a(6) = 5 because 6 = 2*3 = 3*2, the divisors of which are 1, 2, 3, 2*3, 3*2. This makes 5 ordered prime factorizations dividing all those making up 6.
For n = 12; a(12) = 9 because 12 = 2*2*3 = 2*3*2 = 3*2*2, the divisors of which are 1, 2, 3, 2*2, 2*3, 3*2, 2*2*3, 2*3*2, 3*2*2. This makes 9 ordered prime factorizations dividing all those making up 12.
For n prime, a(n) = 2 because a prime n has a single ordered prime factorization n with divisors 1 and n. This makes two ordered prime factorizations dividing that making up n.

Pierre-Louis Giscard, Table of n, a(n) for n = 1..5000

Cf. A000012, A008480.

f[s_]=Zeta[s]/(1-PrimeZetaP[s]); (* Dirichlet g.f *)
(* or *)
Clear[a, b];
a = Prepend[
   Array[Multinomial @@ Last[Transpose[FactorInteger[#]]] &, 200, 2],
   1];
b = Table[1, {u, 1, Length[a]}];
Table[Sum[If[IntegerQ[p/n], b[[n]] a[[p/n]], 0], {n, 1, p}], {p, 1,
  Length[a]}]

Dirichlet generating function: Zeta(s)/(1-P(s)) with Zeta(s) the Riemann zeta function and P(s) the prime zeta function.

G.f. A(x) satisfies: A(x) = x / (1 - x) + Sum_{k>=1} A(x^prime(k)). - Ilya Gutkovskiy, May 30 2020

cp's OEIS Frontend

User: Pierre-Louis Giscard

A348365 Number of connected realizable graphs on n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula