A239342 Number of 1's in all compositions of n into odd parts.

0, 1, 2, 3, 6, 11, 20, 36, 64, 113, 198, 345, 598, 1032, 1774, 3039, 5190, 8839, 15016, 25452, 43052, 72685, 122502, 206133, 346346, 581136, 973850, 1630011, 2725254, 4551683, 7594748, 12660660, 21087448, 35094377, 58360134, 96979089, 161042110, 267248664

Offset: 0

Author

Geoffrey Critzer, Mar 16 2014

Keywords

• nonn

Comments

a(n+1) is the number of ways to tile a strip of length n+1 using white tiles of only odd lengths, with total length n, and one red square of length one. - Gregory L. Simay, Aug 14 2016

A029907, the number of compositions of n with exactly one even part, is equal to a(n+1-2) + a(n+1-4) + a(n+1-6) + ... - Gregory L. Simay, Aug 14 2016

Apart from the initial 0 and 1, this is the p-INVERT transform of (1,0,1,0,1,0,...) for p(S) = (1 - S)^2. See A291219. - Clark Kimberling, Sep 02 2017

Examples

			a(5) = 11 because in the compositions of 5 into odd parts there are a total of 11 1's: 5, 3+1+1, 1+3+1, 1+1+3, 1+1+1+1+1.
Let r represent the red square and 1,3,5 represent the possible odd lengths of the white squares for n=5. Then a(5+1) = a(6) = 20 because r combined with a tile of length 5 generates 2 compositions; r combined with 3,1,1 generates 12 compositions; and r combined with 1,1,1,1,1 generates 6 compositions. 2+12+6 = 20. - _Gregory L. Simay_, Aug 14 2016
		

References

• S. Heubach and T. Mansour, Combinatorics of Compositions and Words, Chapman and Hall, 2010, page 70.

Links

• Michael De Vlieger, Table of n, a(n) for n = 0..4771
• Mengmeng Liu, Andrew Yezhou Wang, The Number of Designated Parts in Compositions with Restricted Parts, J. Int. Seq., Vol. 23 (2020), Article 20.1.8.

Crossrefs

Cf. A000045, A029907.

Programs

Mathematica

nn=30;CoefficientList[Series[x (1-x^2)^2/(1-x-x^2)^2,{x,0,nn}],x]
(* or *)
Table[Count[Flatten[Level[Map[Permutations,IntegerPartitions[n,n,Table[2k+1,{k,0,n/2}]]],{2}]],1],{n,0,30}]

Formula

For n >= 4, a(n) = a(n-1) + a(n-2) + A000045(n-2).

G.f.: x*(1 - x^2)^2/(1 - x - x^2)^2.