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

%I

%S 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,

%T 2400,2160,720,1,34,729,5106,15750,23940,17640,5040,1,58,2018,20720,

%U 92680,211680,258720,161280,40320,1,106,5613,81876,510312,1643544,2963520,3024000,1632960,362880

%N Triangle read by rows: T(n,k) is the number of n-bead necklaces with exactly k different colored beads.

%C 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

%H Alois P. Heinz, <a href="/A087854/b087854.txt">Rows n = 1..141, flattened</a>

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

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

%F 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

%e The triangle begins with T(1,1):

%e 1;

%e 1, 1;

%e 1, 2, 2;

%e 1, 4, 9, 6;

%e 1, 6, 30, 48, 24;

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

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

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

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

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

%e ...

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

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

%p with(numtheory):

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

%p seq(seq(T(n,k), k=1..n), n=1..12); # _Alois P. Heinz_, Jun 19 2013

%t 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 *)

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

%Y Diagonals: A000142 and A074143.

%Y Row sums: apparently A019536.

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

%Y Cf. A254040, A273891.

%K nonn,tabl,easy

%O 1,5

%A _Philippe Deléham_

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 17 05:59 EST 2018. Contains 317275 sequences. (Running on oeis4.)