A055203 -id:A055203 - cp's OEIS frontend

A058809 The sequence lambda(3,n), where lambda is defined in A055203. Number of ways of placing n identifiable positive intervals with a total of exactly three starting and/or finishing points.

0, 0, 6, 24, 78, 240, 726, 2184, 6558, 19680, 59046, 177144, 531438, 1594320, 4782966, 14348904, 43046718, 129140160, 387420486, 1162261464, 3486784398, 10460353200, 31381059606, 94143178824, 282429536478, 847288609440

Offset: 0

N. J. A. Sloane, Jan 03 2001

For all n, a(n)=1*3^n-3*1^n+3*0^n-1*0^n [with 0^0=1] where powers are taken of triangular numbers and multiplied by binomial coefficients with alternating signs. - Henry Bottomley, Jan 05 2001
For n>=1, a(n) is the number of facets of the harmonic polytope. See Ardila and Escobar. - Michel Marcus, Jun 08 2020
For n >= 3, this is the number of acyclic orientations of the wheel graph of order n+1. - Peter Kagey, Oct 13 2020
Number of ternary strings of length n with at least 2 different digits. - Enrique Navarrete, Nov 20 2020
A level 1 Hanoi graph is a triangle. Level n+1 is formed from three copies of level n by adding edges between pairs of corner vertices of each pair of triangles.  This graph represents the allowable moves in the Towers of Hanoi problem with n disks.  a(n) is the number of degree 3 vertices in the level n Hanoi graph. - Allan Bickle, Aug 07 2024

			a(2)=6 since intervals a-a and b-b can be combined as a-ab-b, a-b-ab, ab-a-b, b-ab-a, b-a-ab, or ab-b-a.
The level 2 Hanoi graph has 9 vertices, 6 with degree 3, so a(2) = 6.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Federico Ardila and Laura Escobar, The harmonic polytope, arXiv:2006.03078 [math.CO], 2020.
Allan Bickle, Properties of Sierpinski Triangle Graphs, Springer PROMS 448 (2021) 295-303.
A. Hinz, S. Klavzar, and S. Zemljic, A survey and classification of Sierpinski-type graphs, Discrete Applied Mathematics 217 3 (2017), 565-600.
Eric Weisstein's World of Mathematics, Hanoi Graph
Eric Weisstein's World of Mathematics, Wheel Graph
Index entries for linear recurrences with constant coefficients, signature (4,-3).

Cf. A059116, A059117.

Cf. A000225, A029858, A058809, A375256 (Hanoi graphs).

