A001867 -id:A001867 - cp's OEIS frontend

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.

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

A210323 Number of 2-divided words of length n over a 3-letter alphabet.

Original entry on oeis.org

0, 3, 16, 57, 192, 599, 1872, 5727, 17488, 53115, 161040, 487073, 1471680, 4441167, 13392272, 40355877, 121543680, 365895947, 1101089808, 3312442185, 9962240928, 29954639751, 90049997136, 270661616363, 813397065024, 2444101696683, 7343167947040, 22059763982001, 66263812628160

Offset: 1

N. J. A. Sloane, Mar 20 2012

nonn

See A210109 for further information.
It appears that A027376 gives the number of 2-divided words that have a unique division into two parts. - David Scambler, Mar 21 2012
Row sums of the following irregular triangle W(n,k) which shows how many words of length n over a 3-letter alphabet are 2-divided in k>=1 different ways (3-letter analog of A209919):
3;
8, 8;
18, 21, 18;
48, 48, 48, 48;
116, 124, 119, 124, 116;
312, 312, 312, 312, 312, 312;
810, 828, 810, 831, 810, 828, 810;
2184, 2184, 2192, 2184, 2184, 2192, 2184, 2184;
5880, 5928, 5880, 5928, 5883, 5928, 5880, 5928, 5880;
First column of the following triangle D(n,k) which shows how many words of length n over a 3-letter alphabet are k-divided:
3;
16, 1;
57, 16, 0;
192, 78, 6, 0;
599, 324, 56, 0, 0;
1872, 1141, 343, 15, 0, 0;
5727, 3885, 1534, 166, 0, 0, 0;
17488, 12630, 6067, 1135, 20, 0, 0, 0;
53115, 40315, 22162, 5865, 351, 0, 0, 0, 0;
161040, 126604, ...
- R. J. Mathar, Mar 25 2012
Speculation: W(2n+1,2)=W(2n+1,1) and W(2n,2) = W(2n,1)+W(n,1). W(3n+1,3)=W(3n+1,1); W(3n+2,3)=W(3n+1,1); W(3n,3) = W(3n,1)+W(n,1). - R. J. Mathar, Mar 27 2012

Cf. A210109, A209970, A001867.

a(n) = 3^n - A001867(n) (see A209970 for proof).

a(1)-a(12) computed by David Scambler, Mar 19 2012; a(13) onwards from N. J. A. Sloane, Mar 20 2012

A278663 Number of periodic necklaces with n beads of 3 colors.

Original entry on oeis.org

0, 0, 3, 3, 6, 3, 14, 3, 24, 11, 54, 3, 148, 3, 318, 59, 834, 3, 2314, 3, 5952, 323, 16110, 3, 45178, 51, 122646, 2195, 341820, 3, 962634, 3, 2690844, 16115, 7596486, 363, 21568780, 3, 61171662, 122651, 174343026, 3, 498453878, 3, 1426419876, 958819, 4093181694, 3, 11770610128, 315, 33891550302

Offset: 0

Herbert Kociemba, Nov 25 2016

nonn

			Example: The 6 periodic necklaces with 4 beads and the colors A, B and C are AAAA, BBBB, CCCC, ABAB, ACAC and BCBC.

Cf. A001867, A027376, A066656 (2 colors).

mx=40;f[x_,k_]:=Sum[(MoebiusMu[i]-EulerPhi[i])Log[1-k*x^i]/i,{i,1,mx}];CoefficientList[Series[f[x,3],{x,0,mx}],x]

G.f.: k=3, Sum_{i>=1} (mu(i) - phi(i))*log(1 - k*x^i)/i.

a(n) = A001867(n) - A027376(n). - Alois P. Heinz, Nov 25 2016

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

SageMath

A210323 Number of 2-divided words of length n over a 3-letter alphabet.

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions

A278663 Number of periodic necklaces with n beads of 3 colors.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula