login
A255908
Triangle read by rows: T(n,L) = number of rho-labeled graphs with n edges whose labeling is bipartite with boundary value L.
0
2, 4, 8, 8, 32, 48, 16, 128, 288, 384, 32, 512, 1728, 3072, 3840, 64, 2048, 10368, 24576, 38400, 46080, 128, 8192, 62208, 196608, 384000, 552960, 645120, 256, 32768, 373248, 1572864, 3840000, 6635520, 9031680, 10321920, 512, 131072, 2239488, 12582912, 38400000, 79626240, 126443520, 165150720, 185794560, 1024, 524288, 13436928, 100663296, 384000000, 955514880, 1770209280, 2642411520, 3344302080, 3715891200
OFFSET
1,1
COMMENTS
A graph with n edges is rho-labeled if there exists a one-to-one mapping from its vertex set to {0,1,...,2n} such that every edge receives as label the absolute difference of its end-vertices and the edge labels are x_1, x_2, ..., x_n where x_i = i or x_i = 2n + 1 - i. A rho-labeling of a bipartite graph is said to be bipartite when the labels of one stable set are smaller than the labels on the other stable set. The largest of the smaller vertex labels is its boundary value.
From Robert G. Wilson v, Jul 05 2015: (Start)
The columns:
T(n, 0) = 2^n,
T(n, 1) = 2^(2n-1),
T(n, 2) = 2^(n+1)*3^(n-2),
T(n, 3) = 3*2^(3n-5),
T(n, 4) = 3*2^(n+3)*5^(n-4),
T(n, 5) = 5*2^(2n-2)*3^(n-4), etc.
The diagonals:
the main, T(n, n-1) = 2^n*n*(n-1!) = 2*A002866,
the second diagonal, T(n, n-2) = 2^n*(n-1)^2*(n-2)! = 4*A014479,
the third diagonal, T(n, n-3) = 2^n*(n-2)^3*(n-3)!,
the k_th diagonal, T(n, n-k) = 2^n*(n-k)^k*(n-k)!, etc.
... (End)
LINKS
Joseph A. Gallian, A dynamic survey of graph labeling, Elec. J. Combin., (2014), #DS6.
FORMULA
For n>=1, 0<=L<=n-1, T(n,L)=(2^n)*(L!)*(L+1)^(n-L).
EXAMPLE
For n=5 and L=1, T(5,1)=(2^5)*(1!)*(1+1)^(5-1)=512.
For n=9 and L=3, T(9,3)=12582912.
Triangle, T, begins:
-----------------------------------------------------------------------------
n\L | 0 1 2 3 4 5 6
----|------------------------------------------------------------------------
1 | 2;
2 | 4, 8;
3 | 8, 32, 48;
4 | 16, 128, 288, 384;
5 | 32, 512, 1728, 3072, 3840;
6 | 64, 2048, 10368, 24576, 38400, 46080;
7 | 128, 8192, 62208, 196608, 384000, 552960, 645120;
8 | 256, 32768, 373248, 1572864, 3840000, 6635520, 9031680, ...
...
For n=2 and L=1, T(2,1)=8, because: the bipartite graph <{v1,v2,v3},{x1=v1v2,x2=v1v3}> has rho-labelings (2,1,3),(2,1,4) with L=1 on the stable set {x2} and rho-labelings (1,2,0),(0,4,1) with L=1 on the stable set {x1,x3}; the bipartite graph <{v1,v2,v3,v4},{x1=v1v2,x2=v3v4}> has rho-labeling (0,4,1,3),(1,2,0,3) with L=1 on the stable set {v1,v3} and rho-labeling (4,0,3,1),(2,1,3,0) with L=1 on the stable set {v2,v4}. - Danny Rorabaugh, Apr 03 2015
MATHEMATICA
t[n_, l_] := 2^n*l!(l+1)^(n-l); Table[ t[n, l], {n, 8}, {l, 0, n-1}] // Flatten (* Robert G. Wilson v, Jul 05 2015 *)
PROG
(Magma) [2^n*Factorial(l)*(l+1)^(n-l): l in [0..n-1], n in [1..10]]; // Bruno Berselli, Aug 05 2015
CROSSREFS
Sequence in context: A273068 A362532 A193846 * A341107 A344075 A011402
KEYWORD
easy,nonn,tabl
AUTHOR
STATUS
approved