Join[{0},NestList[3#+6&,0,30]] (* or *) Join[{0},LinearRecurrence[{4,-3},{0,6},30]] (* Harvey P. Dale, Sep 29 2013 *)

concat([0,0], Vec(6*x^2 / ((1 - x)*(1 - 3*x)) + O(x^30))) \\ Colin Barker, Oct 14 2020

For n>0, a(n) = 3^n-3 = 3*a(n-1)+6.
a(0)=0, a(1)=0, a(2)=6, a(n) = 4*a(n-1)-3*a(n-2). - Harvey P. Dale, Sep 29 2013
G.f.: 6*x^2 / ((1 - x)*(1 - 3*x)). - Colin Barker, Oct 14 2020

A059116 The sequence lambda(4,n), where lambda is defined in A055203. Number of ways of placing n identifiable positive intervals with a total of exactly four starting and/or finishing points.

Original entry on oeis.org

0, 0, 6, 114, 978, 6810, 43746, 271194, 1653378, 9998970, 60229986, 362088474, 2174656578, 13054316730, 78345032226, 470127588954, 2820937720578, 16926142884090, 101558406986466, 609355090964634, 3656144492925378

Offset: 0

Henry Bottomley, Jan 05 2001

For all n, a(n)=1*6^n-4*3^n+6*1^n-4*0^n+1*0^n [with 0^0=1] where powers are taken of triangular numbers and multiplied by binomial coefficients with alternating signs.

			a(2)=6 since intervals a-a and b-b can be combined as a-a-b-b, a-b-a-b, a-b-b-a, b-a-b-a, b-a-a-b, or b-a-a-b.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (10,-27,18).

Cf. A058809, A059117.

[1*6^n-4*3^n+6*1^n-4*0^n+1*0^n: n in [0..30]]; // Vincenzo Librandi, Sep 23 2011

A059116:=n->`if`(n<2, 0, 6^n-4*3^n+6): seq(A059116(n), n=0..20); # Wesley Ivan Hurt, Sep 14 2014

concat([0,0], Vec(-6*x^2*(9*x+1)/((x-1)*(3*x-1)*(6*x-1)) + O(x^100))) \\ Colin Barker, Sep 14 2014

For n>0, a(n) = 6^n-4*3^n+6.

a(n) = 10*a(n-1)-27*a(n-2)+18*a(n-3) for n>3. G.f.: -6*x^2*(9*x+1) / ((x-1)*(3*x-1)*(6*x-1)). - Colin Barker, Sep 14 2014

A059117 Square array of lambda(k,n), where lambda is defined in A055203. Number of ways of placing n identifiable positive intervals with a total of exactly k starting and/or finishing points.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 6, 1, 0, 0, 0, 0, 6, 24, 1, 0, 0, 0, 0, 0, 114, 78, 1, 0, 0, 0, 0, 0, 180, 978, 240, 1, 0, 0, 0, 0, 0, 90, 4320, 6810, 726, 1, 0, 0, 0, 0, 0, 0, 8460, 63540, 43746, 2184, 1, 0, 0, 0, 0, 0, 0, 7560, 271170, 774000, 271194, 6558, 1

Offset: 0

Henry Bottomley, Jan 05 2001

			Rows are: 1,0,0,0,0,0,....; 0,0,1,0,0,0,....; 0,0,1,6,6,0,....; 0,0,1,24,114,180,.... etc.

Sum of rows gives A055203. Columns include A000007, A057427, A058809, A059116. Final positive number in each row is A000680.

A[ n_, k_] := If[n < 1 || k < 1, Boole[n == 0 && k == 0], n! k! Coefficient[ Normal[ Series[ Sum[ Exp[-x z] (x z)^m/m! Exp[y z m (m - 1)/2], {m, 0, n}], {z, 0, n + k}]], x^n y^k z^(n + k)]]; (* Michael Somos, Jul 17 2019 *)

lambda(k, n) = (lambda(k - 2, n - 1) + 2*lambda(k - 2, n - 1) + lambda(k - 2, n - 1))*k*(k - 1)/2 starting with lambda(k, 0) = 1 if k = 0 but = 0 otherwise. lambda(k, n) = sum_{j=0..k} (-1)^(k + j) * C(k, j) * ((j - 1)*j/2)^n.

A121316 Unlabeled version of A055203: number of different relations between n intervals (of nonzero length) on a line, up to permutation of intervals.

Original entry on oeis.org

1, 1, 7, 75, 1105, 20821, 478439, 12977815, 405909913, 14382249193, 569377926495, 24908595049347, 1193272108866953, 62128556769033261, 3493232664307133871, 210943871609662171055, 13615857409567572389361, 935523911378273899335537

Offset: 0

Goran Kilibarda and Vladeta Jovovic, Aug 25 2006

nonn

Also number of labeled multigraphs without isolated vertices and with n edges.

Nathaniel Johnston, Table of n, a(n) for n = 0..125
A. N. Bhavale, B. N. Waphare, Basic retracts and counting of lattices, Australasian J. of Combinatorics (2020) Vol. 78, No. 1, 73-99.

Row n=2 of A330942.

Cf. A055203, A121251, A104209.

seq(sum(binomial(k*(k-1)/2+n-1,n)/2^(k+1),k=0..infinity),n=0..20);
with(combinat): A121316:=proc(n) return (1/n!)*add(abs(stirling1(n,k))*A055203(k),k=0..n): end: seq(A121316(n),n=0..20); # Nathaniel Johnston, Apr 28 2011

Table[Sum[Binomial[k*(k-1)/2+n-1,n]/2^(k+1),{k,0,Infinity}],{n,0,20}] (* Vaclav Kotesovec, Mar 15 2014 *)

a(n) = {sum(j=0, 2*n, binomial(binomial(j,2)+n-1, n) * sum(i=j, 2*n, (-1)^(i-j)*binomial(i,j)))} \\ Andrew Howroyd, Feb 09 2020

a(n) = (1/n!)* Sum_{k=0..n} |Stirling1(n,k)|*A055203(k).
a(n) = Sum_{k>=0} binomial(k*(k-1)/2+n-1,n)/2^(k+1).
a(n) ~ n^n * 2^(n-1 + log(2)/4) / (exp(n) * (log(2))^(2*n+1)). - Vaclav Kotesovec, Mar 15 2014
a(n) = Sum_{j=0..2*n} binomial(binomial(j,2)+n-1, n) * (Sum_{i=j..2*n} (-1)^(i-j)*binomial(i,j)). - Andrew Howroyd, Feb 09 2020

A058810 The sequence lambda(n,n), where lambda is defined in A055203.

Original entry on oeis.org

1, 0, 1, 24, 978, 63540, 6075900, 805351680, 141497266680, 31843424440800, 8934902572138200, 3058578720594936000, 1254725049041097480000, 607696683874925162918400, 343106914496426524661817600, 223382333871697909676511744000, 166127588708309626930142410800000

Offset: 0

N. J. A. Sloane, Jan 03 2001

nonn

Number of n X n binary matrices with 2 ones in every column and no empty rows. - Andrew Howroyd, Dec 15 2018

Andrew Howroyd, Table of n, a(n) for n = 0..100

Cf. A055203.

a[0]=1; a[n_] := Sum[(-1)^(n-i)((i-1)i)^n Binomial[n, i], {i, 0, n}]/2^n;
Array[a, 17, 0] (* Jean-François Alcover, Aug 27 2019 *)

a(n)=sum(i=0, n, (-1)^(n-i)*binomial(n,i)*binomial(i,2)^n) \\ Andrew Howroyd, Dec 15 2018

a(n) = Sum_{i=0..n} (-1)^(n-i)*binomial(n,i)*binomial(i,2)^n. - Andrew Howroyd, Dec 15 2018

a(0)=1 prepended by Andrew Howroyd, Dec 15 2018

A262809 Number A(n,k) of lattice paths from {n}^k to {0}^k using steps that decrement one or more components by one; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 13, 13, 1, 1, 1, 75, 409, 63, 1, 1, 1, 541, 23917, 16081, 321, 1, 1, 1, 4683, 2244361, 10681263, 699121, 1683, 1, 1, 1, 47293, 308682013, 14638956721, 5552351121, 32193253, 8989, 1, 1, 1, 545835, 58514835289, 35941784497263, 117029959485121, 3147728203035, 1538743249, 48639, 1, 1

Offset: 0

Alois P. Heinz, Oct 02 2015

Also, A(n,k) is the number of alignments for k sequences of length n each (Slowinski 1998).
Row r > 0 is asymptotic to sqrt(r*Pi) * (r^(r-1)/(r-1)!)^n * n^(r*n+1/2) / (2^(r/2) * exp(r*n) * (log(2))^(r*n+1)), or equivalently to sqrt(r) * (r^(r-1)/(r-1)!)^n * (n!)^r / (2^r * (Pi*n)^((r-1)/2) * (log(2))^(r*n+1)). - Vaclav Kotesovec, Mar 23 2016
From Vaclav Kotesovec, Mar 23 2016: (Start)
Column k > 0 is asymptotic to sqrt(c(k)) * d(k)^n / (Pi*n)^((k-1)/2), where c(k) and d(k) are roots of polynomial equations of degree k, independent on n.
---------------------------------------------------
k               d(k)
---------------------------------------------------
2              5.8284271247461900976033774484193...
3             56.9476283720414911685286267804411...
4            780.2794068067951456595241495989622...
5          13755.2719024115081712083954421541320...
6         296476.9162644200814909862281498491264...
7        7553550.6198338218721069097516499501996...
8      222082591.6017202421029000117685530884167...
9     7400694480.0494436216324852038000444393262...
10  275651917450.6709238286995776605620357737005...
---------------------------------------------------
d(k) is a root of polynomial:
---------------------------------------------------
k=2, 1 - 6*d + d^2
k=3, -1 + 3*d - 57*d^2 + d^3
k=4, 1 - 12*d - 218*d^2 - 780*d^3 + d^4
k=5, -1 + 5*d - 1260*d^2 - 3740*d^3 - 13755*d^4 + d^5
k=6, 1 - 18*d - 5397*d^2 - 123696*d^3 + 321303*d^4 - 296478*d^5 + d^6
k=7, -1 + 7*d - 24031*d^2 - 374521*d^3 - 24850385*d^4 + 17978709*d^5 - 7553553*d^6 + d^7
k=8, 1 - 24*d - 102692*d^2 - 9298344*d^3 + 536208070*d^4 - 7106080680*d^5 - 1688209700*d^6 - 222082584*d^7 + d^8
(End)
d(k) = (2^(1/k) - 1)^(-k). - David Bevan, Apr 07 2022
d(k) is asymptotic to (k/log(2))^k/sqrt(2). - David Bevan, Apr 07 2022
A(n,k) is the number of binary matrices with k columns and any number of nonzero rows with n ones in every column. - Andrew Howroyd, Jan 23 2020

			A(2,2) = 13: [(2,2),(1,2),(0,2),(0,1),(0,0)], [(2,2),(1,2),(0,1),(0,0)], [(2,2),(1,2),(1,1),(0,1),(0,0)], [(2,2),(1,2),(1,1),(0,0)], [(2,2),(1,2),(1,1),(1,0),(0,0)], [(2,2),(2,1),(1,1),(0,1),(0,0)], [(2,2),(2,1),(1,1),(0,0)], [(2,2),(2,1),(1,1),(1,0),(0,0)], [(2,2),(2,1),(2,0),(0,1),(0,0)], [(2,2),(2,1),(1,0),(0,0)], [(2,2),(1,1),(0,1),(0,0)], [(2,2),(1,1),(0,0)], [(2,2),(1,1),(1,0),(0,0)].
Square array A(n,k) begins:
  1, 1,    1,        1,             1,                   1, ...
  1, 1,    3,       13,            75,                 541, ...
  1, 1,   13,      409,         23917,             2244361, ...
  1, 1,   63,    16081,      10681263,         14638956721, ...
  1, 1,  321,   699121,    5552351121,     117029959485121, ...
  1, 1, 1683, 32193253, 3147728203035, 1050740615666453461, ...

Alois P. Heinz, Antidiagonals n = 0..48, flattened
J. B. Slowinski, The Number of Multiple Alignments, Molecular Phylogenetics and Evolution 10:2 (1998), 264-266. doi:10.1006/mpev.1998.0522

Columns: A000012 (k=0 and k=1), A001850 (k=2), A126086 (k=3), A263064 (k=4), A263065 (k=5), A263066 (k=6), A263067 (k=7), A263068 (k=8), A263069 (k=9), A263070 (k=10).
Rows: A000012 (n=0), A000670 (n=1), A055203 (n=2), A062208 (n=3), A062205 (n=4), A263061 (n=5), A263062 (n=6), A062204 (n=7), A263063 (n=8), A263071 (n=9), A263072 (n=10).
Main diagonal: A262810.
Cf. A210472, A225094, A227578, A227655, A229142, A229345, A263159, A316674.
Cf. A188392, A330942, A331461, A331637.

A:= (n, k)-> add(add((-1)^i*binomial(j, i)*
     binomial(j-i, n)^k, i=0..j), j=0..k*n):
seq(seq(A(n, d-n), n=0..d), d=0..10);

A[, 0] =  1; A[n, k_] := Sum[Sum[(-1)^i*Binomial[j, i]*Binomial[j - i, n]^k, {i, 0, j}], {j, 0, k*n}];
Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Jul 22 2016, after Alois P. Heinz *)

T(n,k) = {my(m=n*k); sum(j=0, m, binomial(j,n)^k*sum(i=j, m, (-1)^(i-j)*binomial(i, j)))} \\ Andrew Howroyd, Jan 23 2020

A(n,k) = Sum_{j=0..k*n} Sum_{i=0..j} (-1)^i*C(j,i)*C(j-i,n)^k.
A(n,k) = Sum_{i >= 0} binomial(i,n)^k/2^(i+1). - Peter Bala, Jan 30 2018
A(n,k) = Sum_{j=0..n*k} binomial(j,n)^k * Sum_{i=j..n*k} (-1)^(i-j) * binomial(i,j). - Andrew Howroyd, Jan 23 2020

A078739 Triangle of generalized Stirling numbers S_{2,2}(n,k) read by rows (n>=1, 2<=k<=2n).

Original entry on oeis.org

1, 2, 4, 1, 4, 32, 38, 12, 1, 8, 208, 652, 576, 188, 24, 1, 16, 1280, 9080, 16944, 12052, 3840, 580, 40, 1, 32, 7744, 116656, 412800, 540080, 322848, 98292, 16000, 1390, 60, 1, 64, 46592, 1446368, 9196992, 20447056, 20453376, 10564304, 3047520, 511392, 50400

Offset: 1

N. J. A. Sloane, Dec 21 2002

A generalization of the Stirling2 numbers S_{1,1} from A008277.
The g.f. for column k=2*K is (x^K)*pe(K,x)*d(k,x) and for k=2*K+1 it is (x^K)*po(K,x)*2*(K+1)*K*d(k,x), K>= 1, with d(k,x) := 1/product(1-p*(p-1)*x,p=2..k) and the row polynomials pe(n,x) := sum(A089275(n,m)*x^m,m=0..n-1) and po(n,x) := sum(A089276(n,m)*x^m,m=0..n-1). - Wolfdieter Lang, Nov 07 2003
The formula for the k-th column sequence is given in A089511.
Codara et al., show that T(n,k) gives the number of k-colorings of the graph nK_2 (the disjoint union of n copies of the complete graph K_2). An example is given below. - Peter Bala, Aug 15 2013

			From _Peter Bala_, Aug 15 2013: (Start)
The table begins
n\k | 2    3    4    5    6   7   8
= = = = = = = = = = = = = = = = = =
  1 | 1
  2 | 2    4    1
  3 | 4   32   38   12    1
  4 | 8  208  652  576  188  24   1
...
Graph coloring interpretation of T(2,3) = 4: The graph 2K_2 is 2 copies of K_2, the complete graph on 2 vertices:
o---o  o---o
a   b  c   d
The four 3-colorings of 2K_2 are ac|b|d, ad|b|c, bc|a|d and bd|a|c. (End)

P. Blasiak, K. A. Penson and A. I. Solomon, The Boson Normal Ordering Problem and Generalized Bell Numbers, arXiv:quant-ph/0212072, 2002.
P. Blasiak, K. A. Penson and A. I. Solomon, The general boson normal ordering problem, arXiv:quant-ph/0402027, 2004.
P. Blasiak, K. A. Penson and A. I. Solomon, The general boson normal ordering problem, Phys. Lett. A 309 (2003) 198-205.
Steve Butler, Fan Chung, Jay Cummings, R. L. Graham, Juggling card sequences, arXiv:1504.01426 [math.CO], 2015.
Leonard Carlitz, On Arrays of Numbers, Am. J. Math., 54,4 (1932) 739-752. [Eqs. (3) and (4) with lambda = 0, mu = 2, a_{n,k-1} = a(n, k).- _Wolfdieter Lang_, Jan 30 2020 ]
P. Codara, O. M. D’Antona, P. Hell, A simple combinatorial interpretation of certain generalized Bell and Stirling numbers arXiv:1308.1700v1 [cs.DM]
A. Dzhumadildaev and D. Yeliussizov, Path decompositions of digraphs and their applications to Weyl algebra, arXiv preprint arXiv:1408.6764v1, 2014. [Version 1 contained many references to the OEIS, which were removed in Version 2. - _N. J. A. Sloane_, Mar 28 2015]
Askar Dzhumadil'daev and Damir Yeliussizov, Walks, partitions, and normal ordering, Electronic Journal of Combinatorics, 22(4) (2015), #P4.10.
S.-M. Ma, T. Mansour, M. Schork. Normal ordering problem and the extensions of the Stirling grammar, arXiv preprint arXiv:1308.0169 [math.CO], 2013.
Toufik Mansour, Matthias Schork and Mark Shattuck, The Generalized Stirling and Bell Numbers Revisited, Journal of Integer Sequences, Vol. 15 (2012), #12.8.3.

Row sums give A020556. Triangle S_{1, 1} = A008277, S_{2, 1} = A008297 (ignoring signs), S_{3, 1} = A035342, S_{3, 2} = A078740, S_{3, 3} = A078741. A090214 (S_{4,4}).
The column sequences are A000079(n-1)(powers of 2), 4*A016129(n-2), A089271, 12*A089272, A089273, etc.
Main diagonal is A217900.
Cf. A071951 (Legendre-Stirling triangle).
Cf. A122193, A055203.

# Note that the function implements the full triangle because it can be
# much better reused and referenced in this form.
A078739 := proc(n,k) local r;
add((-1)^(n-r)*binomial(n,r)*combinat[stirling2](n+r,k),r=0..n) end:
# Displays the truncated triangle from the definition:
seq(print(seq(A078739(n,k),k=2..2*n)),n=1..6); # Peter Luschny, Mar 25 2011

t[n_, k_] := Sum[(-1)^(n-r)*Binomial[n, r]*StirlingS2[n+r, k], {r, 0, n}]; Table[t[n, k], {n, 1, 7}, {k, 2, 2*n}] // Flatten (* Jean-François Alcover, Apr 11 2013, after Peter Luschny *)

a(n, k) = sum(binomial(k-2+p, p)*A008279(2, p)*a(n-1, k-2+p), p=0..2) if 2 <= k <= 2*n for n>=1, a(1, 2)=1; else 0. Here A008279(2, p) gives the third row (k=2) of the augmented falling factorial triangle: [1, 2, 2] for p=0, 1, 2. From eq.(21) with r=2 of the Blasiak et al. paper.
a(n, k) = (((-1)^k)/k!)*sum(((-1)^p)*binomial(k, p)*A008279(p, 2)^n, p=2..k) for 2 <= k <= 2*n, n>=1. From eq.(19) with r=2 of the Blasiak et al. paper.
a(n, k) = sum(A071951(n, j)*A089503(j, 2*j-k+1), j=ceiling(k/2)..min(n, k-1)), 1<=n, 2<=k<=2n; relation to Legendre-Stirling triangle. Wolfdieter Lang, Dec 01 2003
a(n, k) = A122193(n,k)*2^n/k! - Peter Luschny, Mar 25 2011
E^n = sum_{k=2}^(2n) a(n,k)*x^k*D^k where D is the operator d/dx, and E the operator x^2d^2/dx^2.
The row polynomials R(n,x) are given by the Dobinski-type formula R(n,x) = exp(-x)*sum {k = 0..inf} (k*(k-1))^n*x^k/k!. - Peter Bala, Aug 15 2013

More terms from Wolfdieter Lang, Nov 07 2003

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.

Original entry on oeis.org

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

Offset: 1

Vladeta Jovovic, Aug 24 2006

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

			Triangle begins:
  1;
  1,  6,   6;
  1, 24, 114,  180,   90;
  1, 78, 978, 4320, 8460, 7560, 2520;
  ...
From _Francisco Santos_, Nov 17 2017: (Start)
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)
From _Peter Bala_, Jan 28 2018: (Start)
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:
  ...a--b--d....  a < b = c < d
  ...a...c--b...  a < c < b = d
  ...a--d...b...  a = c < d < b
  ...a--b...d...  a = c < b < d
  ...c...a--d...  c < a < b = d
  ...c--a--b....  c < a = d < b
