OFFSET
1,2
COMMENTS
For n>1, a(n) >= 2 as [n] and [1,1,..1] are both palindromic partitions. - Chai Wah Wu, Feb 07 2024
LINKS
Chai Wah Wu, Table of n, a(n) for n = 1..10000
David J. Hemmer and Karlee J. Westrem, Palindrome Partitions and the Calkin-Wilf Tree, arXiv:2402.02250 [math.CO], 2024. See Table 3.1 p. 5.
Chai Wah Wu, Proofs of formulas for A368548
Chai Wah Wu, Proofs of formulas for A368548 and A375783
FORMULA
From Chai Wah Wu, Feb 08 2024: (Start)
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.
Let y = 2*Sum_{d|n+1, d>=3, and d is odd} binomial((d-5)/2+(n+1)/d,(d-3)/2).
Then a(n) = x+y.
a(n) = 2 if n>1 and n+1 is prime.
a(n) = (n+3)/2 if n>3 is odd and (n+1)/2 is prime.
a(2^n-1) = Sum_{i=0..n-1} binomial(2^i+2^(n-i-1)-2,2^i-1).
(End)
EXAMPLE
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
PROG
(Python)
from itertools import count
from math import comb
from collections import Counter
from sympy.utilities.iterables import partitions
from sympy import isprime
def A368548(n):
if n == 3 or (n>1 and isprime(n+1)): return 2
c = 0
for p in partitions(n):
s, a = '', 1
for d in sorted(Counter(p).elements()):
s += '1'*(d-a)+'0'
a = d
if s[:-1] == s[-2::-1]:
c += 1
return c # Chai Wah Wu, Feb 06 2024
(Python)
from math import comb
from sympy import divisors
def A368548(n): # faster program using formula
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
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
return x+y # Chai Wah Wu, Feb 08 2024
CROSSREFS
KEYWORD
nonn
AUTHOR
Michel Marcus, Feb 06 2024
EXTENSIONS
a(41)-a(67) from Chai Wah Wu, Feb 06 2024
STATUS
approved