

A122193


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.


10



1, 1, 6, 6, 1, 24, 114, 180, 90, 1, 78, 978, 4320, 8460, 7560, 2520, 1, 240, 6810, 63540, 271170, 604800, 730800, 453600, 113400, 1, 726, 43746, 774000, 6075900, 25424280, 61923960, 90720000, 78813000, 37422000, 7484400
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

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


LINKS



FORMULA

Double e.g.f.: exp(x)*Sum_{n>=0} exp(binomial(n,2)*y)*x^n/n!.
T(n,k) = S_{2,2}(n,k)*k!/2^n; S_{2,2} the generalized Stirling numbers A078739.  Peter Luschny, Mar 25 2011
T(n,k) = Sum_{i = 0..k} (1)^(ki)*binomial(k,i)*(i*(i1)/2)^n.
T(n,k) = k*(k1)/2*( T(n1,k) + 2*T(n1,k1) + T(n1,k2) ) 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).
nth row polynomial R(n,x) = Sum_{i >= 2} (i*(i1)/2)^n * x^i/(1+x)^(i+1) for n >= 1.
1/(1x)*R(n,x/(1x)) = Sum_{i >= 2} (i*(i1)/2)^n*x^i for n >= 1.
R(n,x) = 1/2^n*Sum_{k = 0..n} (1)^(nk)*binomial(n,k)*F(n+k,x), where F(n,x) = Sum_{k = 0..n} k!*Stirling2(n,k)*x^k is the nth Fubini polynomial, the nth row polynomial of A131689.
R(n,x) = x/(1+x)*1/2^n*Sum_{k = 0..n} binomial(n,k)*F(n+k,x) for n >= 1.
The polynomials Sum_{k = 2..2*n} T(n,k)*x^(k2)*(1x)^(2*nk) are the row polynomials of A154283.
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 Worpitzkytype identity Sum_{k = 1..n} A019538(n,k)*binomial(x,k) = x^n.
Sum_{i = 2..n1} (i*(i1)/2)^m = Sum_{k = 2..2*m} T(m,k) * binomial(n,k+1) for m >= 1. See Examples below.
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 nth row polynomial of A019538.
x^2*R(n,1x) = (1+x)^2*R(n,x) for n >= 1.
R(n+1,x) = 1/2*x^2*(d/dx)^2 ((1+x)^2*R(n,x)).
The zeros of R(n,x) belong to the interval [1, 0].
Alternating row sums equal 1, that is R(n,1) = 1.
4^n*Sum_{k = 2..2*n} T(n,k)*(1/2)^k appears to equal (1)^(n+1)*A005799(n) for n >= 1.
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.
Sum_{k = 2..2*n} T(n,k)*binomial(x,k2) = 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)
nth 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)).
The nth 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)


EXAMPLE

Triangle begins:
1;
1, 6, 6;
1, 24, 114, 180, 90;
1, 78, 978, 4320, 8460, 7560, 2520;
...
For n=3 edges and k=4 vertices there are three loopless multigraphs without isolated vertices: a path, a Ygraph, 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)
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:
...abd.... a < b = c < d
...a...cb... a < c < b = d
...ad...b... a = c < d < b
...ab...d... a = c < b < d
...c...ad... c < a < b = d
...cab.... c < a = d < b
T(2,4) = 6: There are 6 arrangements of the two intervals with 4 distinct endpoints:
...ab...cd..... no intersection a < b < c < d
...a...c...b...d... a < c < b < d
...a...cd...b.... [c,d] is a proper subset of [a,b]
...c...a...d...b... c < a < d < b
...c...ab...d... [a,b] is a proper subset of [c,d]
...cd...ab..... no intersection c < d < a < b.
Sums of powers of triangular numbers:
Row 2: Sum_{i = 2..n1} C(i,2)^2 = C(n,3) + 6*C(n,4) + 6*C(n,5);
Row 3: Sum_{i = 2..n1} 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.
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
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
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)
T(3,3) = 24 alignments of length 3 of 3 strings each of length 2. Examples include
(i) A B  (ii) A  B
 C D  C D
 E F E F 
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)


MAPLE

# Note that the function implements the full triangle because it can be
# much better reused and referenced in this form.
# Displays the truncated triangle from the definition:


MATHEMATICA

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 JeanFrançois Alcover at A078739 *)


CROSSREFS



KEYWORD

easy,nonn,tabf


AUTHOR



EXTENSIONS



STATUS

approved



