A122193 - OEIS

%I #62 Dec 02 2024 16:31:33

%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 Peter Bala, <a href="/A131689/a131689.pdf">Deformations of the Hadamard product of power series</a>

%H Peter 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 and 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="https://research.ibm.com/haifa/ponderthis/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