A078739 -id:A078739 - cp's OEIS frontend

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

1, 6, 6, 1, 72, 168, 96, 18, 1, 1440, 5760, 6120, 2520, 456, 36, 1, 43200, 259200, 424800, 285120, 92520, 15600, 1380, 60, 1, 1814400, 15120000, 34776000, 33566400, 16304400, 4379760, 682200, 62400, 3270, 90, 1, 101606400, 1117670400

Offset: 1

N. J. A. Sloane, Dec 21 2002

The sequence of row lengths of this array is [1,3,5,7,...] = A005408(n-1), n>=1.

For the scaled array s2_{3,2}(n,k) := a(n,k)*k!/((n+1)!*n!) see A090452.

			1;
6, 6, 1;
72, 168, 96, 18, 1;
...

Michael De Vlieger, Table of n, a(n) for n = 1..10000 (rows 1 <= n <= 100, flattened).
Paul Barry, Generalized Catalan Numbers Associated with a Family of Pascal-like Triangles, J. Int. Seq., Vol. 22 (2019), Article 19.5.8.
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.
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.
W. Lang, First 6 rows.
Toufik Mansour, Matthias Schork and Mark Shattuck, The Generalized Stirling and Bell Numbers Revisited, Journal of Integer Sequences, Vol. 15 (2012), #12.8.3.
M. Schork, On the combinatorics of normal ordering bosonic operators and deforming it, J. Phys. A 36 (2003) 4651-4665.

Row sums give A078738. Cf. A078739.

Cf. A005408, A090452.

a[n_, k_] := (-1)^k*n!*(n+1)!*HypergeometricPFQ[{2-k, n+1, n+2}, {2, 3}, 1]/(2*(k-2)!); Table[a[n, k], {n, 1, 7}, {k, 2, 2*n}] // Flatten (* Jean-François Alcover, Dec 04 2013 *)

Recursion: a(n, k) = Sum(binomial(2, p)*fallfac(n-1-p+k, 2-p)*a(n-1, k-p), p=0..2), n>=2, 2<=k<=2*n, a(1, 1)=1, else 0. Rewritten from eq.(19) of the Schork reference with r=3, s=2. fallfac(n, m) := A008279(n, m) (falling factorials triangle).
a(n, k) = (((-1)^k)/k!)*Sum(((-1)^p)*binomial(k, p)*product(fallfac(p+(j-1)*(3-2), 2), j=1..n), p=2..k), n>=1, 2<=k<=2*n, else 0. From eq. (12) of the Blasiak et al. reference with r=3, s=2.
a(n, k) = (-1)^k n! (n+1)! 3F2(2-k, n+1, n+2; 2, 3; 1) / (2(k-2)!). - Jean-François Alcover, Dec 04 2013

Edited by Wolfdieter Lang, Dec 23 2003

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

Original entry on oeis.org

1, 6, 18, 9, 1, 36, 540, 1242, 882, 243, 27, 1, 216, 13608, 94284, 186876, 149580, 56808, 11025, 1107, 54, 1, 1296, 330480, 6148872, 28245672, 49658508, 41392620, 18428400, 4691412, 706833, 63375, 3285, 90, 1, 7776, 7954848, 380841264, 3762380016, 13062960720

Offset: 1

N. J. A. Sloane, Dec 21 2002

The sequence of row lengths for this array is [1,4,7,10,..]= A016777(n-1), n>=1.
The g.f. for the k-th column, (with leading zeros and k>=3) is G(k,x)= x^ceiling(k/3)*P(k,x)/product(1-fallfac(p,3)*x,p=3..k), with fallfac(n,m) := A008279(n,m) (falling factorials) and P(k,x) := sum(A089517(k,m)*x^m,m=0..kmax(k)), k>=3, with kmax(k) := A004523(k-3)= floor(2*(k-3)/3)= [0,0,1,2,2,3,4,4,5,...]. For the recurrence of the G(k,x) see A089517. Wolfdieter Lang, Dec 01 2003
For the computation of the k-th column sequence see A090219.
Codara et al., show that T(n,k) gives the number of k-colorings of the graph nK_3 (the disjoint union of n copies of the complete graph K_3). An example is given below. - Peter Bala, Aug 15 2013

			From _Peter Bala_, Aug 15 2013: (Start)
