login
Number of palindromic partitions of n.
3

%I #76 Aug 28 2024 13:41:51

%S 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 60,2,38,34,18,46,104,2,20,46,108,2,122,2,94,148,24,2,212,58,116,76,

%U 140,2,232,164,270,94,30,2,588,2,32,372,274,280,420,2,276

%N Number of palindromic partitions of n.

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

%H Chai Wah Wu, <a href="/A368548/b368548.txt">Table of n, a(n) for n = 1..10000</a>

%H 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 Chai Wah Wu, <a href="/A368548/a368548.pdf">Proofs of formulas for A368548</a>

%H Chai Wah Wu, <a href="/A368548/a368548_1.pdf">Proofs of formulas for A368548 and A375783</a>

%F From _Chai Wah Wu_, Feb 08 2024: (Start)

%F 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 Let y = 2*Sum_{d|n+1, d>=3, and d is odd} binomial((d-5)/2+(n+1)/d,(d-3)/2).

%F Then a(n) = x+y.

%F a(n) = 2 if n>1 and n+1 is prime.

%F a(n) = (n+3)/2 if n>3 is odd and (n+1)/2 is prime.

%F a(2^n-1) = Sum_{i=0..n-1} binomial(2^i+2^(n-i-1)-2,2^i-1).

%F (End)

%e 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 (Python)

%o from itertools import count

%o from math import comb

%o from collections import Counter

%o from sympy.utilities.iterables import partitions

%o from sympy import isprime

%o def A368548(n):

%o if n == 3 or (n>1 and isprime(n+1)): return 2

%o c = 0

%o for p in partitions(n):

%o s, a = '', 1

%o for d in sorted(Counter(p).elements()):

%o s += '1'*(d-a)+'0'

%o a = d

%o if s[:-1] == s[-2::-1]:

%o c += 1

%o return c # _Chai Wah Wu_, Feb 06 2024

%o (Python)

%o from math import comb

%o from sympy import divisors

%o def A368548(n): # faster program using formula

%o 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 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 return x+y # _Chai Wah Wu_, Feb 08 2024

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

%K nonn

%O 1,2

%A _Michel Marcus_, Feb 06 2024

%E a(41)-a(67) from _Chai Wah Wu_, Feb 06 2024