A275548 Number of compositions of n if only the order of the odd numbers matter.
1, 1, 2, 3, 6, 9, 16, 25, 43, 68, 113, 181, 298, 479, 781, 1260, 2048, 3308, 5364, 8672, 14048, 22720, 36782, 59502, 96305, 155807, 252136, 407943, 660113, 1068056, 1728210, 2796266, 4524531, 7320797, 11845394, 19166191, 31011673, 50177864, 81189642, 131367506
Offset: 0
Keywords
Examples
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). 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).
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..1000
Programs
-
Maple
b:= proc(n, i, p) option remember; (t-> `if`(n=0, p!, `if`(i<1, 0, add(b(n-i*j, i-1, p+`if`(t, j, 0))/ `if`(t, j, 0)!, j=0..n/i))))(i::odd) end: a:= n-> b(n$2, 0): seq(a(n), n=0..50); # Alois P. Heinz, Aug 03 2016 -
Mathematica
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]]; a[n_] := b[n, n, 0]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, May 21 2018, after Alois P. Heinz *) 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 *)
Formula
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.
a(2k) = p(k) + Sum_{j=0..(k-1)} p(j)*F(2k - 2j).
a(2k+1) = a(2k) + a(2k-1).
a(2k) = a(2k-1) + a(2k-2) + p(k) - p(k-1).
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]
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
Comments