The table begins
n\k |   3     4     5      6      7     8     9   10  11  12
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
  1 |   1
  2 |   6    18     9      1
  3 |  36   540  1242    882    243    27     1
  4 | 216 13608 94284 186876 149580 56808 11025 1107  54   1
...
Graph coloring interpretation of T(2,3) = 6:
The graph 2K_3 is 2 copies of K_3, the complete graph on 3 vertices:
    o b      o e
   / \      / \
  o---o    o---o
  a   c    d   f
The six 3-colorings of 2K_3 are ad|be|cf, ad|bf|ce, ae|bd|cf, ae|bf|cd, af|bd|ce, and af|be|cd. (End)

P. Blasiak, K. A. Penson and A. I. Solomon, The Boson Normal Ordering Problem and Generalized Bell Numbers
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.
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.
W. Lang, First 6 rows.

Row sums give A069223. Cf. A078739.
The column sequences (without leading zeros) are A000400 (powers of 6), 18*A089507, 9*A089518, A089519, etc.
A089504, A069223 (row sums), A090212 (alternating row sums).
A078740, A090214.

a[n_, k_] := (-1)^k*Sum[(-1)^p*((p-2)*(p-1)*p)^n*Binomial[k, p], {p, 3, k}]/k!; Table[a[n, k], {n, 1, 6}, {k, 3, 3*n}] // Flatten (* Jean-François Alcover, Dec 04 2013 *)

a(n, k) = (((-1)^k)/k!)*Sum_{p = 3..k} (-1)^p* binomial(k, p)*fallfac(p, 3)^n, with fallfac(p, 3) := A008279(p, 3) = p*(p-1)*(p-2); 3 <= k <= 3*n, n >= 1, else 0. From eq.(19) with r = 3 of the Blasiak et al. reference.
E^n = Sum_{k = 3..3*n} a(n,k)*x^k*D^k where D is the operator d/dx, and E the operator x^3d^3/dx^3.
The row polynomials R(n,x) are given by the Dobinski-type formula R(n,x) = exp(-x)*Sum_{k >= 0} (k*(k-1)*(k-2))^n*x^k/k!. - Peter Bala, Aug 15 2013

A055203 Number of different relations between n intervals on a line.

Original entry on oeis.org

1, 1, 13, 409, 23917, 2244361, 308682013, 58514835289, 14623910308237, 4659168491711401, 1843200116875263613, 886470355671907534969, 509366445167037318008557, 344630301458257894126724041, 271188703889907190388528763613, 245570692377888837925941696215449

Offset: 0

Sylviane R. Schwer (schwer(AT)lipn.univ-paris13.fr), Jun 22 2000

From Peter Bala, Jan 30 2018: (Start)
Number of alignments of n strings of length 2 (see Slowinski).
Conjectures: a(n) == 1 (mod 12); 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. (End)

			In case n = 2 this is the Delannoy number a(2) = D(2,2) = 13.
a(2) = 13 because if you have two intervals [a1,a2] and [b1,b2], using a for a1 or a2 and b for b1 or b2 and writing c if an a is at the same place as a b, we get the following possibilities: aabb, acb, abab, cab, abc, baab, abba, cc, bac, cba, baba, bca, bbaa.

S. R. Schwer, Dépendances temporelles: les mots pour le dire, Journées Intelligence Artificielle, 1998.
S. R. Schwer, Enumerating and generating Allen's algebra, in preparation.

T. D. Noe, Table of n, a(n) for n = 0..100
Tim Fernando and Carl Vogel, Prior Probabilities of Allen Interval Relations over Finite Orders, 11th International Conference on Agents and Artificial Intelligence (NLPinAI 2019) Prague.
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
Peter Stockman, Upper Bounds on the Time Complexity of Temporal CSPs, Linköping University | Department of Computer science, Master's thesis, 30 ECTS | Datateknik 2016 | LIU-IDA/LITH-EX-A--16/022--SE.
David Adam Woods, Strings for Temporal Annotation and Semantic Representation of Events, Ph. D. Dissertation, Univ. of Dublin, Trinity College (Ireland, 2022).

Cf. A035317, A055809, A055810, A078739, A122193, A062208.

