login
A368548
Number of palindromic partitions of n.
3
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, 60, 2, 38, 34, 18, 46, 104, 2, 20, 46, 108, 2, 122, 2, 94, 148, 24, 2, 212, 58, 116, 76, 140, 2, 232, 164, 270, 94, 30, 2, 588, 2, 32, 372, 274, 280, 420, 2, 276
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
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.
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
Cf. A068499 (a(n)=2, n>1).
Sequence in context: A220498 A330772 A105681 * A375783 A240039 A369902
KEYWORD
nonn
AUTHOR
Michel Marcus, Feb 06 2024
EXTENSIONS
a(41)-a(67) from Chai Wah Wu, Feb 06 2024
STATUS
approved