|
| |
|
|
A225485
|
|
Number of partitions of n that have frequency depth k, an array read by rows.
|
|
47
|
|
|
|
0, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 3, 1, 3, 4, 3, 1, 1, 4, 8, 1, 1, 3, 6, 9, 3, 1, 2, 8, 12, 7, 1, 3, 11, 17, 10, 1, 1, 11, 26, 17, 1, 5, 19, 25, 27, 1, 1, 17, 44, 38, 1, 3, 25, 53, 52, 1, 1, 3, 29, 63, 76, 4
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,8
|
|
|
COMMENTS
|
Let S = {x(1),...,x(k)} be a multiset whose distinct elements are y(1),...,y(h). Let f(i) be the frequency of y(i) in S. Define F(S) = {f(1),..,f(h)}, F(1,S) = F(S), and F(m,S) = F(F(m-1),S) for m>1. Then lim(F(m,S)) = {1} for every S, so that there is a least positive integer i for which F(i,S) = {1}, which we call the frequency depth of S.
Equivalently, the frequency depth of an integer partition is the number of times one must take the multiset of multiplicities to reach (1). For example, the partition (32211) has frequency depth 5 because we have: (32211) -> (221) -> (21) -> (11) -> (2) -> (1). - Gus Wiseman, Apr 19 2019
Below, m^n abbreviates the sum m+...+m of n terms. In the following list, the numbers p_1,...,p_k are distinct, m >= 1, and k >= 1. The forms of the partitions being counted are as follows:
column 1: [n],
column 2: [m^k],
column 3: [p_1^m,...,p_k^m],
column 4: [(p_1^m_1)^m,..., (p_k^m_k)^m], distinct numbers m_i.
Column 3 is of special interest. Assume first that m = 1, so that the form of partition being counted is p = [p_1,...,p_k], with conjugate given by [q_1,...,q_m] where q_i is the number of parts of p that are >= i. Since the p_i are distinct, the distinct parts of q are the integers 1,2,...,k. For the general case that m >= 1, the distinct parts of q are the integers m,...,km. Let S(n) denote the set of partitions of n counted by column 3. Then if a and b are in the set S*(n) of conjugates of partitions in S(n), and if a > b, then a - b is also in S*(n). Call this the subtraction property. Conversely, if a partition q has the subtraction property, then q must consist of a set of numbers m,..,km for some m. Thus, column 3 counts the partitions of n that have the subtraction property. (End)
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
The first 9 rows:
n = 1 .... 0
n = 2 .... 1..1
n = 3 .... 1..1..1
n = 4 .... 1..2..1..1
n = 5 .... 1..1..2..3
n = 6 .... 1..3..4..3
n = 7 .... 1..1..4..8..1
n = 8 .... 1..3..6..9..3
n = 9 .... 1..2..8.12..7
For the 7 partitions of 5, successive frequencies are shown here:
5 -> 1 (depth 1)
41 -> 11 -> 2 -> 1 (depth 3)
32 -> 11 -> 2 -> 1 (depth 3)
311 -> 12 -> 11 -> 2 -> 1 (depth 4)
221 -> 12 -> 11 -> 2 -> 1 (depth 4)
2111 -> 13 -> 11 -> 2 -> 1 (depth 4)
11111 -> 5 -> 1 (depth 2)
Summary: 1 partition has depth 1; 1 has depth 2; 2 have 3; and 3 have 4, so that the row for n = 5 is 1..1..2..3 .
|
|
|
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], i]],
{i, 1, Length[IntegerPartitions[n]]}];
Flatten[Table[Count[u[n], k], {n, 2, 25}, {k, 1, Max[u[n]]}]]
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,tabf
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
