A391398 Number of compositions of n where the median of parts equals 1.

1, 1, 3, 6, 10, 21, 43, 81, 161, 325, 637, 1260, 2520, 4999, 9917, 19770, 39354, 78275, 155969, 310818, 619174, 1234199, 2460905, 4906597, 9785125, 19518887, 38937907, 77686076, 155017552, 309355889, 617411371, 1232356841, 2459998905, 4910949493, 9804596413

Offset

1,3

Comments

For even-length compositions, the median is defined as the lower-middle element of the sorted parts.

Equivalently, compositions where at least half the parts equal the smallest part, all parts are multiples of the smallest part, and the smallest part is 1.

Links

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

Formula

a(n) = 1 + Sum_{k=2..n-1} Sum_{j=1..min(floor(k/2), n-k)} binomial(k,j) * binomial(n-k-1, j-1).

a(n) = Sum_{d|n} mu(d) * A388070(n/d), where mu is the Möbius function (Möbius transform of A388070).

Example

a(5) = 10 because the compositions of 5 with gcd = median = 1 are: [1,1,1,1,1], [1,1,1,2], [1,1,2,1], [1,2,1,1], [2,1,1,1], [1,1,3], [1,3,1], [3,1,1], [1,4], [4,1]. The composition [5] is excluded because gcd = median = 5, not 1.

Maple

b:= proc(n, c) option remember; `if`(-c>n, 0, `if`(n=0, 1,
      add(b(n-j, c+`if`(j=1, 1, -1)), j=1..n)))
    end:
a:= n-> b(n, 0):
seq(a(n), n=1..35);  # Alois P. Heinz, Dec 09 2025
# Alternative:
a:= proc(n) option remember; `if`(n<5, [1$3, 3, 6][n+1],
      (8*(n-5)*(2*n-5)*a(n-5)-4*(6*n^2-37*n+49)*a(n-4)+2*(6*n^2-33*n+31)*a(n-3)
       -(10*n^2-55*n+53)*a(n-2)+(8*n^2-36*n+23)*a(n-1))/(n*(2*n-7)))
    end:
seq(a(n), n=1..35);  # Alois P. Heinz, Dec 10 2025

Prog

(Python)
from math import comb
def a(n):
    if n == 0: return 0
    total = 1
    for k in range(2, n):
        for j in range(1, min(k // 2, n - k) + 1):
            total += comb(k, j) * comb(n - k - 1, j - 1)
    return total
print([a(n) for n in range(1, 21)])

Crossrefs

Cf. A388070 (compositions where gcd = median), A011782 (total number of compositions).

Cf. A008683.

Sequence in context: A027671 A167617 A274018 * A068149 A068709 A068804

Adjacent sequences: A391395 A391396 A391397 * A391399 A391400 A391401

Keyword

nonn

Author

Austen M. Fletcher, Dec 08 2025

Status

approved