A257783 Number T(n,k) of words w of length n such that each letter of the k-ary alphabet is used at least once and for every prefix z of w we have #(z,a_i) = 0 or #(z,a_i) >= #(z,a_j) for all j>i and #(z,a_i) counts the occurrences of the i-th letter in z; triangle T(n,k), n>=0, 0<=k<=n, read by rows.
1, 0, 1, 0, 1, 2, 0, 1, 3, 6, 0, 1, 7, 12, 24, 0, 1, 12, 35, 60, 120, 0, 1, 25, 87, 210, 360, 720, 0, 1, 44, 232, 609, 1470, 2520, 5040, 0, 1, 89, 599, 1961, 4872, 11760, 20160, 40320, 0, 1, 160, 1591, 5952, 17649, 43848, 105840, 181440, 362880, 0, 1, 321, 4202, 19255, 60465, 176490, 438480, 1058400, 1814400, 3628800
Offset: 0
Examples
T(5,2) = 12: aaaab, aaaba, aaabb, aabaa, aabab, aabba, abaaa, abaab, ababa, baaaa, baaab, baaba. Triangle T(n,k) begins: 1; 0, 1; 0, 1, 2; 0, 1, 3, 6; 0, 1, 7, 12, 24; 0, 1, 12, 35, 60, 120; 0, 1, 25, 87, 210, 360, 720; 0, 1, 44, 232, 609, 1470, 2520, 5040; 0, 1, 89, 599, 1961, 4872, 11760, 20160, 40320;
Links
- Alois P. Heinz, Rows n = 0..20, flattened
Crossrefs
Programs
-
Mathematica
g[l_, i_] := Module[{j}, If[l[[i]] < 1, Return[False], If[l[[i]] > 1, For[j = i + 1, j <= Length[l], j++, If[l[[i]] <= l[[j]], Return[False], If[l[[j]] > 0, Break[]]]]]]; True]; b[l_] := b[l] = If[Complement[l, {0}] == {}, 1, Sum[If[g[l, i], b[ReplacePart[l, i -> l[[i]] - 1]], 0], {i, 1, Length[l]}]]; h[n_, k_, m_, l_] := h[n, k, m, l] = If[n == 0 && k === 0, b[l], If[k == 0 || n > 0 && n < m, 0, Sum[h[n - j, k - 1, Max[m, j], Join[{j}, l]], {j, Max[1, m], n}] + h[n, k - 1, m, Join[{0}, l]]]]; A[n_, k_] := h[n, k, 0, {}]; T[n_, k_] := Sum[(-1)^i*Binomial[k, i]*A[n, k - i], {i, 0, k}]; Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jun 01 2022, after Alois P. Heinz in A213276 *)
Formula
T(n,k) = Sum_{i=0..k} (-1)^i * C(k,i) * A213276(n,k-i).
Comments