login
Number of compositions of n if only the order of the odd numbers matter.
2

%I #36 Jun 02 2018 14:19:39

%S 1,1,2,3,6,9,16,25,43,68,113,181,298,479,781,1260,2048,3308,5364,8672,

%T 14048,22720,36782,59502,96305,155807,252136,407943,660113,1068056,

%U 1728210,2796266,4524531,7320797,11845394,19166191,31011673,50177864,81189642,131367506

%N Number of compositions of n if only the order of the odd numbers matter.

%C The number of partitions of n = 2k with only even numbers is p(k) = A000041(k). The number of compositions of n with only odd numbers is F(n) = the n-th Fibonacci number = A000045(n). Enumerating a(n) is therefore a sum of products of partition numbers and Fibonacci numbers.

%H Alois P. Heinz, <a href="/A275548/b275548.txt">Table of n, a(n) for n = 0..1000</a>

%F a(2k+1) = Sum_{j=0..k} p(j)*F(2k + 1 - 2j), where p(j) = A000041(j), the number of partitions of j, and F(j) = A000045(j), the j-th Fibonacci number.

%F a(2k) = p(k) + Sum_{j=0..(k-1)} p(j)*F(2k - 2j).

%F a(2k+1) = a(2k) + a(2k-1).

%F a(2k) = a(2k-1) + a(2k-2) + p(k) - p(k-1).

%F G.f.: 1/(1 - x - x^2) * Product_{n>=2} 1/(1 - x^(2*n)). - _Peter Bala_, Aug 03 2016 [corrected by _Vaclav Kotesovec_, Jun 02 2018]

%F a(n) ~ c * phi^n, where c = 1 / (sqrt(5) * QPochhammer[1/phi^2]) = 0.92890318501026782066... and phi = A001622 = (1 + sqrt(5))/2 is the golden ratio. - _Vaclav Kotesovec_, Jun 02 2018

%e The compositions enumerated by a(6) = 16 are (6),(5,1),(1,5),(4,2)=(2,4), (3,3), (4,1,1)=(1,4,1)=(1,1,4), (2,3,1)=(3,2,1)=(3,1,2), (2,1,3)=(1,2,3)=(1,3,2), (2,2,2), (3,1,1,1),(1,3,1,1),(1,1,3,1),(1,1,1,3), (2,2,1,1)=(2,1,2,1)=(2,1,1,2)=(1,2,1,2)=(1,1,2,2)=(1,2,2,1), (2,1,1,1,1)=(1,2,1,1,1)=(1,1,2,1,1)=(1,1,1,2,1)=(1,1,1,1,2), (1,1,1,1,1,1).

%e The compositions enumerated by a(5) = 9 are (5), (4,1)=(1,4), (3,2)=(2,3), (3,1,1), (1,3,1), (1,1,3), (2,2,1)=(2,1,2)=(1,2,2), (2,1,1,1)=(1,2,1,1)=(1,1,2,1)=(1,1,1,2), (1,1,1,1,1).

%p b:= proc(n, i, p) option remember; (t-> `if`(n=0, p!,

%p `if`(i<1, 0, add(b(n-i*j, i-1, p+`if`(t, j, 0))/

%p `if`(t, j, 0)!, j=0..n/i))))(i::odd)

%p end:

%p a:= n-> b(n$2, 0):

%p seq(a(n), n=0..50); # _Alois P. Heinz_, Aug 03 2016

%t b[n_, i_, p_] := b[n, i, p] = If[n == 0, p!, If[i < 1, 0, Sum[b[n - i*j, i - 1, p + If[#, j, 0]]/If[#, j, 0]!, {j, 0, n/i}]]]&[OddQ[i]];

%t a[n_] := b[n, n, 0];

%t Table[a[n], {n, 0, 50}] (* _Jean-François Alcover_, May 21 2018, after _Alois P. Heinz_ *)

%t nmax = 40; CoefficientList[Series[1/(1 - x - x^2) * Product[1/(1 - x^(2*k)), {k, 2, nmax}], {x, 0, nmax}], x] (* _Vaclav Kotesovec_, Jun 02 2018 *)

%Y Cf. A000041, A000045, A275592.

%K nonn

%O 0,3

%A _Gregory L. Simay_, Aug 01 2016