OFFSET
0,3
COMMENTS
Consider the compositions of n that are capable of being rearranged into a palindrome, with a fixed, central summand allowed. Then the number of such palindrome-capable compositions of 2n or 2n+1 is a(0)+...+a(n). - Gregory L. Simay, Nov 27 2018
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 51 terms from Vladeta Jovovic)
FORMULA
a(n) ~ 2^(2*n-1) / n. - Vaclav Kotesovec, Sep 10 2014
EXAMPLE
a(3) = 8 because we have: 3+3, 2+2+1+1, 2+1+2+1, 2+1+1+2, 1+2+2+1, 1+2+1+2, 1+1+2+2, 1+1+1+1+1+1. - Geoffrey Critzer, May 12 2014
Note that in Geoffrey's example (in which there's no central summand) all 8 compositions of 6=3*2 are either palindromes or can be rearranged into palindromes. The compositions of 2*2=4 with even multiplic1ty are 2+2 and 1+1+1+1, and are counted by a(2). Adding a fixed, central summand of 2, yields 2 more palindrome-capable compositions of 6: 2+2+2 and 1+1+2+1+1. The composition of 2*1=2 with even multiplicity is 1+1. Adding a fixed, central summand of 4 yields 1 more palindrome composition of 6: 1+4+1. Finally, the bare central summand of 6 is counted by a(0)=1. Hence, the total number of compositions of 6 that are palindrome capable is a(0)+...+a(3), if the central summand is fixed. This sum also gives the total number of palindrome-capable compositions of 7, employing fixed, central summands of 1,3,5 and 7. Gregory L. Simay, Nov 27 2018
MAPLE
b:= proc(n, i, p) option remember; `if`(n=0, p!, `if`(i<1, 0, add(
`if`(irem(j, 2)=0, b(n-i*j, i-1, p+j)/j!, 0), j=0..n/i)))
end:
a:= n-> b(2*n$2, 0):
seq(a(n), n=0..35); # Alois P. Heinz, May 12 2014
MATHEMATICA
Select[Table[Length[Select[Level[Map[Permutations, IntegerPartitions[n]], {2}], Apply[And, EvenQ[Table[Count[#, #[[i]]], {i, 1, Length[#]}]]]&]], {n, 0, 20}], #>0&] (* Geoffrey Critzer, May 12 2014 *)
b[n_, i_, p_] := b[n, i, p] = If[n == 0, p!, If[i < 1, 0, Sum[If[Mod[j, 2] == 0, b[n - i*j, i - 1, p + j]/j!, 0], {j, 0, n/i}]]];
a[n_] := b[2n, 2n, 0];
Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Aug 30 2016, after Alois P. Heinz *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Vladeta Jovovic, Aug 08 2007
STATUS
approved