A130495 Number of compositions of 2n in which each part has even multiplicity.

1, 1, 2, 8, 24, 72, 264, 952, 3352, 11960, 43656, 160840, 594568, 2215480, 8300056, 31191480, 117674504, 445439944, 1691011464, 6437425720, 24564925848, 93937631544, 359943235080, 1381706541512, 5312678458888, 20458827990456, 78898261863832, 304666752525368

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

Cf. A242391 (for odd multiplicity).

Sequence in context: A290904 A231200 A066973 * A026070 A093833 A228404

Adjacent sequences: A130492 A130493 A130494 * A130496 A130497 A130498

Keyword

nonn

Author

Vladeta Jovovic, Aug 08 2007

Status

approved