A246828 -id:A246828 - cp's OEIS frontend

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

Christian G. Bower, Jun 09 2000

nonn

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)

			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)

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.

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.

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

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

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

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

A131408 Repeated integer partitions or nested integer partitions.

Original entry on oeis.org

1, 1, 2, 5, 14, 35, 95, 248, 668, 1781, 4799, 12890, 34766, 93647, 252635, 681272, 1838135, 4958738, 13379885, 36100214, 97409045, 262833314, 709207394, 1913652308, 5163654671, 13933178390, 37596275726, 101446960109, 273737216768, 738632652929, 1993073801930

Offset: 0

Thomas Wieder, Jul 09 2007

nonn

See A131407 for the labeled case (with much more explanation).

Also the number of sequences of distinct integer partitions (y_1, ..., y_k), containing no partitions of the form (111..1) other than (1), such that sum(y_1) = n and length(y_i) = sum(y_{i+1}) for all i = 1, ..., k-1. - Gus Wiseman, Jul 20 2018

			Let denote * an unlabeled element. Then a(n=3)=5 because we have [ *,*,* ], [ *, * ][ * ], [[ *,* ]][[ * ]], [[ *,* ][ * ]], [ * ][ * ][ * ].
From _Gus Wiseman_, Jul 20 2018: (Start)
The a(4) = 14 sequences of integer partitions:
  (4), (31), (22), (211),
  (4)(1), (31)(2), (22)(2), (211)(3), (211)(21),
  (31)(2)(1), (22)(2)(1), (211)(3)(1), (211)(21)(2),
  (211)(21)(2)(1).
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..2321
Thomas Wieder, Visual Basic Program

Cf. A022811, A022818, A131407, A246828.

A000041 := proc(n) combinat[numbpart](n) ; end: A008284 := proc(n,k) if k = 1 or k = n then 1; elif k > n then 0 ; else procname(n-1,k-1)+procname(n-k,k) ; fi ; end: A131408 := proc(n) option remember; local i ; if n <= 2 then n; else A000041(n)+add(A008284(n,i)*procname(i),i=2..n-1) ; fi ; end: for n from 1 to 40 do printf("%d,",A131408(n)) ; od: # R. J. Mathar, Aug 07 2008
# second Maple program:
b:= proc(n, i) option remember; `if`(n=0 or i=1, 1,
      b(n, i-1) + b(n-i, min(n-i, i)))
    end:
a:= proc(n) option remember; b(n$2)+
      add(b(n-i, min(n-i, i))*a(i), i=2..n-1)
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Sep 03 2020

