A245519 Number of alpha-labeled graphs with n edges and at most n vertices.

0, 0, 0, 2, 10, 64, 336, 1872, 11104, 71944, 508032, 3511232, 27192704, 223750464, 1947253504, 17899536448, 173156535168, 1760383827776, 18752453106176, 209034916385472, 2432351796434560, 29509268795249700

Offset

1,4

Links

Table of n, a(n) for n=1..22.

Christian Barrientos, Sarah Minion, On the number of alpha-labeled graphs, Discussiones Mathematicae Graph Theory, to appear.

J. A. Gallian, A dynamic survey of graph labeling, Elec. J. Combin., (2013), #DS6.

David A. Sheppard, The factorial representation of major balanced labelled graphs, Discrete Math., 15(1976), no. 4, 379-388.

Formula

a(n) = Sum_{L=1..n-2} Sum_{i=1..n-1} Product_{k=1..n} d(L,k,i), where

for i < L,

d(L,k) if 1 <= k <= i,

d(L,k,i) ={ d(L,k) - 1 if i < k < n - i,

d(L,k) if n - i <= k <= n;

for i > L + 1,

d(L,k) if 1 <= k <= n - i,

d(L,k,i) ={ d(L,k) - 1 if n - i < k < n - i + L + 2,

d(L,k) if n - i + L + 2 <= k <= n.

k if 1 <= k < m,

d(L,k) ={ L + 1 if m <= k <= M,

n + 1 - k if M < k <= n,

m = min{L + 1, n - L}, M = max{L + 1, n - L}.

Example

For n=4, a(4)=2, there are 2 alpha-labeled graphs with 4 edges and at most 4 vertices.
For n=10, a(10)=71944, there are 71944 alpha-labeled graphs with 10 edges and at most 10 vertices.

Crossrefs

Cf. A241094, A005193.

Sequence in context: A175962 A183165 A129130 * A303483 A186268 A078531

Adjacent sequences: A245516 A245517 A245518 * A245520 A245521 A245522

Keyword

nonn,easy

Author

Sarah Minion and Christian Barrientos, Jul 24 2014

Status

approved