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

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

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 k-th Pisot-Vijayaraghavan 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: A366127 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