login
a(n) = Sum_{k divides n} (n/k)^k.
45

%I #43 Aug 07 2022 11:38:02

%S 1,3,4,9,6,24,8,41,37,68,12,258,14,192,384,593,18,1557,20,2794,2552,

%T 2192,24,16730,3151,8388,20440,35394,30,116474,32,135457,178512,

%U 131396,94968,1111035,38,524688,1596560,2530986,42,7280934,44,8403778

%N a(n) = Sum_{k divides n} (n/k)^k.

%C a(n) is the number of (nonempty) linear partitions of the linearly ordered set [n] = {1,2,...,n} with blocks of the same size, where each block has exactly one element marked. For instance, for n = 4, we have the following 9 linear partitions (where the marked elements are denoted by *):

%C . (*)(*)(*)(*), (*2)(*4), (*234),

%C . (*2)(3*), (1*34),

%C . (1*)(*4), (12*4),

%C . (1*)(3*), (123*).

%C - _Emanuele Munarini_, Feb 03 2014

%H Nick Hobson, <a href="/A055225/b055225.txt">Table of n, a(n) for n = 1..1000</a>

%F G.f.: Sum_{n>=1} -log(1 - n*x^n)/n = Sum_{n>=0} a(n) x^n/n. - _Paul D. Hanna_, Aug 04 2002

%F G.f.: Sum_{n>0} n*x^n/(1-n*x^n). - _Vladeta Jovovic_, Sep 02 2002

%F Sum_{k=1..n} a(k) ~ 3^((n + 3 - mod(n,3))/3)/2. - _Vaclav Kotesovec_, Aug 07 2022

%e a(10) = 10^1 + 5^2 + 2^5 + 1^10 = 68 because positive divisors of 10 are 1, 2, 5, 10.

%t Table[Total[Quotient[n, x = Divisors[n]]^x], {n, 44}] (* _Jayanta Basu_, Jul 08 2013 *)

%t Table[Sum[d^(n/d), {d, Divisors[n]}], {n, 1, 100}] (* _Emanuele Munarini_, Feb 03 2014 *)

%o (PARI) vector(44, n, sumdiv(n, d, (n/d)^d))

%o (PARI) a(n) = sumdiv(n,d, d^(n/d) ); \\ _Joerg Arndt_, Apr 14 2013

%o (Maxima) a(n) := lsum(d^(n/d), d, listify(divisors(n))); makelist(a(n), n, 1, 40); /* _Emanuele Munarini_, Feb 03 2014 */

%Y Cf. A005225, A038041, A236696.

%K nonn

%O 1,2

%A _Leroy Quet_, Jun 20 2000

%E More terms from _James A. Sellers_, Jul 04 2000

%E Duplicate g.f. removed by _Franklin T. Adams-Watters_, Sep 01 2009