A309897 Number of not unique partition coefficients of n.

0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 6, 9, 13, 22, 33, 51, 74, 104, 142, 194, 261, 351, 464, 616, 802, 1047, 1344, 1716, 2186, 2766, 3473, 4367, 5448, 6774, 8375, 10329, 12685, 15553, 18982, 23098, 28046, 33966, 40976, 49381, 59301, 71095, 85017, 101491, 120859

Offset: 0

Author

Peter Luschny, Sep 06 2019

Keywords

• nonn

Comments

We call (p1+p2+ ...)! / (p1!*p2!*p3! ...) a 'partition coefficient' of n if (p1, p2, p3, ...) is a partition, n = p1 + p2 + ... and denote it by P(n, p).

Examples

			a(7) = 1 because the partition coefficients of 7 are [1, 7, 21, 42, 35, 105, 210, 140, 210, 420, 840, 630, 1260, 2520, 5040], P(7, [3, 2, 2]) = P(7, [4, 1, 1, 1]) = 210 and all other partition coefficients are unique.
We say that two partitions of n are multinomial-equivalent if they have the same partition coefficient. For instance [6, 2, 2, 1, 1] ~ [5, 4, 1, 1, 1] ~ [5, 3, 2, 2] and [6, 4, 1, 1, 1, 1, 1] ~ [6, 3, 2, 2, 1, 1] ~ [5, 4, 3, 1, 1, 1] ~ [5, 3, 3, 2, 2].
		

Crossrefs

Cf. A000041, A070289.

Programs

Maple

h := proc(n,k) option remember;
if n = 0 then return [1] elif k < 1 then return [] fi;
[h(n, k-1)[], seq(map(x -> x*k!^j, h(n-k*j, k-1))[], j=1..n/k)] end:
A309897 := proc(n) h(n, n); nops(%) - nops(convert(%, set)) end:
seq(A309897(n), n=0..48);

SageMath

def A309897(n):
    P = Partitions(n)
    M = set(multinomial(x) for x in P)
    return P.cardinality() - len(M)
[A309897(n) for n in range(29)]

Formula

a(n) = A000041(n) - A070289(n).