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.

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

Offset: 0

Author

Emeric Deutsch, Aug 09 2005

Keywords

• nonn
• tabl
• easy

Comments

Row sums yield A047863. T(2*n,n) = A111637(n). T(n,1) = A001787(n).

Examples

			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;
  ...
		

References

• H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 88, Eq. 3.11.2.

Links

• S. R. Finch, Bipartite, k-colorable and k-colored graphs
• S. R. Finch, Bipartite, k-colorable and k-colored graphs, June 5, 2003. [Cached copy, with permission of the author]
• W. Wang and T. Wang, Generalized Riordan array, Discrete Mathematics, Vol. 308, No. 24, 6466-6500.

Crossrefs

Cf. A047863, A111637, A001787.

Cf. A134530 (matrix log), A134531.

Cf. A000684, A011266, A038845, A140802, A224069 (matrix inverse).

Programs

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 *)

Formula

T(n, k)=2^[k(n-k)]*C(n, k).

Matrix log yields triangle A134530, where A134530(n,k) = A134531(n-k)*(2^k)^(n-k)*C(n,k). - Paul D. Hanna, Nov 11 2007

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).

Column k = 2: A038845. Column k = 3: A140802. Sum_{k = 0..n} k*T(n,k) = n*A000684(n). (End)

From Peter Bala, Apr 09 2013: (Start)

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