|
%I #72 Feb 11 2024 02:29:43
%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>
%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
|
