login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A320748 Array read by antidiagonals: T(n,k) is the number of color patterns (set partitions) in an unoriented cycle of length n using k or fewer colors (subsets). 6
1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 3, 4, 1, 1, 2, 3, 6, 4, 1, 1, 2, 3, 7, 9, 8, 1, 1, 2, 3, 7, 11, 22, 9, 1, 1, 2, 3, 7, 12, 33, 40, 18, 1, 1, 2, 3, 7, 12, 36, 73, 100, 23, 1, 1, 2, 3, 7, 12, 37, 89, 237, 225, 44, 1, 1, 2, 3, 7, 12, 37, 92, 322, 703, 582, 63, 1, 1, 2, 3, 7, 12, 37, 93, 349, 1137, 2433, 1464, 122, 1, 1, 2, 3, 7, 12, 37, 93, 353, 1308, 4704, 8309, 3960, 190, 1, 1, 2, 3, 7, 12, 37, 93, 354, 1345, 5953, 19839, 30108, 10585, 362, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,5

COMMENTS

Two color patterns are equivalent if the colors are permuted. An unoriented cycle counts each chiral pair as one, i.e., they are equivalent.

Adnk[d,n,k] in Mathematica program is coefficient of x^k in A(d,n)(x) in Gilbert and Riordan reference.

T(n,k)=Pi_k(C_n) which is the number of non-equivalent partitions of the cycle on n vertices, with at most k parts. Two partitions P1 and P2 of a graph G are said to be equivalent if there is a nontrivial automorphism of G which maps P1 onto P2. - Bahman Ahmadi, Aug 21 2019

In other words, the number of n-bead bracelet structures using a maximum of k different colored beads. - Andrew Howroyd, Oct 30 2019

REFERENCES

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..1275

B. Ahmadi, F. Alinaghipour and M. H. Shekarriz, Number of Distinguishing Colorings and Partitions, arXiv:1910.12102 [math.CO], 2019.

E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.

FORMULA

T(n,k) = Sum_{j=1..k} Ach(n,j)/2 + (1/2n)*Sum_{d|n} phi(d)*A(d,n/d,j), where Ach(n,k) = [n>=0 & n<2 & n==k] + [n>1]*(k*Ach(n-2,k)+Ach(n-2,k-1)+Ach(n-2,k-2)) and A(d,n,k) = [n==0 & k==0] + [n>0 & k>0]*(k*A(d,n-1,k) + Sum_{j|d} A(d,n-1,k-j)).

T(n,k) = (A320747(n,k) + A305749(n,k)) / 2 = A320747(n,k) - A320742(n,k) = A320742(n,k) + A305749(n,k).

EXAMPLE

Array begins with T(1,1):

1   1    1     1     1      1      1      1      1      1      1      1 ...

1   2    2     2     2      2      2      2      2      2      2      2 ...

1   2    3     3     3      3      3      3      3      3      3      3 ...

1   4    6     7     7      7      7      7      7      7      7      7 ...

1   4    9    11    12     12     12     12     12     12     12     12 ...

1   8   22    33    36     37     37     37     37     37     37     37 ...

1   9   40    73    89     92     93     93     93     93     93     93 ...

1  18  100   237   322    349    353    354    354    354    354    354 ...

1  23  225   703  1137   1308   1345   1349   1350   1350   1350   1350 ...

1  44  582  2433  4704   5953   6291   6345   6350   6351   6351   6351 ...

1  63 1464  8309 19839  28228  31284  31874  31944  31949  31950  31950 ...

1 122 3960 30108 88508 144587 171283 178190 179204 179300 179306 179307 ...

For T(7,2)=9, the patterns are AAAAAAB, AAAAABB, AAAABAB, AAAABBB, AAABAAB, AAABABB, AABAABB, AABABAB, and AAABABB; only the last is chiral, paired with AAABBAB.

MATHEMATICA

Adnk[d_, n_, k_] := Adnk[d, n, k] = If[n>0 && k>0, Adnk[d, n-1, k]k + DivisorSum[d, Adnk[d, n-1, k-#]&], Boole[n == 0 && k == 0]]

Ach[n_, k_] := Ach[n, k] = If[n<2, Boole[n==k && n>=0], k Ach[n-2, k] + Ach[n-2, k-1] + Ach[n-2, k-2]] (* A304972 *)

Table[Sum[(DivisorSum[n, EulerPhi[#] Adnk[#, n/#, j]&]/n + Ach[n, j])/2, {j, k-n+1}], {k, 15}, {n, k}] // Flatten

PROG

(PARI) \\ Ach is A304972 and R is A152175 as square matrices.

Ach(n)={my(M=matrix(n, n, i, k, i>=k)); for(i=3, n, for(k=2, n, M[i, k]=k*M[i-2, k] + M[i-2, k-1] + if(k>2, M[i-2, k-2]))); M}

R(n)={Mat(Col([Vecrev(p/y, n) | p<-Vec(intformal(sum(m=1, n, eulerphi(m) * subst(serlaplace(-1 + exp(sumdiv(m, d, y^d*(exp(d*x + O(x*x^(n\m)))-1)/d))), x, x^m))/x))]))}

T(n)={my(M=(R(n) + Ach(n))/2); for(i=2, n, M[, i] += M[, i-1]); M}

{ my(A=T(12)); for(n=1, #A, print(A[n, ])) } \\ Andrew Howroyd, Nov 03 2019

CROSSREFS

Partial row sums of A152176.

Columns 1-6 are A057427, A000011, A056353, A056354, A056355, A056356

For increasing k, columns converge to A084708.

Cf. A320747 (oriented), A320742 (chiral), A305749 (achiral).

Sequence in context: A323767 A159936 A305749 * A320747 A238392 A144464

Adjacent sequences:  A320745 A320746 A320747 * A320749 A320750 A320751

KEYWORD

nonn,tabl,easy

AUTHOR

Robert A. Russell, Oct 21 2018

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 17 16:00 EDT 2021. Contains 347478 sequences. (Running on oeis4.)