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,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

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 * A240039 A369902 A130127

Adjacent sequences: A368545 A368546 A368547 * A368549 A368550 A368551

Keyword

nonn

Author

Michel Marcus, Feb 06 2024

Extensions

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

Status

approved