A111636 - OEIS

%I #33 Apr 03 2023 09:24:58

%S 1,1,1,1,4,1,1,12,12,1,1,32,96,32,1,1,80,640,640,80,1,1,192,3840,

%T 10240,3840,192,1,1,448,21504,143360,143360,21504,448,1,1,1024,114688,

%U 1835008,4587520,1835008,114688,1024,1,1,2304,589824,22020096,132120576,132120576,22020096,589824,2304,1

%N 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.

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

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

%H S. R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/">Bipartite, k-colorable and k-colored graphs</a>

%H S. R. Finch, <a href="/A191371/a191371.pdf">Bipartite, k-colorable and k-colored graphs</a>, June 5, 2003. [Cached copy, with permission of the author]

%H W. Wang and T. Wang, <a href="https://doi.org/10.1016/j.disc.2007.12.037">Generalized Riordan array</a>, Discrete Mathematics, Vol. 308, No. 24, 6466-6500.

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

%F 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

%F From Peter Bala, Aug 13 2012: (Start)

%F Let f(n) = n!*2^binomial(n,2) = A011266(n). Then T(n,k) = f(n)/(f(k)*f(n-k)).

%F 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! + ....

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

%F Recurrence equation: T(n,k) = 2^k*T(n-1,k) + 2^(n-k)*T(n-1,k-1).

%F Column k = 2: A038845. Column k = 3: A140802. Sum {k = 0..n} k*T(n,k) = n*A000684(n).

%F (End)

%F From _Peter Bala_, Apr 09 2013: (Start)

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

%F 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.

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

%F The n-th row is a log-concave sequence and hence unimodal.

%F 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.

%F Sum_{k = 0..n} (-1)^k*T(2*n+1,k) = 0;

%F Sum_{k = 0..n} (-1)^k*2^k*T(2*n,k) = 0;

%F Sum_{k = 0..n} 2^k*T(n,k) = A000684(n). (End)

%F 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

%e 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.

%e Triangle starts:

%e   1;

%e   1,  1;

%e   1,  4,  1;

%e   1, 12, 12,  1;

%e   1, 32, 96, 32, 1;

%e   ...

%p 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

%t 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 *).

%Y Cf. A047863, A111637, A001787.

%Y Cf. A134530 (matrix log), A134531.

%Y A000684, A011266, A038845, A140802. A224069 (matrix inverse).

%K nonn,tabl,easy

%O 0,5

%A _Emeric Deutsch_, Aug 09 2005