T(2,4) = 6: There are 6 arrangements of the two intervals with 4 distinct endpoints:
  ...a--b...c--d.....  no intersection a < b < c < d
  ...a...c...b...d...  a < c < b < d
  ...a...c--d...b....  [c,d] is a proper subset of [a,b]
  ...c...a...d...b...  c < a < d < b
  ...c...a--b...d... [a,b] is a proper subset of [c,d]
  ...c--d...a--b.....  no intersection c < d < a < b.
Sums of powers of triangular numbers:
Row 2: Sum_{i = 2..n-1} C(i,2)^2 = C(n,3) + 6*C(n,4) + 6*C(n,5);
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.
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)
From _Peter Bala_, Feb 04 2018: (Start)
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)

Michael De Vlieger, Table of n, a(n) for n = 1..10000 (rows 1 <= n <= 100).
Peter Bala, Deformations of the Hadamard product of power series
Peter Bala, Notes on A122193
S. Eger, On the Number of Many-to-Many Alignments of N Sequences, arXiv:1511.00622 [math.CO], 2015.
J. Engbers and C. Stocker, Two Combinatorial Proofs of Identities Involving Sums of Powers of Binomial Coefficients, Integers 16 (2016), #A58.
M. Dukes and C. D. White, Web Matrices: Structural Properties and Generating Combinatorial Identities, arXiv:1603.01589 [math.CO], 2016.
IBM Ponder This, Jan 01 2001
J. B. Slowinski, The Number of Multiple Alignments, Molecular Phylogenetics and Evolution 10:2 (1998), 264-266. doi:10.1006/mpev.1998.0522

