A327643 -id:A327643 - cp's OEIS frontend

A002846 Number of ways of transforming a set of n indistinguishable objects into n singletons via a sequence of n-1 refinements.

1, 1, 1, 2, 4, 11, 33, 116, 435, 1832, 8167, 39700, 201785, 1099449, 6237505, 37406458, 232176847, 1513796040, 10162373172, 71158660160, 511957012509, 3819416719742, 29195604706757, 230713267586731, 1861978821637735, 15484368121967620, 131388840051760458

Offset: 1

N. J. A. Sloane. Entry revised by N. J. A. Sloane, Jun 11 2012

Construct the ranked poset L(n) whose nodes are the A000041(n) partitions of n, with all the partitions into the same number of parts having the same rank. A partition into k parts is joined to a partition into k+1 parts if the latter is a refinement of the former.
The partition n^1 is at the left and the partition 1^n at the right. The illustration by Olivier Gérard shows the posets L(2) through L(8).
Then a(n) is the number of paths of length n-1 in L(n) that join n^1 to 1^n.
Stated another way, a(n) is the number of maximal chains in the ranked poset L(n). (This poset is not a lattice for n > 4.) - Comments corrected by Gus Wiseman, May 01 2016

			a(5) = 4 because there are 4 paths from top to bottom in this lattice:
  .
       ooooo
     /      \
  o.oooo   oo.ooo
    |    X    |
  o.o.ooo  o.oo.oo
     \       /
      o.o.o.oo
          |
      o.o.o.o.o
  .
(This is the ranked poset L(5), but drawn vertically rather than horizontally.)

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..80
P. Erdős, R. K. Guy and J. W. Moon, On refining partitions, J. London Math. Soc., 9 (1975), 565-570.
R. K. Guy, Letter to N. J. A. Sloane, June 24 1971: front, back [Annotated scanned copy, with permission]
Olivier Gérard, The ranked posets L(2),...,L(8)
Gus Wiseman, Hasse Diagrams of Partition Refinement Posets n=1..9
Gus Wiseman, Hasse Diagrams of Partition Refinement Posets n=1..9, Version 1, [Cached copy, with permission]
Gus Wiseman, Hasse Diagrams of Partition Refinement Posets n=1..9, Version 2, [Cached copy, with permission]

See A213242, A213385, A213427 for related sequences, A327643.

v:= l-> [seq(`if`(i=1 or l[i]>l[i-1], seq(subs(1=[][], sort(subsop(
         i=[j, l[i]-j][], l))), j=1..l[i]/2), [][]), i=1..nops(l))]:
b:= proc(l) option remember; `if`(max(l)<2, 1, add(b(h), h=v(l))) end:
a:= n-> b([n]):
seq(a(n), n=1..30);  # Alois P. Heinz, Sep 22 2019

Mathematica
```
<Mitch Harris, Jan 19 2006 *)
```

def A002846(n): return Posets.IntegerPartitions(n).chain_polynomial().leading_coefficient()  # Max Alekseyev, Dec 23 2015

a(17)-a(25) from Mitch Harris, Jan 19 2006

A327631 Number T(n,k) of parts in all proper k-times partitions of n; triangle T(n,k), n >= 1, 0 <= k <= n-1, read by rows.

Original entry on oeis.org

1, 1, 2, 1, 5, 3, 1, 11, 21, 12, 1, 19, 61, 74, 30, 1, 34, 205, 461, 432, 144, 1, 53, 474, 1652, 2671, 2030, 588, 1, 85, 1246, 6795, 17487, 23133, 15262, 3984, 1, 127, 2723, 20966, 76264, 148134, 158452, 88194, 19980, 1, 191, 6277, 69812, 360114, 1002835, 1606434, 1483181, 734272, 151080

Offset: 1

Alois P. Heinz, Sep 19 2019

In each step at least one part is replaced by the partition of itself into smaller parts. The parts are not resorted.
T(n,k) is defined for all n>=0 and k>=0.  The triangle displays only positive terms.  All other terms are zero.
Row n is the inverse binomial transform of the n-th row of array A327618.

			T(4,0) = 1:
  4    (1 part).
T(4,1) = 11 = 2 + 2 + 3 + 4:
  4-> 31    (2 parts)
  4-> 22    (2 parts)
  4-> 211   (3 parts)
  4-> 1111  (4 parts)
T(4,2) = 21 = 3 + 4 + 3 + 3 + 4 + 4:
  4-> 31 -> 211   (3 parts)
  4-> 31 -> 1111  (4 parts)
  4-> 22 -> 112   (3 parts)
  4-> 22 -> 211   (3 parts)
  4-> 22 -> 1111  (4 parts)
  4-> 211-> 1111  (4 parts)
