cp's OEIS Frontend

A368548 Number of palindromic partitions of n.

%I A368548 #76 Aug 28 2024 13:41:51
%S A368548 1,2,2,2,4,2,4,4,6,2,10,2,8,10,10,2,18,2,20,16,12,2,36,12,14,24,36,2,
%T A368548 60,2,38,34,18,46,104,2,20,46,108,2,122,2,94,148,24,2,212,58,116,76,
%U A368548 140,2,232,164,270,94,30,2,588,2,32,372,274,280,420,2,276
%N A368548 Number of palindromic partitions of n.
%C A368548 For n>1, a(n) >= 2 as [n] and [1,1,..1] are both palindromic partitions. - _Chai Wah Wu_, Feb 07 2024
%H A368548 Chai Wah Wu, <a href="/A368548/b368548.txt">Table of n, a(n) for n = 1..10000</a>
%H A368548 David J. Hemmer and Karlee J. Westrem, <a href="https://arxiv.org/abs/2402.02250">Palindrome Partitions and the Calkin-Wilf Tree</a>, arXiv:2402.02250 [math.CO], 2024. See Table 3.1 p. 5.
%H A368548 Chai Wah Wu, <a href="/A368548/a368548.pdf">Proofs of formulas for A368548</a>
%H A368548 Chai Wah Wu, <a href="/A368548/a368548_1.pdf">Proofs of formulas for A368548 and A375783</a>
%F A368548 From _Chai Wah Wu_, Feb 08 2024: (Start)
%F A368548 Let x = 0 if n is even and x = Sum_{d|(n+1)/2} binomial(d-2+(n+1)/2d,d-1) if n is odd.
%F A368548 Let y = 2*Sum_{d|n+1, d>=3, and d is odd} binomial((d-5)/2+(n+1)/d,(d-3)/2).
%F A368548 Then a(n) = x+y.
%F A368548 a(n) = 2 if n>1 and n+1 is prime.
%F A368548 a(n) = (n+3)/2 if n>3 is odd and (n+1)/2 is prime.
%F A368548 a(2^n-1) = Sum_{i=0..n-1} binomial(2^i+2^(n-i-1)-2,2^i-1).
%F A368548 (End)
%e A368548 For n=5, the palindromic partitions (as defined in Hemmer and Westrem) are [5], [2, 3], [1, 2, 2], [1, 1, 1, 1, 1]. - _Chai Wah Wu_, Feb 07 2024
%o A368548 (Python)
%o A368548 from itertools import count
%o A368548 from math import comb
%o A368548 from collections import Counter
%o A368548 from sympy.utilities.iterables import partitions
%o A368548 from sympy import isprime
%o A368548 def A368548(n):
%o A368548     if n == 3 or (n>1 and isprime(n+1)): return 2
%o A368548     c = 0
%o A368548     for p in partitions(n):
%o A368548         s, a = '', 1
%o A368548         for d in sorted(Counter(p).elements()):
%o A368548             s += '1'*(d-a)+'0'
%o A368548             a = d
%o A368548         if s[:-1] == s[-2::-1]:
%o A368548             c += 1
%o A368548     return c # _Chai Wah Wu_, Feb 06 2024
%o A368548 (Python)
%o A368548 from math import comb
%o A368548 from sympy import divisors
%o A368548 def A368548(n): # faster program using formula
%o A368548     x = sum(comb(d-2+((n+1)//d>>1),d-1) for d in divisors(n+1>>1,generator=True)) if n&1 else 0
%o A368548     y = sum(comb((d-5>>1)+(n+1)//d,d-3>>1) for d in divisors((n+1)>>(~(n+1)&n).bit_length(),generator=True) if d>=3)<<1
%o A368548     return x+y # _Chai Wah Wu_, Feb 08 2024
%Y A368548 Cf. A068499 (a(n)=2, n>1).
%K A368548 nonn
%O A368548 1,2
%A A368548 _Michel Marcus_, Feb 06 2024
%E A368548 a(41)-a(67) from _Chai Wah Wu_, Feb 06 2024