login
a(n) = Sum_{d|n} (2^(n-d)).
16

%I #37 Jul 17 2020 00:34:15

%S 1,3,5,13,17,57,65,209,321,801,1025,3905,4097,12417,21505,53505,65537,

%T 233985,262145,885761,1327105,3147777,4194305,16060417,17825793,

%U 50339841,84148225,220217345,268435457,990937089,1073741825,3506503681

%N a(n) = Sum_{d|n} (2^(n-d)).

%C A034729 = Sum_{d|n} (2^(d-1)).

%C A055895 = 2*A034729.

%C If p is a prime, then a(p) = A034729(p) = 2^(p-1)+1.

%C From _Gus Wiseman_, Jul 14 2020: (Start)

%C Number of ways to tile a rectangle of size n using horizontal strips. Also the number of ways to choose a composition of each part of a constant partition of n. The a(0) = 1 through a(5) = 17 splittings are:

%C () (1) (2) (3) (4) (5)

%C (1,1) (1,2) (1,3) (1,4)

%C (1),(1) (2,1) (2,2) (2,3)

%C (1,1,1) (3,1) (3,2)

%C (1),(1),(1) (1,1,2) (4,1)

%C (1,2,1) (1,1,3)

%C (2,1,1) (1,2,2)

%C (2),(2) (1,3,1)

%C (1,1,1,1) (2,1,2)

%C (1,1),(2) (2,2,1)

%C (2),(1,1) (3,1,1)

%C (1,1),(1,1) (1,1,1,2)

%C (1),(1),(1),(1) (1,1,2,1)

%C (1,2,1,1)

%C (2,1,1,1)

%C (1,1,1,1,1)

%C (1),(1),(1),(1),(1)

%C (End)

%H Gus Wiseman, <a href="/A074854/b074854.txt">Table of n, a(n) for n = 1..32</a>

%F G.f.: 2^n times coefficient of x^n in Sum_{k>=1} x^k/(2-x^k). - _Benoit Cloitre_, Apr 21 2003; corrected by _Joerg Arndt_, Mar 28 2013

%F G.f.: Sum_{k>0} 2^(k-1)*x^k/(1-2^(k-1)*x^k). - _Vladeta Jovovic_, Jun 24 2003

%F G.f.: Sum_{n>=1} a*z^n/(1-a*z^n) (generalized Lambert series) where z=2*x and a=1/2. - _Joerg Arndt_, Jan 30 2011

%F Triangle A051731 mod 2 converted to decimal. - _Philippe Deléham_, Oct 04 2003

%F G.f.: Sum_{k>0} 1 / (2 / (2*x)^k - 1). - _Michael Somos_, Mar 28 2013

%e Divisors of 6 = 1,2,3,6 and 6-1 = 5, 6-2 = 4, 6-3 = 3, 6-6 = 0. a(6) = 2^5 + 2^4 + 2^3 + 2^0 = 32 + 16 + 8 + 1 = 57.

%e G.f. = x + 3*x^2 + 5*x^3 + 13*x^4 + 17*x^5 + 57*x^6 + 65*x^7 + ...

%e a(14) = 1 + 2^7 + 2^12 + 2^13 = 12417. - _Gus Wiseman_, Jun 20 2018

%t a[ n_] := If[ n < 1, 0, Sum[ 2^(n - d), {d, Divisors[n]}]] (* _Michael Somos_, Mar 28 2013 *)

%o (PARI) a(n)=if(n<1,0,2^n*polcoeff(sum(k=1,n,2/(2-x^k),x*O(x^n)),n))

%o (PARI) a(n) = sumdiv(n,d, 2^(n-d) ); /* _Joerg Arndt_, Mar 28 2013 */

%Y Cf. A055895, A034729.

%Y Cf. A080267.

%Y Cf. A051731.

%Y The version looking at lengths instead of sums is A101509.

%Y The strictly increasing (or strictly decreasing) version is A304961.

%Y Starting with a partition gives A317715.

%Y Starting with a strict partition gives A318683.

%Y Requiring distinct instead of equal sums gives A336127.

%Y Starting with a strict composition gives A336130.

%Y Partitions of partitions are A001970.

%Y Splittings of compositions are A133494.

%Y Splittings of partitions are A323583.

%Y Cf. A006951, A063834, A075900, A279787, A305551, A316245, A323433, A336128.

%K easy,nonn

%O 1,2

%A _Miklos Kristof_, Sep 11 2002

%E a(14) corrected from 9407 to 12417 by _Gus Wiseman_, Jun 20 2018