A054628 -id:A054628 - cp's OEIS frontend

A054616 a(n) = Sum_{d|n} phi(d)*9^(n/d).

0, 9, 90, 747, 6660, 59085, 532350, 4783023, 43053480, 387422001, 3486843810, 31381059699, 282430082700, 2541865828437, 22876797238470, 205891132215735, 1853020231912080, 16677181699666713, 150094635685484490, 1350851717672992251

Offset: 0

N. J. A. Sloane, Apr 16 2000

nonn

Seiichi Manyama, Table of n, a(n) for n = 0..1000

Column k=9 of A185651.

Cf. A054628.

a(n) = if(n==0, 0, sumdiv(n, d, eulerphi(d)*9^(n/d))); \\ Altug Alkan, Mar 16 2018

a(n) = Sum_{k=1..n} 9^gcd(n,k). - Ilya Gutkovskiy, Apr 16 2021

A121775 T(n, k) = Sum_{d|n} phi(n/d)*binomial(d,k) for n>0, T(0, 0) = 1. Triangle read by rows, for 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 2, 3, 1, 3, 5, 3, 1, 4, 8, 7, 4, 1, 5, 9, 10, 10, 5, 1, 6, 15, 20, 21, 15, 6, 1, 7, 13, 21, 35, 35, 21, 7, 1, 8, 20, 36, 60, 71, 56, 28, 8, 1, 9, 21, 42, 86, 126, 126, 84, 36, 9, 1, 10, 27, 59, 130, 215, 253, 210, 120, 45, 10, 1, 11, 21, 55, 165, 330, 462, 462, 330, 165, 55

Offset: 0

Paul D. Hanna, Aug 23 2006

For n>0, (1/n)*Sum_{k=0..n} T(n,k)*(c-1)^k is the number of n-bead necklaces with c colors. See the cross references.

			Triangle begins:
[ 0]  1;
[ 1]  1,  1;
[ 2]  2,  3,  1;
[ 3]  3,  5,  3,   1;
[ 4]  4,  8,  7,   4,   1;
[ 5]  5,  9, 10,  10,   5,   1;
[ 6]  6, 15, 20,  21,  15,   6,   1;
[ 7]  7, 13, 21,  35,  35,  21,   7,   1;
[ 8]  8, 20, 36,  60,  71,  56,  28,   8,  1;
[ 9]  9, 21, 42,  86, 126, 126,  84,  36,  9,  1;
[10] 10, 27, 59, 130, 215, 253, 210, 120, 45, 10, 1;

Cf. A053635 (row sums), A121776 (antidiagonal sums), A054630, A327029.

Cf. A000031 (c=2), A001867 (c=3), A001868 (c=4), A001869 (c=5), A054625 (c=6), A054626 (c=7), A054627 (c=8), A054628 (c=9), A054629 (c=10).

PARI
```
T(n,k)=if(n
				
```

# uses[DivisorTriangle from A327029]
DivisorTriangle(euler_phi, binomial, 13) # Peter Luschny, Aug 24 2019

cp's OEIS Frontend

A054616 a(n) = Sum_{d|n} phi(d)*9^(n/d).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula