A255908 Triangle read by rows: T(n,L) = number of rho-labeled graphs with n edges whose labeling is bipartite with boundary value L.

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

Author

Christian Barrientos and Sarah Minion, Mar 10 2015

Keywords

• easy
• nonn
• tabl

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)

Examples

			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
		

Links

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

Programs

Magma

[2^n*Factorial(l)*(l+1)^(n-l): l in [0..n-1], n in [1..10]]; // Bruno Berselli, Aug 05 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 *)

Formula

For n>=1, 0<=L<=n-1, T(n,L)=(2^n)*(L!)*(L+1)^(n-L).