A380108 Number of distinct partitions of length n binary strings into maximal constant substrings up to permutation.

1, 2, 3, 6, 10, 18, 29, 48, 75, 118, 179, 272, 403, 596, 865, 1252, 1786, 2538, 3566, 4990, 6918, 9552, 13086, 17856, 24205, 32684, 43881, 58698, 78125, 103618, 136820, 180064, 236031, 308432, 401585, 521340, 674579, 870446, 1119786, 1436798, 1838405, 2346480, 2987204

Offset: 0

Author

Yaroslav Deryavko, Jan 12 2025

Keywords

• nonn

Comments

Equivalently, a(n) is the number of partitions of n into parts of two kinds where the number of parts of each kind differ by at most one.

Examples

			For n = 3, the partitions are (000), (111), (00, 1), (0, 11), (0, 0, 1), (0, 1, 1).
		

Links

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

Crossrefs

Cf. A000712, A114921, A342528.

Programs

Maple

g:= (n, i, t)-> `if`(t>1+n, 0, `if`(n=0, 1, b(n, i, t))):
b:= proc(n, i, t) option remember; add(add(g(n-i*j,
      min(n-i*j, i-1), abs(t+2*h-j)), h=0..j), j=`if`(i=1, n, 0..n/i))
    end:
a:= n-> g(n$2, 0):
seq(a(n), n=0..42);  # Alois P. Heinz, Jan 15 2025

Mathematica

g[n_, i_, t_] := If[t > 1+n, 0, If[n == 0, 1, b[n, i, t]]];
b[n_, i_, t_] := b[n, i, t] = Sum[Sum[g[n-i*j,
   Min[n-i*j, i-1], Abs[t+2*h-j]], {h, 0, j}], {j, If[i == 1, n, 0], n/i}];
a[n_] := g[n, n, 0];
Table[a[n], {n, 0, 42}] (* Jean-François Alcover, Feb 02 2025, after Alois P. Heinz *)

PARI

seq(n)={my(p=1/prod(k=1, n, 1-y*x^k + O(x*x^n))); Vec(sum(k=0, n\2, polcoef(p, k, y)*(2*polcoef(p, k+1, y) + polcoef(p, k, y))))} \\ Andrew Howroyd, Jan 12 2025

Python

n = 0
while True:
    m = set()
    for i in range(2**n):
        t = bin(i)[2:]
        t = '0' * (n - len(t)) + t + '2'
        l = []
        s = 0
        for j in range(1, n + 1):
            if t[j] != t[j - 1]:
                l.append(t[s:j])
                s = j
        l.sort()
        l = tuple(l)
        m.add(l)
    print(len(m), end=' ')
    n += 1

Formula

G.f.: Sum_{k>=0} ([y^k] P(x,y))*([y^k] (1 + 2*y)*P(x,y)), where P(x,y) = Product_{k>=1} 1/(1 - y*x^k). - Andrew Howroyd, Jan 12 2025