|
|
A225491
|
|
Maximal frequency depth for multisets over an alphabet of n letters.
|
|
1
|
|
|
0, 4, 5, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
Frequency depth is defined at A225485. Suppose S is a multiset on an alphabet y(1),..,y(n). Let f(n) > 0 be the frequency of y(i) in S, so that F(S) (as at A225485) is the multiset {f(1),..,f(m)}, where m is the number of distinct terms in S. Let {g(1),..,g(k)} be the set of distinct terms of F(S), and let h(i) be the number of occurrences of g(i) in F(S). Then F(F(S)) is a partition p(m) of m, and D(F(F(S))) = D(p(m)), where D denotes frequency depth. To maximize D for n>1, put m = n to get a(n) = 2 + A225486(n), for n > 1.
|
|
LINKS
|
|
|
FORMULA
|
a(1) = 0, a(n) = 2 + A225486(n) for n > 1.
|
|
EXAMPLE
|
For n = 2, let the alphabet be {u,v}. Then for some p>=0 and q>=0, S consists of p u's and q v's, so that F(S) = {p,q}. Assume without loss of generality that p<=q. If 1 <= p < q, then the depth of 4 is the number of arrows when we write S -> pq -> 11 -> 2 -> 1. The other possibilities (p = 0, or p=q) for p and q lead to depths < 4, so that a(2) = 4.
|
|
MATHEMATICA
|
c[s_] := c[s] = Select[Table[Count[s, i], {i, 1, Max[s]}], # > 0 &]
f[s_] := f[s] = Drop[FixedPointList[c, s], -2]
t[s_] := t[s] = Length[f[s]]
u[n_] := u[n] = Table[t[Part[IntegerPartitions[n], k]], {k, 1,
Length[IntegerPartitions[n]]}];
v = Table[Max[u[n]], {n, 2, 40}]; (* A225491 *)
Prepend[2 + v, 0]
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|