A395377 Number of ordered set partitions of {1..n} having pairwise distinct block sums.

1, 1, 3, 11, 61, 415, 3345, 31427, 340675, 4116811, 55720683, 824183715, 13373853905, 233866939405, 4428702535059, 89350926814601, 1933003918341879, 44230054234727113, 1075973388687731679, 27522458243665907779, 743933733844855291351, 21031776710122509531877

Offset

0,3

Comments

An ordered set partition of {1..n} is a sequence (B_1,...,B_k) of nonempty disjoint subsets whose union is {1..n}. If s(B) = Sum_{x in B} x, then a(n) counts those partitions for which the values s(B_i) are pairwise distinct.

Equivalently, this counts ordered set partitions for which the map B -> s(B) is injective.

This is a refinement of the Fubini numbers A000670 obtained by imposing an additive distinctness constraint on block sums. Let T(n,k) be the number of set partitions of {1..n} into k blocks with pairwise distinct block sums; then a(n) = Sum_{k=0..n} k!*T(n,k). This can be viewed as counting ordered set partitions avoiding collisions among block sums.

Links

Table of n, a(n) for n=0..21.

Formula

a(n) = Sum_{k=0..n} k! * A395416(n,k), where A395416(n,k) is the number of set partitions of {1..n} into k blocks with pairwise distinct block sums.

Example

For n = 3, there are 13 ordered set partitions; the only ones with equal block sums are 12|3 and 3|12, hence a(3) = 11.
For n = 4, T(4,1)=1, T(4,2)=6, T(4,3)=4, T(4,4)=1, hence a(4) = 1!*1 + 2!*6 + 3!*4 + 4!*1 = 61.

Prog

(Python)
from functools import lru_cache
def a(n):
    subsum = [0] * (1 << n)
    for mask in range(1, 1 << n):
        b = mask & -mask
        subsum[mask] = subsum[mask ^ b] + b.bit_length()
    @lru_cache(None)
    def F(mask, used):
        if mask == 0:
            return 1
        total = 0
        sub = mask
        while sub:
            s = subsum[sub]
            if s not in used:
                total += F(mask ^ sub, used + (s, ))
            sub = (sub - 1) & mask
        return total
    return F((1 << n) - 1, ())

Crossrefs

Cf. A000670, A275780, A395416.

Sequence in context: A228204 A095237 A185385 * A024528 A368880 A386265

Adjacent sequences: A395374 A395375 A395376 * A395378 A395379 A395380

Keyword

nonn

Author

Pablo Cadena-Urzúa, Apr 20 2026

Extensions

a(16) from Alois P. Heinz, Apr 21 2026

a(17)-a(21) from Christian Sievers, Apr 26 2026

Status

approved