login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A275548 Number of compositions of n if only the order of the odd numbers matter. 2
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

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.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..1000

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

EXAMPLE

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).

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 *)

CROSSREFS

Cf. A000041, A000045, A275592.

Sequence in context: A062114 A094768 A301753 * A260710 A093830 A320268

Adjacent sequences:  A275545 A275546 A275547 * A275549 A275550 A275551

KEYWORD

nonn

AUTHOR

Gregory L. Simay, Aug 01 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 12 21:10 EDT 2020. Contains 336440 sequences. (Running on oeis4.)