Row sums give A055203.
Cf. A078739, A005799, A019538, A131689, A154283, A299041, A087127.
For Sum_{i = 2..n} C(i,2)^k see A024166 (k = 2), A085438 - A085442 ( k = 3 thru 7).

# Note that the function implements the full triangle because it can be
# much better reused and referenced in this form.
A122193 := (n,k) -> A078739(n,k)*k!/2^n:
# Displays the truncated triangle from the definition:
seq(print(seq(A122193(n,k),k=2..2*n)),n=1..6); # Peter Luschny, Mar 25 2011

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

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
From Peter Bala, Jan 28 2018: (Start)
T(n,k) = Sum_{i = 0..k} (-1)^(k-i)*binomial(k,i)*(i*(i-1)/2)^n.
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).
n-th row polynomial R(n,x) = Sum_{i >= 2} (i*(i-1)/2)^n * x^i/(1+x)^(i+1) for n >= 1.
1/(1-x)*R(n,x/(1-x)) = Sum_{i >= 2} (i*(i-1)/2)^n*x^i for n >= 1.
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.
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^(k-2)*(1-x)^(2*n-k) are the row polynomials of A154283.
A154283 * A007318 equals the row reverse of this array.
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.
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.
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.
x^2*R(n,-1-x) = (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.
R(n,-2) = 4*R(n,1) = 4*A055203(n).
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,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)
From Peter Bala, Mar 08 2018: (Start)
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)).
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)

