login
A245519
Number of alpha-labeled graphs with n edges and at most n vertices.
0
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
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
Sequence in context: A175962 A183165 A129130 * A303483 A186268 A078531
KEYWORD
nonn,easy
AUTHOR
STATUS
approved