T(4,3) = 12 = 4 + 4 + 4:
  4-> 31 -> 211 -> 1111  (4 parts)
  4-> 22 -> 112 -> 1111  (4 parts)
  4-> 22 -> 211 -> 1111  (4 parts)
Triangle T(n,k) begins:
  1;
  1,   2;
  1,   5,    3;
  1,  11,   21,    12;
  1,  19,   61,    74,    30;
  1,  34,  205,   461,   432,    144;
  1,  53,  474,  1652,  2671,   2030,    588;
  1,  85, 1246,  6795, 17487,  23133,  15262,  3984;
  1, 127, 2723, 20966, 76264, 148134, 158452, 88194, 19980;
  ...

Alois P. Heinz, Rows n = 1..200, flattened
Wikipedia, Partition (number theory)

Columns k=0-2 give: A057427, -1+A006128(n), A328042.
Row sums give A327648.
T(n,floor(n/2)) gives A328041.
Cf. A327618, A327632, A327639, A327643.

b:= proc(n, i, k) option remember; `if`(n=0, [1, 0],
     `if`(k=0, [1, 1], `if`(i<2, 0, b(n, i-1, k))+
         (h-> (f-> f +[0, f[1]*h[2]/h[1]])(h[1]*
        b(n-i, min(n-i, i), k)))(b(i$2, k-1))))
    end:
T:= (n, k)-> add(b(n$2, i)[2]*(-1)^(k-i)*binomial(k, i), i=0..k):
seq(seq(T(n, k), k=0..n-1), n=1..12);

b[n_, i_, k_] := b[n, i, k] = If[n == 0, {1, 0}, If[k == 0, {1, 1}, If[i < 2, 0, b[n, i - 1, k]] + Function[h, Function[f, f + {0, f[[1]]*h[[2]]/ h[[1]]}][h[[1]]*b[n - i, Min[n - i, i], k]]][b[i, i, k - 1]]]];
T[n_, k_] := Sum[b[n, n, i][[2]]*(-1)^(k - i)*Binomial[k, i], {i, 0, k}];
Table[T[n, k], {n, 1, 12}, {k, 0, n - 1}] // Flatten (* Jean-François Alcover, Jan 07 2020, after Alois P. Heinz *)

T(n,k) = Sum_{i=0..k} (-1)^(k-i) * binomial(k,i) * A327618(n,i).

T(n,n-1) = n * A327639(n,n-1) = n * A327643(n) for n >= 1.

A327639 Number T(n,k) of proper k-times partitions of n; triangle T(n,k), n >= 0, 0 <= k <= max(0,n-1), read by rows.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 4, 6, 3, 1, 6, 15, 16, 6, 1, 10, 45, 88, 76, 24, 1, 14, 93, 282, 420, 302, 84, 1, 21, 223, 1052, 2489, 3112, 1970, 498, 1, 29, 444, 2950, 9865, 18123, 18618, 10046, 2220, 1, 41, 944, 9030, 42787, 112669, 173338, 155160, 74938, 15108

Offset: 0

Alois P. Heinz, Sep 20 2019

In each step at least one part is replaced by the partition of itself into smaller parts. The parts are not resorted.
T(n,k) is defined for all n>=0 and k>=0.  The triangle displays only positive terms.  All other terms are zero.
Row n is the inverse binomial transform of the n-th row of array A323718.

			T(4,0) = 1:  4
T(4,1) = 4:     T(4,2) = 6:          T(4,3) = 3:
  4-> 31          4-> 31 -> 211        4-> 31 -> 211 -> 1111
  4-> 22          4-> 31 -> 1111       4-> 22 -> 112 -> 1111
  4-> 211         4-> 22 -> 112        4-> 22 -> 211 -> 1111
  4-> 1111        4-> 22 -> 211
                  4-> 22 -> 1111
                  4-> 211-> 1111
Triangle T(n,k) begins:
  1;
  1;
  1,  1;
  1,  2,   1;
  1,  4,   6,    3;
  1,  6,  15,   16,     6;
  1, 10,  45,   88,    76,     24;
  1, 14,  93,  282,   420,    302,     84;
  1, 21, 223, 1052,  2489,   3112,   1970,    498;
  1, 29, 444, 2950,  9865,  18123,  18618,  10046,  2220;
  1, 41, 944, 9030, 42787, 112669, 173338, 155160, 74938, 15108;
  ...

Alois P. Heinz, Rows n = 0..170, flattened
Wikipedia, Iverson bracket
Wikipedia, Partition (number theory)

Columns k=0-2 give A000012, A000065, A327769.
Row sums give A327644.
T(2n,n) gives A327645.
Cf. A323718, A327631, A327643, A327646.

