A225491 Maximal frequency depth for multisets over an alphabet of n letters.

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

Offset: 1

Author

Clark Kimberling, May 09 2013

Keywords

• nonn

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.

Examples

			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.
		

Links

• Clark Kimberling, Table of n, a(n) for n = 1..40

Crossrefs

Cf. A225485, A225486.

Programs

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]

Formula

a(1) = 0, a(n) = 2 + A225486(n) for n > 1.