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,5

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.

Links

Table of n, a(n) for n=1..66.

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

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

Example

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

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

Crossrefs

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

Sequence in context: A137153 A340814 A063841 * A137596 A111669 A336573

Adjacent sequences: A256158 A256159 A256160 * A256162 A256163 A256164

Keyword

nonn,tabl

Author

Margaret A. Readdy, Mar 16 2015

Status

approved