b:= proc(n, i, k) option remember; `if`(n=0 or k=0, 1, `if`(i>1,
      b(n, i-1, k), 0) +b(i$2, k-1)*b(n-i, min(n-i, i), k))
    end:
T:= (n, k)-> add(b(n$2, i)*(-1)^(k-i)*binomial(k, i), i=0..k):
seq(seq(T(n, k), k=0..max(0, n-1)), n=0..12);

b[n_, i_, k_] := b[n, i, k] = If[n == 0 || k == 0, 1, If[i > 1, b[n, i - 1, k], 0] + b[i, i, k - 1] b[n - i, Min[n - i, i], k]];
T[n_, k_] := Sum[b[n, n, i] (-1)^(k - i) Binomial[k, i], {i, 0, k}];
Table[T[n, k], {n, 0, 12}, {k, 0, Max[0, n - 1] }] // Flatten (* Jean-François Alcover, Dec 09 2020, after Alois P. Heinz *)

T(n,k) = Sum_{i=0..k} (-1)^(k-i) * binomial(k,i) * A323718(n,i).
T(n,n-1) = A327631(n,n-1)/n = A327643(n) for n >= 1.
Sum_{k=1..n-1} k * T(n,k) = A327646(n).
Sum_{k=0..max(0,n-1)} (-1)^k * T(n,k) = [n<2], where [] is an Iverson bracket.

A327702 Number of refinement sequences n -> ... -> {1}^n, where in each step one part that is the rightmost copy of its size is replaced by a partition of itself into smaller parts (in weakly decreasing order).

Original entry on oeis.org

1, 1, 2, 5, 14, 47, 174, 730, 3300, 16361, 85991, 485982, 2877194, 18064663, 118111993, 810388956, 5755059363, 42643884970, 325468477721, 2576976440845, 20960795772211, 176056148076418, 1514733658531058, 13418942409623726, 121442280888373117, 1128425823360525506

Offset: 1

Alois P. Heinz, Sep 22 2019

nonn

			a(4) = 5:
  4 -> 1111
  4 -> 211  -> 1111
  4 -> 31   -> 1111
  4 -> 31   -> 211  -> 1111
  4 -> 22   -> 211  -> 1111

Alois P. Heinz, Table of n, a(n) for n = 1..58
Wikipedia, Partition (number theory)

Cf. A002846, A327643, A327697, A327698, A327699.

v:= l-> [seq(`if`(i=1 or l[i]>l[i-1], seq(subs(1=[][], sort(
         subsop(i=h[], l))), h=({combinat[partition](l[i])[]}
         minus{[l[i]]})), [][]), i=1..nops(l))]:
b:= proc(l) option remember; `if`(max(l)<2, 1, add(b(h), h=v(l))) end:
a:= n-> b([n]):
seq(a(n), n=1..26);

A327697 Number of refinement sequences n -> ... -> {1}^n, where in each step every single part of a nonempty selection of parts is replaced by a partition of itself into smaller parts (in weakly decreasing order).

Original entry on oeis.org

1, 1, 2, 7, 22, 122, 598, 4683, 31148, 292008, 2560274, 30122014, 313694962, 4189079688, 53048837390, 826150653479, 11827659365138, 204993767192252, 3371451881544534, 65337695492942258, 1198123466804343518, 25318312971995895392, 516420623159289735874

Offset: 1

Alois P. Heinz, Sep 22 2019

nonn

			a(1) = 1:
  1
a(2) = 1:
  2 -> 11
a(3) = 2:
  3 -> 111
  3 -> 21   -> 111
a(4) = 7:
  4 -> 1111
  4 -> 211  -> 1111
  4 -> 31   -> 1111
  4 -> 31   -> 211  -> 1111
  4 -> 22   -> 1111
  4 -> 22   -> 112  -> 1111
  4 -> 22   -> 211  -> 1111

Wikipedia, Partition (number theory)

Cf. A002846, A327643, A327698, A327699, A327702.

A327698 Number of refinement sequences n -> ... -> {1}^n, where in each step exactly one part is replaced by a partition of itself into smaller parts (in weakly decreasing order).

Original entry on oeis.org

1, 1, 2, 6, 17, 74, 300, 1755, 9360, 65510, 442117, 3802889, 30213386, 294892947, 2789021105, 31360525517, 334374848070, 4184958056248, 50606351991305, 704124800141153, 9452367941048830, 143309007303310536, 2124982437997726705, 35389562541842450218

Offset: 1

Alois P. Heinz, Sep 22 2019

nonn

			a(4) = 6:
  4 -> 1111
  4 -> 211  -> 1111
  4 -> 31   -> 1111
  4 -> 31   -> 211  -> 1111
  4 -> 22   -> 112  -> 1111
  4 -> 22   -> 211  -> 1111

