|
| |
|
|
A141199
|
|
Number of hierarchical ordered partitions of partitions.
|
|
20
|
|
|
|
1, 1, 3, 7, 17, 38, 87, 191, 421, 911, 1963, 4186, 8885, 18724, 39284, 82005, 170521, 353214, 729290, 1501184, 3081869, 6311404, 12896983, 26301515, 53541702, 108815626, 220824295, 447524559, 905850001, 1831526719
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
Consider the "ordered partitions of partitions" as described in A055887. They are produced by introducing separators (a term used by J. Riordan) between the parts of a partition. If a partition has P parts, then it is possible to introduce 1, 2, ... P-1 separators. Let "|" denote such a separator. We just append 1,2,...,P-1 separators to each integer partition of n and subsequently form all permutation of the resulting list (which is composed of parts and separators).
There are some rules: If we do not append a separator, then we do not perform any permutation. Furthermore, we do not accept permutations which have a dangling separator in front of the integer parts or past them. E.g. the permutations [|,1,2,3] and [1,2,3,|] are forbidden. Furthermore, sequences of separators as "|,|" are forbidden.
Now we impose a further restriction on the permutations. Consider the elements between two separators. We call their number "occupation number". We just request that the occupation number of a ordered partition is monotonically decreasing (if we start from the left to the right of a permutation written in our notation). If we interpret a separator as a level, then we can speak of a hierarchy. E.g. we do not count [1,|,2,3,|,4] as a hierarchy, but we accept [1,2|,3,4] as a hierarchy. We thus speak of "hierarchically ordered partitions of partitions" for this sequence.
With the generating function f := z -> 1/(mul(1-z^i/mul(1-z^j,j=1..i), i=1..25)); we get the asymptotic expansion using the command equivalent (f(z),z,n);
The result is 3.788561346*exp(-n)^(-log(2)) + O(1/n*exp(-n)^(-log(2))). Let fas := n -> 3.788562346*exp(-n)^(-log(2)); then for n=60 we get fas(60)/A141199(60)= .4367915009e19/4344507472742893655 = 1.005387846.
In short, a(n) is the number of finite sequences of integer partitions with weakly decreasing lengths and total sum n. The case of twice-partitions is A358831. A version choosing compositions is A218482. The strictly decreasing case is A358836. For ordered set partitions we have A005651. For weakly decreasing bigomega see A358335. - Gus Wiseman, Dec 05 2022
|
|
|
LINKS
|
|
|
|
FORMULA
|
G.f.: 1/Product_{i>=1} (1-x^i/Product_{j=1..i} (1-x^j)). - Vladeta Jovovic, Jul 16 2008
|
|
|
EXAMPLE
|
n=1:
[1]
-------------------------
n=2:
[1, 1],
[1, "|", 1],
[2]]
-------------------------
n=3:
[1, 2],
[1, "|", 1, "|", 1],
[1, 1, 1],
[3],
[2, "|", 1],
[1, 1, "|", 1],
[1, "|", 2]
-------------------------
n=4:
[1, 1, 1, "|", 1],
[1, 1, "|", 1, 1],
[2, 2],
[1, 3],
[1, 1, 1, 1],
[1, 1, 2],
[4],
[1, "|", 1, "|", 1, "|", 1],
[1, 2, "|", 1],
[1, 1, "|", 2],
[1, 1, "|", 1, "|", 1],
[2, "|", 1, "|", 1],
[1, "|", 2, "|", 1],
[1, "|", 1, "|", 2],
[1, "|", 3],
[3, "|", 1],
[2, "|", 2].
|
|
|
MAPLE
|
A Maple program to generate these "hierarchically ordered partitions of partitions" is available on request.
An asymptotic expansion can be found using the generating function given by Vladeta Jovovic. For that purpose we use the Maple program "equivalent" from Bruno Salvy (http://ago.inria.fr/libraries/libraries.html).
|
|
|
PROG
|
(PARI) my(N=40, x='x+O('x^N)); Vec(1/prod(k=1, N, 1-x^k/prod(j=1, k, 1-x^j))) \\ Seiichi Manyama, Jan 18 2022
|
|
|
CROSSREFS
|
Cf. A000041, A000219, A001970, A005651, A063834, A129519, A218482, A358335, A358831, A358836, A358908.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
