|
|
A111636
|
|
Triangle read by rows: T(n,k) (0<=k<=n) is the number of labeled graphs having k blue nodes and n-k green ones and only nodes of different colors can be joined by an edge.
|
|
6
|
|
|
1, 1, 1, 1, 4, 1, 1, 12, 12, 1, 1, 32, 96, 32, 1, 1, 80, 640, 640, 80, 1, 1, 192, 3840, 10240, 3840, 192, 1, 1, 448, 21504, 143360, 143360, 21504, 448, 1, 1, 1024, 114688, 1835008, 4587520, 1835008, 114688, 1024, 1, 1, 2304, 589824, 22020096, 132120576, 132120576, 22020096, 589824, 2304, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
|
|
REFERENCES
|
H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 88, Eq. 3.11.2.
|
|
LINKS
|
|
|
FORMULA
|
T(n, k)=2^[k(n-k)]*C(n, k).
From Peter Bala, Aug 13 2012: (Start)
Let f(n) = n!*2^binomial(n,2) = A011266(n). Then T(n,k) = f(n)/(f(k)*f(n-k)).
E.g.f.: sum {n >= 0} exp(2^n*t*x)*x^n/n! = 1 + (1+t)*x + (1+4*t+t^2)*x^2/2! + ....
O.g.f.: sum {n >= 0} x^n/(1-2^n*t*x)^(n+1) = 1 + (1+t)*x + (1+4*t+t^2)*x^2 + .... O.g.f. for column k: 1/(1-2^k*x)^(k+1).
Recurrence equation: T(n,k) = 2^k*T(n-1,k) + 2^(n-k)*T(n-1,k-1).
(End)
Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)) = 1 + x + x^2/(2!*2) + x^3/(3!*2^3) + .... Then a generating function for this sequence is E(z)*E(x*z) = 1 + (1 + x)*z + (1 + 4*x + x^2)*z^2/(2!*2) + (1 + 12*x + 12*x^2 + x^3)*z^3/(3!*2^3) + .... Cf. Pascal's triangle A007318 with an e.g.f. of exp(z)*exp(x*z).
This is a generalized Riordan array (E(x), x) with respect to the sequence n!*2^C(n,2), as defined by Wang and Wang.
The n-th power of this triangle has a generating function E(z)^n*E(x*z). See A224069 for the inverse array (n = -1).
The n-th row is a log-concave sequence and hence unimodal.
The row polynomials satisfy the recurrence equation R(n+1,x) = 2^n*x*R(n,x/2) + R(n,2*x) with R(0,x) = 1, as well as R'(n,2*x) = n*2^(n-1)*R(n-1,x) (the ' denotes differentiation w.r.t. x). The row polynomials appear to have only real zeros.
Sum_{k = 0..n} (-1)^k*T(2*n+1,k) = 0;
Sum_{k = 0..n} (-1)^k*2^k*T(2*n,k) = 0;
Sum_{k = 0..n} 2^k*T(n,k) = A000684(n). (End)
T(n,k+1) = Product_{i=0..k} (T(n-i,1)/T(i+1,1)) for 0 <= k < n. - Werner Schulte, Nov 13 2018
|
|
EXAMPLE
|
T(2,1)=4 because we have B G, B--G, G B and G--B, where B (G) stands for a blue (green) node and -- denotes an edge.
Triangle starts:
1;
1, 1;
1, 4, 1;
1, 12, 12, 1;
1, 32, 96, 32, 1;
...
|
|
MAPLE
|
T:=(n, k)->binomial(n, k)*2^(k*(n-k)): for n from 0 to 9 do seq(T(n, k), k=0..n) od; # yields sequence in triangular form
|
|
MATHEMATICA
|
nn=6; f[x_, y_]:=Sum[Exp[x 2^n](y x)^n/n!, {n, 0, nn}]; Range[0, nn]!CoefficientList[Series[f[x, y], {x, 0, nn}], {x, y}]//Grid (* Geoffrey Critzer, Sep 07 2013 *).
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|