t[, 1] = 1; t[n, k_] /; 1 <= k <= n := t[n, k] = Sum[t[n-i, k-1], {i, 1, n-1}] - Sum[t[n-i, k], {i, 1, k-1}]; t[, ] = 0; a[1]=1; a[2]=2; a[n_] := a[n] = PartitionsP[n] + Sum[t[n, i]*a[i], {i, 2, n-1}]; Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Feb 02 2017 *)
roo[n_]:=If[n==1,{{{1}}},Join@@Cases[Most[IntegerPartitions[n]],y_:>Prepend[(Prepend[#,y]&/@roo[Length[y]]),{y}]]];
Table[Length[roo[n]],{n,10}] (* Gus Wiseman, Jul 20 2018 *)

a(n) = A000041(n) + Sum_{i=2..n-1} A008284(n,i)*a(i).

a(n) ~ c * d^n, where d = A246828 = 2.69832910647421123126399866618837633..., c = 0.232635324064951140265176690908381464098550827908380222089145... . - Vaclav Kotesovec, Sep 04 2014

Edited and extended by R. J. Mathar, Aug 07 2008

a(0)=1 prepended and edited by Alois P. Heinz, Sep 03 2020

A326346 Total number of partitions in the partitions of compositions of n.

Original entry on oeis.org

0, 1, 4, 14, 47, 151, 474, 1457, 4414, 13210, 39155, 115120, 336183, 976070, 2819785, 8110657, 23239662, 66362960, 188930728, 536407146, 1519205230, 4293061640, 12106883585, 34079016842, 95762829405, 268670620736, 752676269695, 2105751165046, 5883798478398

Offset: 0

Alois P. Heinz, Sep 11 2019

nonn

			a(3) = 14 = 1+1+1+2+2+2+2+3 counts the partitions in 3, 21, 111, 2|1, 11|1, 1|2, 1|11, 1|1|1.

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

Cf. A000041, A030267, A055887, A060642, A304969, A325915, A327548.

b:= proc(n) option remember; `if`(n=0, [1, 0], (p-> p+
      [0, p[1]])(add(combinat[numbpart](j)*b(n-j), j=1..n)))
    end:
a:= n-> b(n)[2]:
seq(a(n), n=0..32);

b[n_] := b[n] = If[n==0, {1, 0}, Function[p, p + {0, p[[1]]}][Sum[ PartitionsP[j] b[n-j], {j, 1, n}]]];
a[n_] := b[n][[2]];
a /@ Range[0, 32] (* Jean-François Alcover, Dec 05 2020, after Alois P. Heinz *)

a(n) = Sum_{k=1..n} k * A060642(n,k).

a(n) ~ c * d^n * n, where d = A246828 = 2.69832910647421123126399866618837633... and c = 0.171490233695958246364725709205670983251448838158816... - Vaclav Kotesovec, Sep 14 2019

A095975 -a(n) is inverse EULER transform of -A000041(n).

Original entry on oeis.org

1, 2, 5, 11, 27, 60, 147, 344, 839, 2031, 5017, 12379, 30921, 77407, 195121, 493451, 1253613, 3194303, 8166757, 20933754, 53798919, 138566312, 357647565, 924834079, 2395702801, 6215748612, 16150985071, 42024182520, 109485000777, 285578913962, 745728542725

Offset: 1

Vladeta Jovovic, Jul 20 2004

Alois P. Heinz, Table of n, a(n) for n = 1..1000
N. J. A. Sloane, Transforms

Cf. A055887, A246828.

with(numtheory): b:= proc(n) option remember; `if`(n=0,1, add(add(d, d=divisors(j)) *b(n-j), j=1..n)/n) end: c:= proc(n) option remember; local j; add(c(j) *b(n-j), j=1..n-1)-n*b(n) end: a:= -proc(n) option remember; local d; `if`(n=0,1, add(mobius(n/d)*c(d), d=divisors(n))/n) end: seq(a(n), n=1..40); # Alois P. Heinz, Sep 09 2008
# The function EulerInvTransform is defined in A358451.
a := -EulerInvTransform(n -> -combinat:-numbpart(n)):
seq(a(n), n = 1..31); # Peter Luschny, Nov 21 2022

b[n_] := b[n] = If[n == 0, 1, Sum[Sum[d, {d, Divisors[j]}]*b[n-j], {j, 1, n}]/n]; c[n_] := c[n] = Sum[c[j]*b[n-j], {j, 1, n-1}] - n*b[n]; a[n_] := -If[n == 0, 1, Sum[MoebiusMu[n/d]*c[d], {d, Divisors[n]}]/n]; Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Feb 24 2015, after Alois P. Heinz *)

Moebius transform of A055890(n).

a(n) ~ d^n / n, d = 2.69832910647421123126399866618837... (see A246828). - Vaclav Kotesovec, Aug 25 2014

More terms from Alois P. Heinz, Sep 09 2008

A141799 Number of repeated integer partitions of n.

Original entry on oeis.org

1, 3, 8, 25, 66, 192, 511, 1418, 3812, 10383, 27958, 75758, 204215, 551821, 1488561, 4018722, 10842422, 29262357, 78955472, 213063551, 574905487, 1551325859, 4185959285, 11295211039, 30478118079, 82240300045, 221911189754, 598790247900, 1615732588962

Offset: 1

Thomas Wieder, Jul 05 2008

nonn

An integer n can be partitioned into P(n) partitions P([n],i) where i=1,...,P(n) counts the partitions. The partition P([n],i) consists of T(n,i) integer parts t(i,j) with j=1,...,T(n,i). Now we perform on each t(i,j) an integer partition again and arrive at new partitions. Their parts can be partitioned again and so forth. We count such repeated partitions of n. One convention is necessary to avoid an infinite loop: The trivial partition P([n],1)=[n] will not be partitioned again but just counted once (and therefore we also have a(1)=1).

			For the integers 1, 2, 3 and 4 we have
[1] -> 1,
thus a(1)=1.
[2] -> 1,
[1,1] => [1] ->, [1] -> 1.
thus a(2)=3.
[3] -> 1,
[1,2] => [1] -> 1, [2] -> 3,
[1,1,1] => [1] -> 1, [1] -> 1, [1] -> 1,
thus a(3)=8.
[4] -> 1,
[1,3] => [1] -> 1, [3] -> 8,
[2,2] => [2] -> 3, [2] -> 3,
[1,1,2] => [1] -> 1, [1] -> 1, [2] -> 3,
[1,1,1,1] => [1] -> 1, [1] -> 1, [1] -> 1, [1] -> 1,
thus a(4)=25.

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Cf. A000041, A131407, A131408, A137732, A246828.

A141799 := proc(n) option remember ; local a,P,i,p ; if n =1 then 1; else a := 0 ; for P in combinat[partition](n) do if nops(P) > 1 then for i in P do a := a+procname(i) ; od: else a := a+1 ; fi; od: RETURN(a) ; fi ; end: for n from 1 to 40 do printf("%d,",A141799(n)) ; od: # R. J. Mathar, Aug 25 2008
# second Maple program
a:= proc(n) option remember;
      1+ `if`(n>1, b(n, n-1)[2], 0)
    end:
b:= proc(n, i) option remember; local f, g;
      if n=0 or i=1 then [1, n]
    else f:= b(n, i-1); g:= `if`(i>n, [0, 0], b(n-i, i));
         [f[1]+g[1], f[2]+g[2] +g[1]*a(i)]
      fi
    end:
seq(a(n), n=1..40); # Alois P. Heinz, Apr 05 2012

a[n_] := a[n] = 1 + If[n>1, b[n, n-1][[2]], 0]; b[n_, i_] := b[n, i] = Module[{f, g}, If[n == 0 || i == 1, {1, n}, f = b[n, i-1]; g = If[i>n, {0, 0}, b[n-i, i]]; {f[[1]] + g[[1]], f[[2]] + g[[2]] + g[[1]]*a[i]}]]; Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Oct 29 2015, after Alois P. Heinz *)

Let sum_{i=1}^P(n) denote the sum over all integer partitions P([n],i) of n. Let sum_{j=1}^T(i,j) denote the sum over all parts of the i-th integer partition. Then we have the recursive formula 1 if t(i,j)=n a(n) = sum_{i=1}^P(n) sum_{j=1}^T(i,j) { a(t(i,j)) else. E.g. a(4)=25 because [4] contributes 1, [1,3] contributes a(1)+a(3)=1+8=9, [2,2] contributes a(2)+a(2)=3+3=6, [1,1,2] contributes a(1)+a(1)+a(2)=1+1+3=5, [1,1,1,1] contributes a(1)+a(1)+a(1)+a(1)=1+1+1+1=4 which gives in total 25.

a(n) ~ c * d^n, where d = 2.69832910647421123126399866... (see A246828), c = 0.5088820425072641934222229579416714164592334575899644931509447692360546... . - Vaclav Kotesovec, Sep 04 2014

Extended by R. J. Mathar, Aug 25 2008

A214948 a(n) is the sum over all proper integer partitions of n of the previous terms.

Original entry on oeis.org

1, 2, 6, 19, 51, 148, 395, 1095, 2945, 8020, 21597, 58518, 157746, 426250, 1149832, 3104236, 8375167, 22603530, 60988687, 164579663, 444082316, 1198312390, 3233419264, 8724918311, 23542640336, 63526028693, 171413973501, 462531951559, 1248062990751, 3367686427976

Offset: 1

Olivier Gérard, Jul 30 2012

By "proper integer partition", one means that the case {n} is excluded for having only one part, equal to the number partitioned.

The growth of this function is exponential a(n) -> c * exp(n). [This is not correct, a(n) ~ c * d^n, where d = A246828 = 2.69832910647421123126399... and c = 0.39308289517441096263558422597609193642795355676880812197435683468376... - Vaclav Kotesovec, Dec 27 2023]

			a(4) = (a(3)+a(1))+(a(2)+a(2))+(a(2)+a(1)+a(1))+(a(1)+a(1)+a(1)+a(1)) = (6 +  1) + (2 + 2) + (2 + 2*1) + (4*1) = 7 + 4 + 4 + 4 = 19.

Alois P. Heinz, Table of n, a(n) for n = 1..2320 (first 70 terms from Vincenzo Librandi)

Cf. A000041, A246828.

b:= proc(n, i) option remember; `if`(n<2, [1, n], `if`(i<1, 0,
      b(n, i-1)+(p-> p+[0, p[1]*a(i)])(b(n-i, min(n-i, i)))))
    end:
a:= n-> b(n, n-1)[2]:
seq(a(n), n=1..33);  # Alois P. Heinz, Dec 27 2023

Clear[a]; a[1] := 1; a[n_Integer] :=
a[n] = Plus @@ Map[Function[p, Plus @@ Map[a, p]], Drop[IntegerPartitions[n], 1]]; Table[ a[n], {n,1,30}]

a(n) = sum( sum( a(i), i in p) , p in P*(n)) where P*(n) is the set of all integer partitions of n excluding {n}, p is a partition of P*(n), i is a part of p.

a(n) ~ exp(k) * a(n-1), k = 0.992632731... (conjecture). - Bill McEachen, Dec 26 2023

cp's OEIS Frontend

A055887 Number of ordered partitions of partitions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A131408 Repeated integer partitions or nested integer partitions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A326346 Total number of partitions in the partitions of compositions of n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A095975 -a(n) is inverse EULER transform of -A000041(n).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A141799 Number of repeated integer partitions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A214948 a(n) is the sum over all proper integer partitions of n of the previous terms.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula