A368548 Number of palindromic partitions of n.

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

Author

Michel Marcus, Feb 06 2024

Keywords

• nonn

Comments

For n>1, a(n) >= 2 as [n] and [1,1,..1] are both palindromic partitions. - Chai Wah Wu, Feb 07 2024

Examples

			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
		

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

Crossrefs

Cf. A068499 (a(n)=2, n>1).

Programs

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

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)

Extensions

a(41)-a(67) from Chai Wah Wu, Feb 06 2024