Definition corrected by Francisco Santos, Nov 17 2017

A062208 a(n) = Sum_{m>=0} binomial(m,3)^n*2^(-m-1).

Original entry on oeis.org

1, 1, 63, 16081, 10681263, 14638956721, 35941784497263, 143743469278461361, 874531783382503604463, 7687300579969605991710001, 93777824804632275267836362863, 1537173608464960118370398000894641, 32970915649974341628739088902163732463

Offset: 0

Angelo Dalli, Jun 13 2001

Number of alignments of n strings of length 3.

Conjectures: a(2*n) = 3 (mod 60) and a(2*n+1) = 1 (mod 60); for fixed k, the sequence a(n) (mod k) eventually becomes periodic with exact period a divisor of phi(k), where phi(k) is Euler's totient function A000010. - Peter Bala, Feb 04 2018

Alois P. Heinz, Table of n, a(n) for n = 0..100
J. B. Slowinski, The Number of Multiple Alignments, Molecular Phylogenetics and Evolution 10:2 (1998), 264-266. doi:10.1006/mpev.1998.0522

Cf. A000670, A055203, A001850, A126086.
See A062204 for further references, formulas and comments.
Cf. A001850, A062204, A062205, A299041.
Row n=3 of A262809.

A000629 := proc(n) local k ; sum( k^n/2^k,k=0..infinity) ; end: A062208 := proc(n) local a,stir,ni,n1,n2,n3,stir2,i,j,tmp ; a := 0 ; if n = 0 then RETURN(1) ; fi ; stir := combinat[partition](n) ; stir2 := {} ; for i in stir do if nops(i) <= 3 then tmp := i ; while nops(tmp) < 3 do tmp := [op(tmp),0] ; od: tmp := combinat[permute](tmp) ; for j in tmp do stir2 := stir2 union { j } ; od: fi ; od: for ni in stir2 do n1 := op(1,ni) ; n2 := op(2,ni) ; n3 := op(3,ni) ; a := a+combinat[multinomial](n,n1,n2,n3)*(A000629(3*n1+2*n2+n3)-1/2-2^(3*n1+2*n2+n3)/4)*(-3)^n2*2^n3 ; od: a/(2*6^n) ; end: seq(A062208(n),n=0..14) ; # R. J. Mathar, Apr 01 2008
a:=proc(n) options operator, arrow: sum(binomial(m, 3)^n*2^(-m-1),m=0.. infinity) end proc: seq(a(n),n=0..12); # Emeric Deutsch, Mar 22 2008