Wikipedia, Partition (number theory)

Cf. A002846, A327643, A327697, A327699, A327702.

A327699 Number of refinement sequences n -> ... -> {1}^n, where in each step every single part of a nonempty selection of parts is replaced by a partition of itself into two smaller parts (in weakly decreasing order).

Original entry on oeis.org

1, 1, 1, 4, 9, 48, 211, 1736, 9777, 91169, 739174, 8613817, 83763730, 1105436491, 13222076337, 207852246589, 2789691577561, 47759515531854, 755158220565169, 14595210284816038, 255814560447492788, 5373613110108953192, 105867623217924984398, 2460702471446564481641

Offset: 1

Alois P. Heinz, Sep 22 2019

nonn

			a(4) = 4:
  4 -> 31   -> 211  -> 1111
  4 -> 22   -> 1111
  4 -> 22   -> 112  -> 1111
  4 -> 22   -> 211  -> 1111

Wikipedia, Partition (number theory)

Cf. A002846, A327643, A327697, A327698, A327702.

A327729 a(n) = Sum_{p} M(n-k; p_1-1, ..., p_k-1) * Product_{j=1..k} a(p_j), where p = (p_1, ..., p_k) ranges over all partitions of n into smaller parts (k is a partition length and M is a multinomial).

Original entry on oeis.org

1, 1, 2, 6, 18, 90, 414, 2892, 18342, 155124, 1265130, 13413240, 129656286, 1564538796, 18285385518, 255345207156, 3378398348214, 52931303772912, 797460543143154, 13926097774972152, 234050020177159926, 4466082284967035124, 83159771376289666806

Offset: 1

Alois P. Heinz, Sep 23 2019

nonn

The formula is a generalization of the formula given in A327643.

Alois P. Heinz, Table of n, a(n) for n = 1..460
Wikipedia, Multinomial coefficients
Wikipedia, Partition (number theory)

Cf. A327643, A327711.

with(combinat):
a:= proc(n) option remember; `if`(n<2, 1, add(mul(a(i), i=p)
      *multinomial(n-nops(p), map(x-> x-1, p)[]),
       p=select(x-> nops(x)>1, partition(n))))
    end:
seq(a(n), n=1..24);
# second Maple program:
b:= proc(n, p, i) option remember; `if`(n=0, p!, `if`(i<1, 0,
      b(n, p, i-1) +a(i)*b(n-i, p-1, min(n-i, i))/(i-1)!))
    end:
a:= n-> `if`(n<2, 1, b(n$2, n-1)):
seq(a(n), n=1..24);

b[n_, p_, i_] := b[n, p, i] = If[n == 0, p!, If[i < 1, 0, b[n, p, i - 1] + a[i] b[n - i, p - 1, Min[n - i, i]]/(i - 1)!]];
a[n_] := If[n < 2, 1, b[n, n, n - 1]];
Array[a, 24] (* Jean-François Alcover, May 03 2020, after 2nd Maple program *)

cp's OEIS Frontend

A002846 Number of ways of transforming a set of n indistinguishable objects into n singletons via a sequence of n-1 refinements.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Extensions

A327631 Number T(n,k) of parts in all proper k-times partitions of n; triangle T(n,k), n >= 1, 0 <= k <= n-1, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A327639 Number T(n,k) of proper k-times partitions of n; triangle T(n,k), n >= 0, 0 <= k <= max(0,n-1), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A327702 Number of refinement sequences n -> ... -> {1}^n, where in each step one part that is the rightmost copy of its size is replaced by a partition of itself into smaller parts (in weakly decreasing order).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

A327697 Number of refinement sequences n -> ... -> {1}^n, where in each step every single part of a nonempty selection of parts is replaced by a partition of itself into smaller parts (in weakly decreasing order).

Views

Author

Keywords

Examples

Links

Crossrefs

A327698 Number of refinement sequences n -> ... -> {1}^n, where in each step exactly one part is replaced by a partition of itself into smaller parts (in weakly decreasing order).

Views

Author

Keywords

Examples

Links

Crossrefs

A327699 Number of refinement sequences n -> ... -> {1}^n, where in each step every single part of a nonempty selection of parts is replaced by a partition of itself into two smaller parts (in weakly decreasing order).

Views

Author

Keywords

Examples

Links

Crossrefs

A327729 a(n) = Sum_{p} M(n-k; p_1-1, ..., p_k-1) * Product_{j=1..k} a(p_j), where p = (p_1, ..., p_k) ranges over all partitions of n into smaller parts (k is a partition length and M is a multinomial).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica