A256161 Triangle of allowable Stirling numbers of the second kind a(n,k).

1, 1, 1, 1, 2, 1, 1, 3, 4, 1, 1, 4, 11, 6, 1, 1, 5, 26, 23, 9, 1, 1, 6, 57, 72, 50, 12, 1, 1, 7, 120, 201, 222, 86, 16, 1, 1, 8, 247, 522, 867, 480, 150, 20, 1, 1, 9, 502, 1291, 3123, 2307, 1080, 230, 25, 1, 1, 10, 1013, 3084, 10660, 10044, 6627, 2000, 355, 30, 1

Offset: 1

Author

Margaret A. Readdy, Mar 16 2015

Keywords

• nonn
• tabl

Comments

Row sums = A007476 starting (1, 2, 4, 9, 23, 65, 199, 654, 2296, 8569, ...).

a(n,k) counts restricted growth words of length n in the letters {1, ..., k} where every even entry appears exactly once.

Examples

			a(4,1) = 1 via 1111;
a(4,2) = 3 via 1211, 1121, 1112;
a(4,3) = 4 via 1213, 1231, 1233, 1123;
a(4,4) = 1 via 1234.
Triangle starts:
  1;
  1,  1;
  1,  2,  1;
  1,  3,  4,  1;
  1,  4, 11,  6,  1;
  ...
		

Links

• Yue Cai and Margaret Readdy, Negative q-Stirling numbers, arXiv:1506.03249 [math.CO], 2015.

Crossrefs

Cf. A007476 (row sums), A246118 (essentially the same triangle).

Programs

Mathematica

a[, 1] = a[n, n_] = 1;
a[n_, k_] := a[n, k] = a[n-1, k-1] + Ceiling[k/2] a[n-1, k];
Table[a[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Dec 15 2018 *)

Formula

a(n,k) = a(n-1,k-1) + ceiling(k/2)*a(n-1,k) for n >= 1 and 1 <= k <= n with boundary conditions a(n,0) = KroneckerDelta[n,0].

a(n,2) = n-1.

a(n,n-1) = floor(n/2)*ceiling(n/2).