a[n_] = Sum[2^(-1-m)*((m-2)*(m-1)*m)^n, {m, 0, Infinity}]/6^n; a /@ Range[0, 12] (* Jean-François Alcover, Jul 13 2011 *)
With[{r = 3}, Flatten[{1, Table[Sum[Sum[(-1)^i*Binomial[j, i]*Binomial[j - i, r]^k, {i, 0, j}], {j, 0, k*r}], {k, 1, 15}]}]] (* Vaclav Kotesovec, Mar 22 2016 *)

From Vaclav Kotesovec, Mar 22 2016: (Start)
a(n) ~ 3^(2*n + 1/2) * n!^3 / (Pi * n * 2^(n+3) * (log(2))^(3*n+1)).
a(n) ~ sqrt(Pi)*3^(2*n+1/2)*n^(3*n+1/2) / (2^(n+3/2)*exp(3*n)*(log(2))^(3*n+1)).
(End)
a(n) = Sum_{k = 3..3*n} Sum_{i = 0..k} (-1)^(k-i)*binomial(k,i)* binomial(i,3)^n. Row sums of A299041. - Peter Bala, Feb 04 2018

New definition from Vladeta Jovovic, Mar 01 2008

Edited by N. J. A. Sloane, Sep 19 2009 at the suggestion of Max Alekseyev

A059516 Number of different relations between n intervals (possibly of zero length) on a line.

Original entry on oeis.org

1, 2, 26, 818, 47834, 4488722, 617364026, 117029670578, 29247820616474, 9318336983422802, 3686400233750527226, 1772940711343815069938, 1018732890334074636017114, 689260602916515788253448082, 542377407779814380777057527226, 491141384755777675851883392430898

Offset: 0

Henry Bottomley, Jan 19 2001

			a(1)=2 since if a is starting point of interval and A is end point then possibilities are aA (zero length) or a-A (positive length). a(2)=26 since possibilities are: aAbB, aAb-B, b-aAB, abB-A, a-AbB, ab-AB, aA-bB, bB-aA, aA-b-B, b-aA-B, b-B-aA, bB-a-A, a-bB-A, a-A-bB, ab-A-B, ab-B-A, a-b-AB, b-a-AB, a-bA-B, b-a-AB, a-A-b-B, a-b-A-B, a-b-B-A, b-B-a-A, b-a-B-A, b-a-A-B.

Alois P. Heinz, Table of n, a(n) for n = 0..224
IBM Ponder This, Jan 01 2001

Row n=2 of A316674. Row sums of A300729.

b:= proc(n) option remember; `if`(n=0, 1,
      add(b(n-j)*binomial(n, j), j=1..n))
    end:
