A391398 - OEIS

%I #26 Mar 13 2026 18:56:36

%S 1,1,3,6,10,21,43,81,161,325,637,1260,2520,4999,9917,19770,39354,

%T 78275,155969,310818,619174,1234199,2460905,4906597,9785125,19518887,

%U 38937907,77686076,155017552,309355889,617411371,1232356841,2459998905,4910949493,9804596413

%N Number of compositions of n where the median of parts equals 1.

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

%C 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.

%H Alois P. Heinz, <a href="/A391398/b391398.txt">Table of n, a(n) for n = 1..3323</a>

%F 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).

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

%e 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.

%p b:= proc(n, c) option remember; `if`(-c>n, 0, `if`(n=0, 1,

%p       add(b(n-j, c+`if`(j=1, 1, -1)), j=1..n)))

%p     end:

%p a:= n-> b(n, 0):

%p seq(a(n), n=1..35);  # _Alois P. Heinz_, Dec 09 2025

%p # Alternative:

%p a:= proc(n) option remember; `if`(n<5, [1$3, 3, 6][n+1],

%p       (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)

%p        -(10*n^2-55*n+53)*a(n-2)+(8*n^2-36*n+23)*a(n-1))/(n*(2*n-7)))

%p     end:

%p seq(a(n), n=1..35);  # _Alois P. Heinz_, Dec 10 2025

%o (Python)

%o from math import comb

%o def a(n):

%o     if n == 0: return 0

%o     total = 1

%o     for k in range(2, n):

%o         for j in range(1, min(k // 2, n - k) + 1):

%o             total += comb(k, j) * comb(n - k - 1, j - 1)

%o     return total

%o print([a(n) for n in range(1, 21)])

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

%Y Cf. A008683.

%K nonn

%O 1,3

%A _Austen M. Fletcher_, Dec 08 2025