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

1, 1, 1, 3, 6, 24, 84, 498, 2220, 15108, 92328, 773580, 5636460, 53563476, 471562512, 5270698716, 52117937052, 637276396764, 7317811499736, 100453675122444, 1276319138168796, 19048874583061716, 270233458572751440, 4442429353548965628, 68384217440167826412

Offset

1,4

Comments

Number of proper (n-1)-times partitions of n, cf. A327639.

Might be called "Half-Factorial numbers" analog to the "Half-Catalan numbers" (A000992).

The recursion formula is a special case of the formula given in A327729.

a(n+1)/(n*a(n)) tends to 0.67617164... - Vaclav Kotesovec, Apr 28 2020

Links

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

Vaclav Kotesovec, Plot of a(n+1)/(n*a(n)) for n = 1..10000

Wikipedia, Partition (number theory)

Formula

a(n) = Sum_{j=1..floor(n/2)} C(n-2,j-1) a(j)*a(n-j) for n > 1, a(1) = 1.

a(n) = A327639(n,n-1) = A327631(n,n-1)/n.

Example

a(1) = 1:
  1
a(2) = 1:
  2 -> 11
a(3) = 1:
  3 -> 21 -> 111
a(4) = 3:
  4 -> 31 -> 211 -> 1111
  4 -> 22 -> 112 -> 1111
  4 -> 22 -> 211 -> 1111
a(5) = 6:
  5 -> 41 -> 311 -> 2111 -> 11111
  5 -> 41 -> 221 -> 1121 -> 11111
  5 -> 41 -> 221 -> 2111 -> 11111
  5 -> 32 -> 212 -> 1112 -> 11111
  5 -> 32 -> 212 -> 2111 -> 11111
  5 -> 32 -> 311 -> 2111 -> 11111

Maple

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:
a:= n-> add(b(n$2, i)*(-1)^(n-1-i)*binomial(n-1, i), i=0..n-1):
seq(a(n), n=1..29);
# second Maple program:
a:= proc(n) option remember; `if`(n=1, 1,
      add(a(j)*a(n-j)*binomial(n-2, j-1), j=1..n/2))
    end:
seq(a(n), n=1..29);

Mathematica

a[n_] := a[n] = Sum[Binomial[n-2, j-1] a[j] a[n-j], {j, n/2}]; a[1] = 1;
Array[a, 25] (* Jean-François Alcover, Apr 28 2020 *)

Crossrefs

Cf. A000142, A000992, A002846 (only one part of each size is replaceable), A327631, A327639, A327697, A327698, A327699, A327702, A327729.

Sequence in context: A132390 A080373 A363016 * A296215 A152761 A295761

Adjacent sequences: A327640 A327641 A327642 * A327644 A327645 A327646

Keyword

nonn

Author

Alois P. Heinz, Sep 20 2019

Status

approved