a:= n-> add(b(n+k)*binomial(n, k), k=0..n)/2^n:
seq(a(n), n=0..20);  # Alois P. Heinz, Jul 10 2018

T[0, 0] = 1; T[n_, k_] := Sum[(-1)^(k-i) Binomial[k, i] (i(i+1)/2)^n, {i, 0, k}];
a[n_] := Sum[T[n, k], {k, 1, 2n}]; a[0] = 1;
a /@ Range[0, 20] (* Jean-François Alcover, Oct 27 2020, from A300729 *)

a(n) = 2*A055203(n)-0^n = Sum_k A059515(k, n).
a(n) = Sum_{m>=0} binomial(m+1,2)^n/2^(m+1). a(n) = (1/2^n)*Sum_{k=0..n} binomial(n,k)*A000670(n+k). - Vladeta Jovovic, Aug 17 2006
E.g.f. as a continued fraction: 1/(1 + 2*(1 - exp(t))/(1 + 2*(1 - exp(2*t))/(1 + 2*(1 - exp(3*t))/(1 + ...)))) = 1 + 2*t + 26*t^2/2! + .... See A300729. - Peter Bala, Jun 13 2019

cp's OEIS Frontend

A058809 The sequence lambda(3,n), where lambda is defined in A055203. Number of ways of placing n identifiable positive intervals with a total of exactly three starting and/or finishing points.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A059116 The sequence lambda(4,n), where lambda is defined in A055203. Number of ways of placing n identifiable positive intervals with a total of exactly four starting and/or finishing points.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

PARI

Formula

A059117 Square array of lambda(k,n), where lambda is defined in A055203. Number of ways of placing n identifiable positive intervals with a total of exactly k starting and/or finishing points.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A121316 Unlabeled version of A055203: number of different relations between n intervals (of nonzero length) on a line, up to permutation of intervals.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A058810 The sequence lambda(n,n), where lambda is defined in A055203.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A262809 Number A(n,k) of lattice paths from {n}^k to {0}^k using steps that decrement one or more components by one; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A078739 Triangle of generalized Stirling numbers S_{2,2}(n,k) read by rows (n>=1, 2<=k<=2n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs