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

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

Author

N. J. A. Sloane, Dec 21 2002

Keywords

• nonn
• tabf
• easy

Comments

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

Examples

			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)
		

Links

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

Crossrefs

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.

Programs

Maple

# 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

Mathematica

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

Formula

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

Extensions

More terms from Wolfdieter Lang, Nov 07 2003