A141199 Number of hierarchical ordered partitions of partitions.

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

Offset: 0

Author

Thomas Wieder, Jun 13 2008, Jun 29 2008, Jul 28 2008

Keywords

• nonn

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

Examples

			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].
		

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..1000
• Thomas Wieder, The number of certain rankings and hierarchies formed from labeled or unlabeled elements and sets, Applied Mathematical Sciences, vol. 3, 2009, no. 55, 2707 - 2724. [_Thomas Wieder_, Nov 14 2009]

Crossrefs

Cf. A055887, A083355, A140585.

Cf. A000041, A000219, A001970, A005651, A063834, A129519, A218482, A358335, A358831, A358836, A358908.

Programs

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).

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

Formula

G.f.: 1/Product_{i>=1} (1-x^i/Product_{j=1..i} (1-x^j)). - Vladeta Jovovic, Jul 16 2008

Extensions

More terms from Vladeta Jovovic, Jul 16 2008

a(0)=1 prepended by Seiichi Manyama, Jan 18 2022