login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A087854 Triangle read by rows: T(n,k) is the number of n-bead necklaces with exactly k different colored beads. 13
1, 1, 1, 1, 2, 2, 1, 4, 9, 6, 1, 6, 30, 48, 24, 1, 12, 91, 260, 300, 120, 1, 18, 258, 1200, 2400, 2160, 720, 1, 34, 729, 5106, 15750, 23940, 17640, 5040, 1, 58, 2018, 20720, 92680, 211680, 258720, 161280, 40320, 1, 106, 5613, 81876, 510312, 1643544, 2963520, 3024000, 1632960, 362880 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,5

COMMENTS

Equivalently, T(n,k) is the number of sequences (words) of length n on an alphabet of k letters where each letter of the alphabet occurs at least once in the sequence.  Two sequences are considered equivalent if one can be obtained from the other by a cyclic shift of the letters. Cf. A054631 where the surjective restriction is removed. - Geoffrey Critzer, Jun 18 2013

LINKS

Alois P. Heinz, Rows n = 1..141, flattened

FORMULA

T(n,k) = Sum_{i=0..k-1} (-1)^i * C(k,i) * A075195(n,k-1); A075195 = Jablonski's table.

T(n,k) = (k!/n) * Sum_{d divides n} phi(d) * S2(n/d, k); = S2(n,k) = Stirling numbers of 2nd kind A008277.

G.f. for column k: -Sum_{d>0} (phi(d)/d) * Sum_{j} (-1)^(k-j) * C(k,j) * log(1-j x^d). - Robert A. Russell, Sep 26 2018

EXAMPLE

The triangle begins with T(1,1):

  1;

  1,   1;

  1,   2,    2;

  1,   4,    9,     6;

  1,   6,   30,    48,     24;

  1,  12,   91,   260,    300,     120;

  1,  18,  258,  1200,   2400,    2160,     720;

  1,  34,  729,  5106,  15750,   23940,   17640,    5040;

  1,  58, 2018, 20720,  92680,  211680,  258720,  161280,   40320;

  1, 106, 5613, 81876, 510312, 1643544, 2963520, 3024000, 1632960, 362880;

  ...

For T(4,2)=4, the necklaces are AAAB, AABB, ABAB, and ABBB.

For T(4,4)=6, the necklaces are ABCD, ABDC, ACBD, ACDB, ADBC, and ADCB.

MAPLE

with(numtheory):

T:= (n, k)-> (k!/n) *add(phi(d) *Stirling2(n/d, k), d=divisors(n)):

seq(seq(T(n, k), k=1..n), n=1..12);  # Alois P. Heinz, Jun 19 2013

MATHEMATICA

Table[Table[Sum[EulerPhi[d]*StirlingS2[n/d, k]k!, {d, Divisors[n]}]/n, {k, 1, n}], {n, 1, 10}]//Grid (* Geoffrey Critzer, Jun 18 2013 *)

CROSSREFS

Columns 1-6: A057427, A052823, A056283, A056284, A056285, A056286.

Diagonals: A000142 and A074143.

Row sums: apparently A019536.

Cf. Euler totient function phi A000010, A075195 = (Table of Jablonski), A008277 (Stirling 2 numbers).

Cf. A254040, A273891.

Sequence in context: A137399 A158985 A295687 * A185041 A086873 A101560

Adjacent sequences:  A087851 A087852 A087853 * A087855 A087856 A087857

KEYWORD

nonn,tabl,easy

AUTHOR

Philippe Deléham

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 18 07:01 EST 2018. Contains 317279 sequences. (Running on oeis4.)