%I #57 Jun 05 2019 09:59:34
%S 1,1,6,6,1,24,114,180,90,1,78,978,4320,8460,7560,2520,1,240,6810,
%T 63540,271170,604800,730800,453600,113400,1,726,43746,774000,6075900,
%U 25424280,61923960,90720000,78813000,37422000,7484400
%N Triangle T(n,k) of number of loopless multigraphs with n labeled edges and k labeled vertices and without isolated vertices, n >= 1; 2 <= k <= 2*n.
%C T(n,k) equals the number of arrangements on a line of n (nondegenerate) finite closed intervals having k distinct endpoints. See the 'IBM Ponder This' link. An example is given below. - _Peter Bala_, Jan 28 2018
%C T(n,k) equals the number of alignments of length k of n strings each of length 2. See Slowinski. Cf. A131689 (alignments of strings of length 1) and A299041 (alignments of strings of length 3). - _Peter Bala_, Feb 04 2018
%H Michael De Vlieger, <a href="/A122193/b122193.txt">Table of n, a(n) for n = 1..10000</a> (rows 1 <= n <= 100).
%H P. Bala, <a href="/A131689/a131689.pdf">Deformations of the Hadamard product of power series</a>
%H P. Bala, <a href="/A122193/a122193.pdf">Notes on A122193</a>
%H S. Eger, <a href="http://arxiv.org/abs/1511.00622">On the Number of Many-to-Many Alignments of N Sequences</a>, arXiv:1511.00622 [math.CO], 2015.
%H J. Engbers and C. Stocker, <a href="http://math.colgate.edu/~integers/vol16.html ">Two Combinatorial Proofs of Identities Involving Sums of Powers of Binomial Coefficients</a>, Integers 16 (2016), #A58.
%H M. Dukes, C. D. White, <a href="http://arxiv.org/abs/1603.01589">Web Matrices: Structural Properties and Generating Combinatorial Identities</a>, arXiv:1603.01589 [math.CO], 2016.
%H IBM Ponder This, <a href="http://domino.watson.ibm.com/Comm/wwwr_ponder.nsf/challenges/January2001.html">Jan 01 2001</a>
%H J. B. Slowinski, <a href="http://www.neurociencias.org.ve/cont-cursos-laboratorio-de-neurociencias-luz/Slowinski1998%20phylogenetics.pdf">The Number of Multiple Alignments</a>, Molecular Phylogenetics and Evolution 10:2 (1998), 264-266. doi:<a href="http://dx.doi.org/10.1006/mpev.1998.0522">10.1006/mpev.1998.0522</a>
%F Double e.g.f.: exp(-x)*Sum_{n>=0} exp(binomial(n,2)*y)*x^n/n!.
%F T(n,k) = S_{2,2}(n,k)*k!/2^n; S_{2,2} the generalized Stirling numbers A078739. - _Peter Luschny_, Mar 25 2011
%F From _Peter Bala_, Jan 28 2018: (Start)
%F T(n,k) = Sum_{i = 0..k} (-1)^(k-i)*binomial(k,i)*(i*(i-1)/2)^n.
%F T(n,k) = k*(k-1)/2*( T(n-1,k) + 2*T(n-1,k-1) + T(n-1,k-2) ) for 2 < k <= 2*n with boundary conditions T(n,2) = 1 for n >= 1 and T(n,k) = 0 if (k < 2) or (k > 2*n).
%F n-th row polynomial R(n,x) = Sum_{i >= 2} (i*(i-1)/2)^n * x^i/(1+x)^(i+1) for n >= 1.
%F 1/(1-x)*R(n,x/(1-x)) = Sum_{i >= 2} (i*(i-1)/2)^n*x^i for n >= 1.
%F R(n,x) = 1/2^n*Sum_{k = 0..n} (-1)^(n-k)*binomial(n,k)*F(n+k,x), where F(n,x) = Sum_{k = 0..n} k!*Stirling2(n,k)*x^k is the n-th Fubini polynomial, the n-th row polynomial of A131689.
%F R(n,x) = x/(1+x)*1/2^n*Sum_{k = 0..n} binomial(n,k)*F(n+k,x) for n >= 1.
%F The polynomials Sum_{k = 2..2*n} T(n,k)*x^(k-2)*(1-x)^(2*n-k) are the row polynomials of A154283.
%F A154283 * A007318 equals the row reverse of this array.
%F Sum_{k = 2..2*n} T(n,k)*binomial(x,k) = ( binomial(x,2) )^n. Equivalently, Sum_{k = 2..2*n} (-1)^k*T(n,k)*binomial(x+k,k) = ( binomial(x+2,2) )^n. Cf. the Worpitzky-type identity Sum_{k = 1..n} A019538(n,k)*binomial(x,k) = x^n.
%F Sum_{i = 2..n-1} (i*(i-1)/2)^m = Sum_{k = 2..2*m} T(m,k) * binomial(n,k+1) for m >= 1. See Examples below.
%F R(n,x) = x^2 o x^2 o ... o x^2 (n factors), where o is the black diamond product of power series defined in Dukes and White. Note the polynomial x o x o ... o x (n factors) is the n-th row polynomial of A019538.
%F x^2*R(n,-1-x) = (1+x)^2*R(n,x) for n >= 1.
%F R(n+1,x) = 1/2*x^2*(d/dx)^2 ((1+x)^2*R(n,x)).
%F The zeros of R(n,x) belong to the interval [-1, 0].
%F Alternating row sums equal 1, that is R(n,-1) = 1.
%F R(n,-2) = 4*R(n,1) = 4*A055203(n).
%F 4^n*Sum_{k = 2..2*n} T(n,k)*(-1/2)^k appears to equal (-1)^(n+1)*A005799(n) for n >= 1.
%F For k a nonzero integer, the power series A(k,x) := exp( Sum_{n >= 1} 1/k^2*R(n,k)*x^n/n ) appear to have integer coefficients. See the Example section.
%F Sum_{k = 2..2*n} T(n,k)*binomial(x,k-2) = binomial(x,2)^n - 2*binomial(x+1,2)^n + binomial(x+2,2)^n. These polynomials have their zeros on the vertical line Re x = -1/2 in the complex plane (the corresponding property also holds for the row polynomials of A019538 with a factor of x removed). (End)
%F From _Peter Bala_, Mar 08 2018: (Start)
%F n-th row polynomial R(n,x) = coefficient of (z_1)^2 * ... * (z_n)^2 in the expansion of the rational function 1/(1 + x - x*(1 + z_1)*...*(1 + z_n)).
%F The n-th row of the table is given by the matrix product P^(-1)*v_n, where P denotes Pascal's triangle A007318 and v_n is the sequence (0, 0, 1, 3^n, 6^n, 10^n, ...) regarded as an infinite column vector, where 1, 3, 6, 10, ... is the sequence of triangular numbers A000217. Cf. A087127. (End)
%e Triangle begins:
%e 1;
%e 1, 6, 6;
%e 1, 24, 114, 180, 90;
%e 1, 78, 978, 4320, 8460, 7560, 2520;
%e ...
%e From _Francisco Santos_, Nov 17 2017: (Start)
%e For n=3 edges and k=4 vertices there are three loopless multigraphs without isolated vertices: a path, a Y-graph, and the multigraph {12, 34, 34}. The number of labelings in each is 3!4!/a, where a is the number of automorphisms. This gives respectively 3!4!/2 = 72, 3!4!/6 = 24 and 3!4!/8 = 18, adding up to 72 + 24 + 18 = 114. (End)
%e From _Peter Bala_, Jan 28 2018: (Start)
%e T(2,3) = 6: Consider 2 (nondegenerate) finite closed intervals [a, b] and [c, d]. There are 6 arrangements of these two intervals with 3 distinct endpoints:
%e ...a--b--d.... a < b = c < d
%e ...a...c--b... a < c < b = d
%e ...a--d...b... a = c < d < b
%e ...a--b...d... a = c < b < d
%e ...c...a--d... c < a < b = d
%e ...c--a--b.... c < a = d < b
%e T(2,4) = 6: There are 6 arrangements of the two intervals with 4 distinct endpoints:
%e ...a--b...c--d..... no intersection a < b < c < d
%e ...a...c...b...d... a < c < b < d
%e ...a...c--d...b.... [c,d] is a proper subset of [a,b]
%e ...c...a...d...b... c < a < d < b
%e ...c...a--b...d... [a,b] is a proper subset of [c,d]
%e ...c--d...a--b..... no intersection c < d < a < b.
%e Sums of powers of triangular numbers:
%e Row 2: Sum_{i = 2..n-1} C(i,2)^2 = C(n,3) + 6*C(n,4) + 6*C(n,5);
%e Row 3: Sum_{i = 2..n-1} C(i,2)^3 = C(n,3) + 24*C(n,4) + 114*C(n,5) + 180*C(n,6) + 90*C(n,7). See A024166 and A085438.
%e exp( Sum_{n >= 1} R(n,2)*x^n/n ) = (1 + x + 19*x^2 + 1147*x^3 + 145606*x^4 + 31784062*x^5 + ... )^4
%e exp( Sum_{n >= 1} R(n,3)*x^n/n ) = (1 + x + 37*x^2 + 4453*x^3 + 1126375*x^4 + 489185863*x^5 + ... )^9
%e exp( Sum_{n >= 1} R(n,4)*x^n/n ) = (1 + x + 61*x^2 + 12221*x^3 + 5144411*x^4 + 3715840571*x^5 + ... )^16 (End)
%e From _Peter Bala_, Feb 04 2018: (Start)
%e T(3,3) = 24 alignments of length 3 of 3 strings each of length 2. Examples include
%e (i) A B - (ii) A - B
%e - C D - C D
%e - E F E F -
%e There are 18 alignments of type (i) with two gap characters in one of the columns (3 ways of putting 2 gap characters in a column x 2 ways to place the other letter in the row which doesn't yet have a gap character x 3 columns: there are 6 alignments of type (ii) with a single gap character in each column (3 ways to put a single gap character in the first column x 2 ways to then place a single gap character in the second column). (End)
%p # Note that the function implements the full triangle because it can be
%p # much better reused and referenced in this form.
%p A122193 := (n,k) -> A078739(n,k)*k!/2^n:
%p # Displays the truncated triangle from the definition:
%p seq(print(seq(A122193(n,k),k=2..2*n)),n=1..6); # _Peter Luschny_, Mar 25 2011
%t t[n_, k_] := Sum[(-1)^(n - r) Binomial[n, r] StirlingS2[n + r, k], {r, 0, n}]; Table[t[n, k] k!/2^n, {n, 6}, {k, 2, 2 n}] // Flatten (* _Michael De Vlieger_, Nov 18 2017, after _Jean-François Alcover_ at A078739 *)
%Y Row sums give A055203.
%Y Cf. A078739, A005799, A019538, A131689, A154283, A299041, A087127.
%Y For Sum_{i = 2..n} C(i,2)^k see A024166 (k = 2), A085438 - A085442 ( k = 3 thru 7).
%K easy,nonn,tabf
%O 1,3
%A _Vladeta Jovovic_, Aug 24 2006
%E Definition corrected by _Francisco Santos_, Nov 17 2017