login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A321704
Number of words w of length n over an n-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.
1
1, 1, 4, 18, 118, 895, 8151, 83916, 977026, 12602451, 178880725, 2766415036, 46314488705, 834067614601, 16074694453741, 330017679352180, 7188779521480810
OFFSET
0,3
FORMULA
a(n) = A213276(n,n).
EXAMPLE
a(3) = 18: aaa, aab, aac, aba, abc, aca, acb, baa, bac, bbb, bbc, bca, bcb, caa, cab, cba, cbb, ccc.
MAPLE
h:= proc(n, k, m, l) option remember;
`if`(n=0 and k=0, b(l), `if`(k=0 or n>0 and n<m, 0,
add(h(n-j, k-1, max(m, j), [j, l[]]), j=max(1, m)..n)
+h(n, k-1, m, [0, l[]], [])))
end:
b:= proc(l) option remember;
`if`({l[]} minus {0}={}, 1, add(`if`(g(l, i),
b(subsop(i=l[i]-1, l)), 0), i=1..nops(l)))
end:
g:= proc(l, i) local j;
if l[i]<1 then return false
elif l[i]>1 then for j from i+1 to nops(l) do
if l[i]<=l[j] then return false
elif l[j]>0 then break
fi od fi; true
end:
a:= n-> h(n$2, 0, []):
seq(a(n), n=0..10); # Alois P. Heinz, Mar 29 2020
MATHEMATICA
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];
a[n_] := h[n, n, 0, {}];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 15}] (* Jean-François Alcover, Jun 01 2022, after Alois P. Heinz *)
CROSSREFS
Main diagonal of A213276.
Sequence in context: A278994 A223008 A162224 * A296982 A222375 A053529
KEYWORD
nonn,more
AUTHOR
Alois P. Heinz, Nov 17 2018
STATUS
approved