Row n=2 of A262809.

lambda := proc(p,n) option remember; if n = 1 then if p = 2 then RETURN(1) else RETURN(0) fi; else RETURN((p*(p-1)/2)*(lambda(p,n-1)+2*lambda(p-1,n-1)+lambda(p-2,n-1))) fi; end; A055203 := n->add(lambda(i,n),i=2..2*n);
A055203 := proc(n) local k; add(A078739(n,k)*k!,k=0..2*n)/2^n end:
seq(A055203(n),n=0..15); # Peter Luschny, Mar 25 2011
# second Maple program:
b:= proc(n) option remember; `if`(n=0, 1,
      add(b(n-j)*binomial(n, j), j=1..n))
    end:
a:= n-> ceil(add(b(n+k)*binomial(n, k), k=0..n)/2^(n+1)):
seq(a(n), n=0..20);  # Alois P. Heinz, Jul 10 2018

a[n_] := Sum[((m-1)*m)^n / 2^(m+n+1), {m, 0, Infinity}]; Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Oct 10 2011, after Vladeta Jovovic *)
With[{r = 2}, 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 *)

a(n) = Sum_{i=2..2n} lambda(i, n), with lambda(p, 1) = 1 if p = 2, otherwise 0; lambda(p, n) = (p*(p-1)/2)*(lambda(p, n-1) + 2*lambda(p-1, n-1) + lambda(p-2, n-1)).
lambda(p, n) = Sum_k[( - 1)^(p + k) * C(p, k) * ((k - 1)*k/2)^n]. So if T(m, 0), T(m, 1), ..., T(m, m) is any row of A035317 with m >= 2n - 1 then a(n) = Sum_j[(-1)^j * T(m, j) * ((m - j + 1)*(m - j)/2)^n]; e.g., a(2) = 13 = 1*6^2 - 3*3^2 + 4*1^2 - 2*0^2 = 1*10^2 - 4*6^2 + 7*3^2 - 6*1^2 + 3*0^2 = 1*15^2 - 5*10^2 + 11*6^2 - 13*3^2 + 9*1^2 - 3*0^2 etc. while a(3) = 409 = 1*15^3 - 5*10^3 + 11*6^3 - 13*3^3 + 9*1^3 - 3*0^3 etc. - Henry Bottomley, Jan 03 2001
Row sums of A122193. - Vladeta Jovovic, Aug 24 2006
a(n) = Sum_{k=0..n} k!*Stirling2(n,k)*A121251(k). - Vladeta Jovovic, Aug 25 2006
E.g.f.: Sum_{m>=0} exp(x*binomial(m,2))/2^(m+1). - Vladeta Jovovic, Sep 24 2006
a(n) = Sum_{m>=0} binomial(m,2)^n/2^(m+1). - Vladeta Jovovic, Aug 17 2006
a(n) = (1/2^n)*Sum_{k=0..n} (-1)^(n-k)*binomial(n,k)*A000670(n+k). - Vladeta Jovovic, Aug 17 2006
a(n) ~ n! * n^n * 2^(n-1) / (exp(n) * (log(2))^(2*n+1)). - Vaclav Kotesovec, Mar 15 2014
From Peter Bala, Jan 30 2018: (Start)
a(n) = Sum_{k = 2..2*n} Sum_{i = 0..k} (-1)^(k-i)*binomial(k,i)*(i*(i-1)/2)^n.
a(n) = (1/2^(n+1))*Sum_{k = 0..n} binomial(n,k)*A000670(n+k) for n >= 1. (End)

More terms from Larry Reeves (larryr(AT)acm.org), Oct 04 2000

More terms from N. J. A. Sloane, Jan 03 2001

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

A090214 Generalized Stirling2 array S_{4,4}(n,k).

Original entry on oeis.org

1, 24, 96, 72, 16, 1, 576, 13824, 50688, 59904, 30024, 7200, 856, 48, 1, 13824, 1714176, 21606912, 76317696, 110160576, 78451200, 30645504, 6976512, 953424, 78400, 3760, 96, 1, 331776, 207028224, 8190885888, 74684104704, 253100173824

Offset: 1

Wolfdieter Lang, Dec 01 2003

