A055887 Number of ordered partitions of partitions.

1, 1, 3, 8, 22, 59, 160, 431, 1164, 3140, 8474, 22864, 61697, 166476, 449210, 1212113, 3270684, 8825376, 23813776, 64257396, 173387612, 467856828, 1262431711, 3406456212, 9191739970, 24802339472, 66924874539, 180585336876, 487278670744, 1314838220172

Offset

0,3

Comments

Jordan matrices are upper bidiagonal matrices such that (A) the diagonal entries are in sorted order, (B) there are only 1's and 0's on the superdiagonal, (C) for each superdiagonal 1, the two diagonal entries to the left and below it must be equal. Let J(N) be the number of N X N Jordan matrices where the diagonal values are, without loss of generality, taken to be a prefix of some fixed strictly increasing sequence x_1, x_2, x_3, ... If Jordan blocks sorted by eigenvalue with ties broken by block size during the sorting, then J(1, 2, 3, ...) is this sequence. - Warren D. Smith, Jan 28 2002

Number of compositions of n into parts k >= 1 where there are A000041(k) sorts of part k. - Joerg Arndt, Sep 30 2012

Also number of chains of multisets that partition a normal multiset of weight n, where a multiset is normal if it spans an initial interval of positive integers. - Gus Wiseman, Oct 28 2015

From Gus Wiseman, Jul 31 2022: (Start)

Also the number of ways to choose a multiset partition into constant multisets of a multiset of length n covering an initial interval of positive integers. This interpretation involves only multisets, not sequences. For example, the a(1) = 1 through a(3) = 8 multiset partitions are:

{{1}} {{1,1}} {{1,1,1}}

{{1},{1}} {{1},{1,1}}

{{1},{2}} {{1},{2,2}}

{{2},{1,1}}

{{1},{1},{1}}

{{1},{1},{2}}

{{1},{2},{2}}

{{1},{2},{3}}

Factorizations into prime powers, are counted by A000688.

The strongly normal case is A063834.

The strongly normal strict case is A270995.

Twice-partitions of type PPR are counted by A279784, factorizations A295935.

The strict case is A304969.

(End)

Links

Alois P. Heinz, Table of n, a(n) for n = 0..2320

N. J. A. Sloane, Transforms

N. J. A. Sloane and Thomas Wieder, The Number of Hierarchical Orderings, arXiv:math/0307064 [math.CO], 2003; Order 21 (2004), 83-89, DOI:10.1007/s11083-004-9460-9.

Eric Weisstein's World of Mathematics, q-Pochhammer Symbol.

Formula

Invert transform of partitions numbers A000041.

Let p(k) be the number of integer partitions of k. Furthermore, set a(0)=1. Then a(n) = Sum_{k=1..n} p(k)*a(n-k). - Thomas Wieder, Nov 26 2007

G.f.: 1/( 1 - Sum_{k>=1} p(k)*x^k ) where p(k) = A000041(k) is the number of integer partitions of k. - Joerg Arndt, Sep 30 2012

a(n) ~ c * d^n, where d = 2.698329106474211231263998666188376330713465125913986356769... (see A246828) and c = 0.414113793172792357745578049739573823627306487211379286647... - Vaclav Kotesovec, Mar 29 2014

G.f.: 1/(2 - 1/(x)_inf), where (x)_inf is the q-Pochhammer symbol. - Vladimir Reshetnikov, Sep 22 2016

Example

The a(4) = 22 chains of multisets, where notation x-y means "y is a submultiset of x", are: (o-o-o-o) (oo-o-o) (oo-oo) (ooo-o) (oooo) (oe-o-o) (ooe-o) (oooe) (oe-oe) (ooe-e) (oee-o) (ooee) (oei-o) (ooei) (oe-e-e) (oee-e) (oeee) (oei-e) (oeei) (oei-i) (oeii) (oeis).
From Gus Wiseman, Jul 31 2022: (Start)
a(n) is the number of ways to choose an integer partition of each part of an integer composition of n. The a(0) = 1 through a(3) = 8 choices are:
  ()  ((1))  ((2))     ((3))
             ((11))    ((21))
             ((1)(1))  ((111))
                       ((1)(2))
                       ((2)(1))
                       ((1)(11))
                       ((11)(1))
                       ((1)(1)(1))
(End)

Maple

with(combstruct); SeqSetSetU := [T, {T=Sequence(S), S=Set(U, card >= 1), U=Set(Z, card >=1)}, unlabeled];
P := (x) -> product( 1/(1-x^k), k=1..20 ) - 1; F := (x) -> series( 1/(1-P(x)) - 1, x, 21 ); # F(x) is g.f. for this sequence # Warren D. Smith, Jan 28 2002
A055887rec:= proc(n::integer) local k; option remember; with(combinat): if n = 0 then 1 else add(numbpart(k) *procname(n - k), k=1..n); end if; end proc: seq (A055887rec(n), n=0..10); # Thomas Wieder, Nov 26 2007

Mathematica

a = 1/Product[(1 - x^k), {k, 1, \[Infinity]}] - 1; CoefficientList[Series[1/(1 - a), {x, 0, 20}], x] (* Geoffrey Critzer, Dec 23 2010 *)
(1/(2 - 1/QPochhammer[x]) + O[x]^30)[[3]] (* Vladimir Reshetnikov, Sep 22 2016 *)
Table[Sum[Times@@PartitionsP/@c, {c, Join@@Permutations/@IntegerPartitions[n]}], {n, 0, 10}] (* Gus Wiseman, Jul 31 2022 *)

Prog

(PARI) Vec(1/(2-1/eta(x+O(x^66)))) \\ Joerg Arndt, Sep 30 2012

Crossrefs

Cf. A055888, A083355, A095975, A246828.

Row sums of A060642.

Cf. A326346.

The unordered version is A001970, row-sums of A061260.

A000041 counts integer partitions, strict A000009.

A011782 counts integer compositions.

A072233 counts partitions by sum and length.

Cf. A001055, A050361, A063834, A279784, A355743.

Sequence in context: A291399 A077848 A300662 * A318901 A278612 A331028

Adjacent sequences: A055884 A055885 A055886 * A055888 A055889 A055890

Keyword

nonn

Author

Christian G. Bower, Jun 09 2000

Status

approved