

A072951


a(n) = Sum_{k=1..n} binomial(k, n mod k).


3



1, 2, 4, 6, 11, 15, 27, 39, 63, 100, 159, 247, 403, 641, 1023, 1644, 2653, 4264, 6872, 11081, 17895, 28899, 46680, 75420, 121918, 197113, 318728, 515420, 833592, 1348309, 2181022, 3528144, 5707568, 9233629, 14938481, 24168531, 39102324
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

a(n) = Sum_{k>=2} z(k)*v(k)^n where v(k) is the real positive solution to x^k = x + 1 (i.e., the kth PisotVijayaraghavan number) and z(k) is the real positive root of a polynomial P(k,x) with integer coefficients of degree k.
In particular a(n) is asymptotic to (1/10)*(5 + sqrt(5))*phi^n where phi is the golden ratio.
First P(k,x) are P(2,x) = 5x^2  5x  1; P(3,x) = 23x^3  23x^2 + 8x  1; P(4) = 283x^4  283x^3 + 105x^2  17x + 1; P(5) = 2869x^5  2869x^4 + 1154x^3  234x^2 + 24x  1.
a(n) is the number of compositions of n into almost equal parts. It means the difference between the largest part and the smallest part is at most 1. For example, there are 6 compositions of 4 into almost equal parts, (4), (2,2), (2,1,1), (1,2,1), (1,1,2), (1,1,1,1).  Ran Pan, Oct 16 2015


LINKS

Vincenzo Librandi, Table of n, a(n) for n = 1..1000


MATHEMATICA

Table[Sum[Binomial[k, Mod[n, k]], {k, n}], {n, 37}] (* Michael De Vlieger, Jul 30 2017 *)


PROG

(PARI) a(n)=sum(k=1, n, binomial(k, n%k))
(MAGMA) [&+[Binomial(k, n mod k): k in [1..n]]: n in [1..40]]; // Vincenzo Librandi, Jul 31 2017


CROSSREFS

Sequence in context: A187492 A103580 A094866 * A325591 A062766 A115269
Adjacent sequences: A072948 A072949 A072950 * A072952 A072953 A072954


KEYWORD

easy,nonn


AUTHOR

Benoit Cloitre, Aug 20 2002


EXTENSIONS

Name from Benoit Cloitre, May 03 2003


STATUS

approved