The row length sequence for this array is [1,5,9,13,17,...] = A016813(n-1), n >= 1.
The g.f. for the k-th column, (with leading zeros and k >= 4) is G(k,x) = x^ceiling(k/4)*P(k,x)/Product_{p = 4..k} (1 - fallfac(p,4)*x), with fallfac(n,m) := A008279(n,m) (falling factorials) and P(k,x) := Sum_{m = 0..kmax(k)} A090221(k,m)*x^m, k >= 4, with kmax(k) := A057353(k-4)= floor(3*(k-4)/4). For the recurrence of the G(k,x) see A090221.
Codara et al., show that T(n,k) gives the number of k-colorings of the graph nK_4 (the disjoint union of n copies of the complete graph K_4). - Peter Bala, Aug 15 2013

			Table begins
n\k|   4      5      6      7      8     9   10   11   12
= = = = = = = = = = = = = = = = = = = = = = = = = = = = =
1  |   1
2  |  24     96     72     16      1
3  | 576  13824  50688  59904  30024  7200  856   48    1
...

Robert Israel, Table of n, a(n) for n = 1..10011 (rows 1 to 71, flattened)
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.
P. Codara, O. M. D’Antona, and P. Hell, A simple combinatorial interpretation of certain generalized Bell and Stirling numbers, arXiv:1308.1700v1 [cs.DM], 2013.
A. Dzhumadildaev and D. Yeliussizov, Path decompositions of digraphs and their applications to Weyl algebra, arXiv preprint arXiv:1408.6764v1 [math.CO], 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.
Wolfdieter Lang, First 4 rows.
M. Schork, On the combinatorics of normal ordering bosonic operators and deforming it, J. Phys. A 36 (2003) 4651-4665.

Cf. A090215, A071379 (row sums), A090213 (alternating row sums).

S_{1, 1} = A008277, S_{2, 1} = A008297 (ignoring signs), S_{3, 1} = A035342, S_{2, 2} = A078739, S_{3, 2} = A078740, S_{3, 3} = A078741.

T:= (n,k) -> (-1)^k/k!*add((-1)^p*binomial(k,p)*(p*(p-1)*(p-2)*(p-3))^n,p=4..k):
seq(seq(T(n,k),k=4..4*n),n=1..10); # Robert Israel, Jan 28 2016

a[n_, k_] := (((-1)^k)/k!)*Sum[((-1)^p)*Binomial[k, p]*FactorialPower[p, 4]^n, {p, 4, k}]; Table[a[n, k], {n, 1, 5}, {k, 4, 4*n}] // Flatten (* Jean-François Alcover, Sep 05 2012, updated Jan 28 2016 *)

a(n, k) = (-1)^k/k! * Sum_{p = 4..k} (-1)^p * binomial(k, p) * fallfac(p, 4)^n,  with fallfac(p, 4) := A008279(p, 4) = p*(p - 1)*(p - 2)*(p - 3); 4 <= k <= 4*n, n >= 1, else 0. From eq.(19) with r = 4 of the Blasiak et al. reference.
E^n = Sum_{k = 4..4*n} a(n,k)*x^k*D^k where D is the operator d/dx, and E the operator (x^4)*d^4/dx^4.
The row polynomials R(n,x) are given by the Dobinski-type formula R(n,x) = exp(-x)*Sum_{k >= 0} (k*(k - 1)*(k - 2)*(k - 3))^n*x^k/k!. - Peter Bala, Aug 15 2013

A092077 Generalized Stirling2 array (8,2).

Original entry on oeis.org

1, 56, 16, 1, 10192, 4928, 776, 48, 1, 3872960, 2477440, 575680, 63360, 3536, 96, 1, 2517424000, 1940556800, 572868800, 86163840, 7326880, 364800, 10480, 160, 1, 2497284608000, 2210343116800, 773352966400, 143430604800, 15836206400, 1099612800, 49056960, 1398400, 24520, 240, 1

Offset: 1

Wolfdieter Lang, Feb 27 2004

The sequence of row lengths for this array is [1,3,5,7,9,11,...]=A005408(n-1), n>=1.

P. Blasiak, K. A. Penson and A. I. Solomon, The general boson normal ordering problem, arXiv:quant-ph/0402027, 2004.
Wolfdieter Lang, First 6 rows.
M. Schork, On the combinatorics of normal ordering bosonic operators and deforming it, J. Phys. A 36 (2003) 4651-4665.

The generalized (k, 2)-Stirling2 arrays are, for k=2, ..., 7: A078739, A078740, A090438, A091534, A091746 and A091747.

Cf. A091546, A091552 (first, resp. second column). A091757 (row sums). A091758 (alternating row sums).

a[n_, k_] := ((-1)^k/k!) Sum[(-1)^p Binomial[k, p] Product[FactorialPower[ p + 6(j-1), 2], {j, 1, n}], {p, 2, k}];
Table[a[n, k], {n, 1, 6}, {k, 2, 2n}] // Flatten (* Jean-François Alcover, Feb 28 2020 *)

a(n, k) = (((-1)^k)/k!)*sum(((-1)^p)*binomial(k, p)*product(fallfac(p+6*(j-1), 2), j=1..n), p=2..k), n>=1, 2<=k<=2*n, else 0. From eq. (12) of the Blasiak et al. reference with r=8, s=2.

Recursion: a(n, k) = sum(binomial(2, p)*fallfac(6*(n-1)+k-p, 2-p)*a(n-1, k-p), p=0..2), n>=2, 2<=k<=2*n, a(1, 2)=1, else 0. Rewritten from eq.(19) of the Schork reference with r=8, s=2. fallfac(n, m) := A008279(n, m) (falling factorials triangle).

A262704 Triangle: Newton expansion of C(n,m)^3, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 6, 1, 0, 6, 24, 1, 0, 0, 114, 60, 1, 0, 0, 180, 690, 120, 1, 0, 0, 90, 2940, 2640, 210, 1, 0, 0, 0, 5670, 21840, 7770, 336, 1, 0, 0, 0, 5040, 87570, 107520, 19236, 504, 1, 0, 0, 0, 1680, 189000, 735210, 407400, 42084, 720, 1, 0, 0, 0, 0, 224700, 2835756, 4280850, 1284360, 83880, 990, 1

Offset: 0

Giuliano Cabrele, Sep 27 2015

Triangle here T_3(n,m) is such that C(n,m)^3 = Sum_{j=0..n} C(n,j)*T_3(j,m).
Equivalently, lower triangular matrix T_3 such that
|| C(n,m)^3 || = A181583 =  P * T_3 = A007318 * T_3.
T_3(n,m) = 0 for n < m and for 3*m < n. In fact:
C(x,m)^q and C(x,m), with m nonnegative and q positive integer, are polynomial in x of degree m*q and m respectively, and C(x,m) is a divisor of C(x,m)^q.
Therefore the Newton series will give C(x,m)^q = T_q(m,m)*C(x,m) + T_q(m+1,m)*C(x,m+1) + ... + T_q(q*m,m)*C(x,q*m), where T_q(n,m) is the n-th forward finite difference of C(x,m)^q at x = 0.
Example:
C(x,2)^3 = x^3*(x-1)^3 / 8 = 1*C(x,2) + 24*C(x,3) + 114*C(x,4) + 180*C(x,5) + 90*C(x,6);
C(5,2)^3 = C(5,3)^3 = 1000 = 1*C(5,2) + 24*C(5,3) + 114*C(5,4) + 180*C(5,5) = 1*C(5,3) + 60*C(5,4) + 690*C(5,5).
So we get the expansion of the 3rd power of the binomial coefficient in terms of the binomial coefficients on the same row.
T_1 is the unitary matrix,
T_2 is the transpose of A109983,
T_3 is this sequence,
T_4, T_5 are A262705, A262706.

			Triangle starts:
n\m  [0]     [1]     [2]     [3]     [4]     [5]     [6]     [7]     [8]
[0]  1;
[1]  0,      1;
[2]  0,      6,      1;
[3]  0,      6,      24,     1;
[4]  0,      0,      114,    60,     1;
[5]  0,      0,      180,    690,    120,    1;
[6]  0,      0,      90,     2940,   2640,   210,    1;
[7]  0,      0,      0,      5670,   21840,  7770,   336,    1;
[8]  0,      0,      0,      5040,   87570,  107520, 19236,  504,    1;
[9]  ...

Gheorghe Coserea, Rows n = 0..200, flattened
P. Blasiak, K. A. Penson and A. I. Solomon, The general boson normal ordering problem, arXiv:quant-ph/0402027, 2004.

Row sums are A172634, the inverse binomial transform of the Franel numbers (A000172).
Column sums are the A126086, per the comment given thereto by Brendan McKay.
Second diagonal (T_3(n+1,n)) is A007531 (n+2).
Column T_3(n,2) is A122193(3,n).
Cf. A109983 (transpose of), A262705, A262706.
Cf. A078739, A078741, A274786.

[&+[(-1)^(n-j)*Binomial(n,j)*Binomial(j,m)^3: j in [0..n]]: m in [0..n], n in [0..10]]; // Bruno Berselli, Oct 01 2015

T3[n_, m_] := Sum[(-1)^(n - j) * Binomial[n, j] * Binomial[j, m]^3, {j, 0, n}]; Table[T3[n, m], {n, 0, 10}, {m, 0, n}] // Flatten (* Jean-François Alcover, Oct 01 2015 *)

// as a function
T_3:=(n,m)->_plus((-1)^(n-j)*binomial(n,j)*binomial(j,m)^3 $ j=0..n):
// as a matrix h x h
_P:=h->matrix([[binomial(n,m) $m=0..h]$n=0..h]):
_P_3:=h->matrix([[binomial(n,m)^3 $m=0..h]$n=0..h]):
_T_3:=h->_P(h)^-1*_P_3(h):

T_3(nmax) = {for(n=0, nmax, for(m=0, n, print1(sum(j=0, n, (-1)^(n-j)*binomial(n,j)*binomial(j,m)^3), ", ")); print())} \\ Colin Barker, Oct 01 2015

t3(n,m) = sum(j=0, n,  (-1)^((n-j)%2)* binomial(n,j)*binomial(j,m)^3);
concat(vector(11, n, vector(n, k, t3(n-1,k-1)))) \\ Gheorghe Coserea, Jul 14 2016

T_3(n,m) = Sum_{j=0..n} (-1)^(n-j)*C(n,j)*C(j,m)^3.

Also, let S(r,s)(n,m) denote the Generalized Stirling2 numbers as defined in the link above,then T_3(n,m) = n! / (m!)^3 * S(m,m)(3,n).

A089503 Triangle of numbers used for basis change between certain falling factorials.

Original entry on oeis.org

1, 1, 4, 1, 12, 30, 1, 24, 168, 336, 1, 40, 540, 2880, 5040, 1, 60, 1320, 13200, 59400, 95040, 1, 84, 2730, 43680, 360360, 1441440, 2162160, 1, 112, 5040, 117600, 1528800, 11007360, 40360320, 57657600, 1, 144, 8568, 274176, 5140800, 57576960

Offset: 1

Wolfdieter Lang, Dec 01 2003

Used to relate array A078739 ((2,2)-Stirling2) to triangle A071951 (Legendre-Stirling).

			The triangle begins:
n\m 1   2    3      4       5        6        7        8 ...
1:  1
2:  1   4
3:  1  12   30
4:  1  24  168    336
5:  1  40  540   2880    5040
6:  1  60 1320  13200   59400    95040
7:  1  84 2730  43680  360360  1441440  2162160
8:  1 112 5040 117600 1528800 11007360 40360320 57657600
...
Row 9:  1 144 8568 274176 5140800 57576960 374250240 1283143680 1764322560
Row 10: 1 180 13680 574560 14651280 234420480 2344204800 14065228800 45711993600 60949324800.
Reformatted - _Wolfdieter Lang_, Apr 10 2013
n=3: fallfac(x+2,6) = 1*fallfac(x,6) + 12*fallfac(x,5) + 30*fallfac(x,4).

Wolfdieter Lang, First 9 rows.

eq[n_, x_] := Sum[FactorialPower[x, 1 - m + 2*n]*a[n, m], {m, 1, n}] == FactorialPower[x + n - 1, 2*n]; eq[n_] := Table[eq[n, x], {x, n + 1, 2*n}]; row[n_] := First[Table[a[n, m], {m, 1, n}] /. Solve[eq[n]]]; Array[row, 10] // Flatten (* Jean-François Alcover, Sep 02 2016 *)
a[n_,m_]:= Binomial[n-1,m-1]*Binomial[2n,m-1]*Gamma[m]; Table[a[n,m],{n,1,10},{m,1,n}] (* Stefano Negro, Nov 10 2021 *)

fallfac(x+n-1, 2*n) = Sum_{m=1..n} a(n, m)*fallfac(x, 2*n-(m-1)), n>=1 where fallfac(x, k) := Product_{j=1..k} (x+1-j), with fallfac(n, k) = A068424(n, k) (falling factorials). a(n, m) = 0 if n < m.

T(n, m) = binomial(n-1, m-1)*binomial(2n, m-1)*m!, for 1 <= m <= n, with binomial(n, m) = A007318. - Stefano Negro, Nov 10 2021

A262705 Triangle: Newton expansion of C(n,m)^4, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 14, 1, 0, 36, 78, 1, 0, 24, 978, 252, 1, 0, 0, 4320, 8730, 620, 1, 0, 0, 8460, 103820, 46890, 1290, 1, 0, 0, 7560, 581700, 1159340, 185430, 2394, 1, 0, 0, 2520, 1767360, 13387570, 8314880, 595476, 4088, 1, 0, 0, 0, 3087000, 85806000, 170429490, 44341584, 1642788, 6552, 1

Offset: 0

Giuliano Cabrele, Sep 30 2015

Triangle here T_4(n,m) is such that C(n,m)^4 = Sum_{j=0..n} C(n,j)*T_4(j,m).
Equivalently, lower triangular matrix T_4 such that
|| C(n,m)^4 || = A202750 =  P * T_4 = A007318 * T_4.
T_4(n,m) = 0 for n < m and for 4*m < n.
Refer to comment to A262704.
Example:
C(x,2)^4 = x^4*(x-1)^4 /16 = 1*C(x,2) + 78*C(x,3) + 978*C(x,4) + 4320*C(x,5) + 8460*C(x,6) + 7560*C(x,7) + 2520*C(x,8);
C(5,2)^4 = C(5,3)^4 = 10000 = 1*C(5,2) + 78*C(5,3) + 978*C(5,4) + 4320*C(5,5) = 1*C(5,3) + 252*C(5,4) + 8730*C(5,5).

			Triangle starts:
[1];
[0,  1];
[0, 14,    1];
[0, 36,   78,      1];
[0, 24,  978,    252,     1];
[0,  0, 4320,   8730,   620,    1];
[0,  0, 8460, 103820, 46890, 1290, 1];

P. Blasiak, K. A. Penson and A. I. Solomon, The general boson normal ordering problem, arXiv:quant-ph/0402027, 2004.

Row sums are, by definition, the inverse binomial transform of A005260.
Second diagonal (T_4(n+1,n)) is A058895(n+1).
Column T_4(n,2) is A122193(4,n).
Cf. A109983 (transpose of), A262704, A262706.
Cf. A078739, A078741.

[&+[(-1)^(n-j)*Binomial(n,j)*Binomial(j,m)^4: j in [0..n]]: m in [0..n], n in [0..10]]; // Bruno Berselli, Oct 01 2015

T4[n_, m_] := Sum[(-1)^(n - j) * Binomial[n, j] * Binomial[j, m]^4, {j, 0, n}]; Table[T4[n, m], {n, 0, 9}, {m, 0, n}] // Flatten (* Jean-François Alcover, Oct 01 2015 *)

// as a function
T_4:=(n,m)->_plus((-1)^(n-j)*binomial(n,j)*binomial(j,m)^4 $ j=0..n):
// as a matrix h x h
_P:=h->matrix([[binomial(n,m) $m=0..h]$n=0..h]):
_P_4:=h->matrix([[binomial(n,m)^4 $m=0..h]$n=0..h]):
_T_4:=h->_P(h)^-1*_P_4(h):

T_4(nmax) = {for(n=0, nmax, for(m=0, n, print1(sum(j=0, n, (-1)^(n-j)*binomial(n,j)*binomial(j,m)^4), ", ")); print())} \\ Colin Barker, Oct 01 2015

T_4(n,m) = Sum_{j=0..n} (-1)^(n-j)*C(n,j)*C(j,m)^4.

Also, let S(r,s)(n,m) denote the Generalized Stirling2 numbers as defined in the link above, then T_4(n,m) = n! / (m!)^4 * S(m,m)(4,n).

A262706 Triangle: Newton expansion of C(n,m)^5, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 30, 1, 0, 150, 240, 1, 0, 240, 6810, 1020, 1, 0, 120, 63540, 94890, 3120, 1, 0, 0, 271170, 2615340, 740640, 7770, 1, 0, 0, 604800, 32186070, 47271840, 4029690, 16800, 1, 0, 0, 730800, 214628400, 1281612570, 518276640, 17075940, 32760, 1, 0, 0, 453600, 859992000, 18459063000, 26947757970, 4027831080, 60171300, 59040, 1

Offset: 0

Giuliano Cabrele, Sep 30 2015

Triangle here T_5(n,m) is such that C(n,m)^5 = Sum_{j=0..n} C(n,j)*T_5(j,m).
Equivalently, lower triangular matrix T_5 such that
|| C(n,m)^5 ||  =  P * T_5 = A007318 * T_5.
T_5(n,m) = 0 for n < m and for 5*m < n.
Refer to comment to A262704.
Example:
C(x,2)^5 = x^5*(x-1)^5/32 = 1*C(x,2) + 240*C(x,3) + 6810*C(x,4) + 63540*C(x,5) + 271170*C(x,6) + 604800*C(x,7) + 730800*C(x,8) + 453600*C(x,9) + 113400*C(x,10);
C(5,2)^5 = C(5,3)^5 = 100000 = 1*C(5,2) + 240*C(5,3) + 6810*C(5,4) + 63540*C(5,5) = 1*C(5,3) + 1020*C(5,4) + 94890*C(5,5).

			Triangle starts:
[1];
[0,   1];
[0,  30,      1];
[0, 150,    240,       1];
[0, 240,   6810,    1020,      1];
[0, 120,  63540,   94890,   3120,    1];
[0,   0, 271170, 2615340, 740640, 7770, 1];

P. Blasiak, K. A. Penson and A. I. Solomon, The general boson normal ordering problem, arXiv:quant-ph/0402027, 2004.

Second diagonal (T_5(n+1,n)) is A061167(n+1).
Column T_5(n,2) is A122193(5,n).
Cf. A109983 (transpose of), A262704, A262705.
Cf. A078739, A078741.

[&+[(-1)^(n-j)*Binomial(n,j)*Binomial(j,m)^5: j in [0..n]]: m in [0..n], n in [0..10]]; // Bruno Berselli, Oct 01 2015

T5[n_, m_] := Sum[(-1)^(n - j) * Binomial[n, j] * Binomial[j, m]^5, {j, 0, n}]; Table[T5[n, m], {n, 0, 9}, {m, 0, n}] // Flatten (* Jean-François Alcover, Oct 01 2015 *)

// as a function
T_5:=(n,m)->_plus((-1)^(n-j)*binomial(n,j)*binomial(j,m)^5 $ j=0..n):
// as a matrix h x h
_P:=h->matrix([[binomial(n,m) $m=0..h]$n=0..h]):
_P_5:=h->matrix([[binomial(n,m)^5 $m=0..h]$n=0..h]):
_T_5:=h->_P(h)^-1*_P_5(h):

T_5(nmax) = {for(n=0, nmax, for(m=0, n, print1(sum(j=0, n, (-1)^(n-j)*binomial(n,j)*binomial(j,m)^5), ", ")); print())} \\ Colin Barker, Oct 01 2015

T_5(n,m) = Sum_{j=0..n} (-1)^(n-j)*C(n,j)*C(j,m)^5.

Also, let S(r,s)(n,m) denote the Generalized Stirling2 numbers as defined in the link above, then T_5(n,m) = n! / (m!)^5 * S(m,m)(5,n).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A055203 Number of different relations between n intervals on a line.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A090214 Generalized Stirling2 array S_{4,4}(n,k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A092077 Generalized Stirling2 array (8,2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A262704 Triangle: Newton expansion of C(n,m)^3, read by rows.

Views

Author

Keywords

Comments

Examples

Links