A213276 Number A(n,k) of n-length words w over a k-ary alphabet such that 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; square array A(n,k), n>=0, k>=0, read by antidiagonals.
1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 4, 1, 0, 1, 4, 9, 5, 1, 0, 1, 5, 16, 18, 9, 1, 0, 1, 6, 25, 46, 36, 14, 1, 0, 1, 7, 36, 95, 118, 74, 27, 1, 0, 1, 8, 49, 171, 315, 276, 165, 46, 1, 0, 1, 9, 64, 280, 711, 895, 712, 367, 91, 1, 0, 1, 10, 81, 428, 1414, 2506, 2535, 1805, 869, 162, 1, 0
Offset: 0
Examples
A(0,k) = 1: the empty word.
A(n,1) = 1: (a)^n for alphabet {a}.
A(1,k) = k: number of words = size of the alphabet.
A(2,k) = k^2: all words with 2 letters from the alphabet.
A(3,2) = 5: aaa, aab, aba, baa, bbb for alphabet {a,b}.
A(3,3) = 18: aaa, aab, aac, aba, abc, aca, acb, baa, bac, bbb, bbc, bca, bcb, caa, cab, cba, cbb, ccc.
A(4,2) = 9: aaaa, aaab, aaba, aabb, abaa, abab, baaa, baab, bbbb.
A(5,2) = 14: aaaaa, aaaab, aaaba, aaabb, aabaa, aabab, aabba, abaaa, abaab, ababa, baaaa, baaab, baaba, bbbbb.
Square array A(n,k) begins:
1, 1, 1, 1, 1, 1, 1, 1, ...
0, 1, 2, 3, 4, 5, 6, 7, ...
0, 1, 4, 9, 16, 25, 36, 49, ...
0, 1, 5, 18, 46, 95, 171, 280, ...
0, 1, 9, 36, 118, 315, 711, 1414, ...
0, 1, 14, 74, 276, 895, 2506, 6104, ...
0, 1, 27, 165, 712, 2535, 8151, 23527, ...
0, 1, 46, 367, 1805, 7280, 25781, 83916, ...
Links
- Alois P. Heinz, Antidiagonals n = 0..24, flattened
Crossrefs
Programs
-
Maple
A:= (n, k)-> h(n, k, 0, []): h:= proc(n, k, m, l) option remember; `if`(n=0 and k=0, b(l), `if`(k=0 or n>0 and n -
Mathematica
a[n_, k_] := h[n, k, 0, {}]; 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]]]]; 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]}]]; 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]; Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Dec 11 2013, translated from Maple *)
Formula
T(n,k) = Sum_{i=0..k} C(k,i) * A257783(n,k-i).