A309748 -id:A309748 - cp's OEIS frontend

A309784 T(n,k) is the number of non-equivalent distinguishing coloring partitions of the cycle on n vertices with exactly k parts. Regular triangle read by rows, n >= 1, 1 <= k <= n.

0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 4, 2, 1, 0, 1, 8, 10, 3, 1, 0, 1, 25, 32, 16, 3, 1, 0, 4, 62, 129, 84, 27, 4, 1, 0, 7, 176, 468, 433, 171, 37, 4, 1, 0, 18, 470, 1806, 2260, 1248, 338, 54, 5, 1, 0, 31, 1311, 6780, 11515, 8388, 3056, 590, 70, 5, 1, 0, 70, 3620, 25917, 58312, 56065, 26695, 6907, 1014, 96, 6, 1

Offset: 1

Mohammad Hadi Shekarriz, Aug 17 2019

The cycle graph is defined for n>=3; extended to n=1,2 using the closed form.
A vertex-coloring of a graph G is called distinguishing if it is only preserved by the identity automorphism of G. This notion is considered in the subject of symmetry breaking of simple (finite or infinite) graphs. A distinguishing coloring partition of a graph G is a partition of the vertices of G such that it induces a distinguishing coloring for G. We say two distinguishing coloring partitions P1 and P2 of G are equivalent if there is a nontrivial automorphism of G which maps P1 onto P2. Given a graph G, we use the notation psi_k(G) to denote the number of non-equivalent distinguishing coloring partitions of G with exactly k parts. For n>=3, this sequence gives T(n,k) = psi_k(C_n), i.e., the number of non-equivalent distinguishing coloring partitions of the cycle C_n on n vertices with exactly k parts.
T(n,k) is the number of primitive (period n) n-bead bracelet structures which are not periodic palindromes using exactly k different colored beads. - Andrew Howroyd, Sep 20 2019

			The triangle begins:
  0;
  0,  0;
  0,  0,   1;
  0,  0,   1,    1;
  0,  0,   4,    2,    1;
  0,  1,   8,   10,    3,    1;
  0,  1,  25,   32,   16,    3,   1;
  0,  4,  62,  129,   84,   27,   4,  1;
  0,  7, 176,  468,  433,  171,  37,  4, 1;
  0, 18, 470, 1806, 2260, 1248, 338, 54, 5, 1;
  ...
For n=6, we can partition the vertices of C_6 into exactly 3 parts in 8 ways such that all these partitions induce distinguishing colorings for C_6 and that all the 8 partitions are non-equivalent. The partitions are as follows:
    { { 1 }, { 2 }, { 3, 4, 5, 6 } }
    { { 1 }, { 2, 3 }, { 4, 5, 6 } }
    { { 1 }, { 2, 3, 4, 6 }, { 5 } }
    { { 1 }, { 2, 3, 5 }, { 4, 6 } }
    { { 1 }, { 2, 3, 6 }, { 4, 5 } }
    { { 1 }, { 2, 4, 5 }, { 3, 6 } }
    { { 1, 2 }, { 3, 4 }, { 5, 6 } }
    { { 1, 2 }, { 3, 5 }, { 4, 6 } }
For n=6, the above 8 partitions can be written as the following 3 colored bracelet structures: ABCCCC, ABBCCC, ABBBCB, ABBCBC, ABBCCB, ABCBBC, AABBCC, AABCBC. - _Andrew Howroyd_, Sep 22 2019

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.
Mohammad Hadi Shekarriz, GAP Program

Column k=2 appears to be A011948.
Columns k=3..4 are A328038, A328039.
Row sums are A328035.
Cf. A107424, A152175, A152176, A276543, A276544, A285012, A285037, A309748, A309785.

\\ 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(A=Ach(n), M=R(n), S=matrix(n, n, n, k, stirling(n, k, 2))); Mat(vectorv(n, n, sumdiv(n, d, moebius(d)*(M[n/d,] + A[n/d,])/2 - moebius(d)*(S[(n/d+1)\2, ] + S[n/d\2+1, ] + if((n-d)%2, A[(n/d+1)\2, ] + A[n/d\2+1, ]))/if(d%2, 2, 1) )))}
{ my(A=T(12)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Oct 02 2019

T(n,k) = A276543(n,k) - A285037(n,k). - Andrew Howroyd, Sep 20 2019

T(10,6) corrected by Mohammad Hadi Shekarriz, Sep 28 2019

a(56)-a(78) from Andrew Howroyd, Sep 28 2019

A007179 Dual pairs of integrals arising from reflection coefficients.

Original entry on oeis.org

0, 1, 1, 4, 6, 16, 28, 64, 120, 256, 496, 1024, 2016, 4096, 8128, 16384, 32640, 65536, 130816, 262144, 523776, 1048576, 2096128, 4194304, 8386560, 16777216, 33550336, 67108864, 134209536, 268435456, 536854528, 1073741824, 2147450880, 4294967296, 8589869056

Offset: 0

N. J. A. Sloane, Simon Plouffe

			From _Gus Wiseman_, Feb 26 2022: (Start)
Also the number of integer compositions of n with at least one odd part. For example, the a(1) = 1 through a(5) = 16 compositions are:
  (1)  (1,1)  (3)      (1,3)      (5)
              (1,2)    (3,1)      (1,4)
              (2,1)    (1,1,2)    (2,3)
              (1,1,1)  (1,2,1)    (3,2)
                       (2,1,1)    (4,1)
                       (1,1,1,1)  (1,1,3)
                                  (1,2,2)
                                  (1,3,1)
                                  (2,1,2)
                                  (2,2,1)
                                  (3,1,1)
                                  (1,1,1,2)
                                  (1,1,2,1)
                                  (1,2,1,1)
                                  (2,1,1,1)
                                  (1,1,1,1,1)
(End)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
J. Heading, Theorem relating to the development of a reflection coefficient in terms of a small parameter, J. Phys. A 14 (1981), 357-367.
Kyu-Hwan Lee, Se-jin Oh, Catalan triangle numbers and binomial coefficients, arXiv:1601.06685 [math.CO], 2016.
A. Yajima, How to calculate the number of stereoisomers of inositol-homologs, Bull. Chem. Soc. Jpn. 2014, 87, 1260-1264 | doi:10.1246/bcsj.20140204. See Tables 1 and 2 (and text). - _N. J. A. Sloane_, Mar 26 2015
Index entries for linear recurrences with constant coefficients, signature (2,2,-4).

Column k=2 of A309748.
Odd bisection is A000302.
Even bisection is A006516 = 2^(n-1)*(2^n - 1).
The complement is counted by A077957, internal version A027383.
The internal case is A274230, even bisection A134057.
A000045(n-1) counts compositions without odd parts, non-singleton A077896.
A003242 counts Carlitz compositions.
A011782 counts compositions.
A034871, A097805, and A345197 count compositions by alternating sum.
A052952 (or A074331) counts non-singleton compositions without even parts.
Cf. A000918, A033484, A052955, A060867, A116406, A138364.

[Floor(2^n/2-2^(n/2)*(1+(-1)^n)/4): n in [0..40]]; // Vincenzo Librandi, Aug 20 2011

f := n-> if n mod 2 = 0 then 2^(n-1)-2^((n-2)/2) else 2^(n-1); fi;

LinearRecurrence[{2,2,-4},{0,1,1},30] (* Harvey P. Dale, Nov 30 2015 *)
Table[2^(n-1)-If[EvenQ[n],2^(n/2-1),0],{n,0,15}] (* Gus Wiseman, Feb 26 2022 *)

Vec(x*(1-x)/((1-2*x)*(1-2*x^2)) + O(x^50)) \\ Michel Marcus, Jan 28 2016

From Paul Barry, Apr 28 2004: (Start)
  Binomial transform is (A000244(n)+A001333(n))/2.
  G.f.: x*(1-x)/((1-2*x)*(1-2*x^2)).
  a(n) = 2*a(n-1)+2*a(n-2)-4*a(n-3).
  a(n) = 2^n/2-2^(n/2)*(1+(-1)^n)/4. (End)
G.f.: (1+x*Q(0))*x/(1-x), where Q(k)= 1 - 1/(2^k - 2*x*2^(2*k)/(2*x*2^k - 1/(1 + 1/(2*2^k - 8*x*2^(2*k)/(4*x*2^k + 1/Q(k+1)))))); (continued fraction). - Sergei N. Gladkovskii, May 22 2013
a(n) = A011782(n+2) - A077957(n) - Gus Wiseman, Feb 26 2022

A309635 The number of non-equivalent distinguishing coloring partitions of the path on n vertices (n>=1) with at most k parts (k>=1). Square array read by descending antidiagonals: the rows are indexed by n, the number of vertices of the path, and the columns are indexed by k, the number of parts.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 4, 0, 1, 1, 2, 8, 6, 0, 1, 1, 2, 9, 20, 16, 0, 1, 1, 2, 9, 26, 65, 28, 0, 1, 1, 2, 9, 27, 102, 182, 64, 0, 1, 1, 2, 9, 27, 111, 364, 560, 120, 0, 1, 1, 2, 9, 27, 112, 440, 1436, 1640, 256, 0

Offset: 1

Mohammad Hadi Shekarriz, Aug 13 2019

A vertex-coloring of a graph G is called distinguishing if it is only preserved by the identity automorphism of G. This notion is considered in the subject of symmetry breaking of simple (finite or infinite) graphs. A distinguishing coloring partition of a graph G is a partition of the vertices of G such that it induces a distinguishing coloring for G. We say two distinguishing coloring partitions P1 and P2 of G are equivalent if there is a nontrivial automorphism of G which maps P1 onto P2. Given a graph G, we use the notation Psi_k(G) to denote the number of non-equivalent distinguishing coloring partitions of G with at most k parts. This sequence gives A(n,k) = Psi_k(P_n), i.e., the number of non-equivalent distinguishing coloring partitions of the path P_n on n vertices with at most k parts.

Note that, for any graph G, Psi_k(G) = Sum_{i<=k} psi_i(G), where psi_i(G) is the number of non-equivalent distinguishing coloring partitions of G with exactly i parts. For instance, here we have T(n,k) = Sum_{i<=k} A309748(n,i).

			Table begins:
  ======================================================================
  n\k| 1    2     3      4      5      6      7      8      9     10
  ---+------------------------------------------------------------------
   1 | 1,   1,    1,     1,     1,     1,     1,     1,     1,     1 ...
   2 | 0,   1,    1,     1,     1,     1,     1,     1,     1,     1 ...
   3 | 0,   1,    2,     2,     2,     2,     2,     2,     2,     2 ...
   4 | 0,   4,    8,     9,     9,     9,     9,     9,     9,     9 ...
   5 | 0,   6,   20,    26,    27,    27,    27,    27,    27,    27 ...
   6 | 0,  16,   65,   102,   111,   112,   112,   112,   112,   112 ...
   7 | 0,  28,  182,   364,   440,   452,   453,   453,   453,   453 ...
   8 | 0,  64,  560,  1436,  1978,  2120,  2136,  2137,  2137,  2137 ...
   9 | 0, 120, 1640,  5560,  9082, 10428, 10670, 10690, 10691, 10691 ...
  10 | 0, 256, 4961, 22136, 43528, 55039, 58019, 58409, 58434, 58435 ...
  ...
For n=4, we can partition the vertices of P_4 into at most 3 parts in 8 ways such that all these partitions induce distinguishing colorings for P_4 and that all the 8 partitions are non-equivalent. The partitions are as follows:
    { { 1 }, { 2 }, { 3, 4 } }
    { { 1 }, { 2, 3 }, { 4 } }
    { { 1 }, { 2, 4 }, { 3 } }
    { { 1, 4 }, { 2 }, { 3 } }
    { { 1 }, { 2, 3, 4 } }
    { { 1, 2 }, { 3, 4 } }
    { { 1, 2, 4 }, { 3 } }
    { { 1, 3 }, { 2, 4 } }

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

Column k=2 is A007179(n > 1).

Cf. A284949, A309748.

T(n, k) = Sum_{i=1..k} A309748(n,i).

A327610 Number of length n reversible string structures that are not palindromic using exactly three different colors.

Original entry on oeis.org

0, 0, 1, 4, 14, 49, 154, 496, 1520, 4705, 14266, 43384, 130844, 394849, 1187614, 3571936, 10729040, 32222785, 96724306, 290313064, 871172324, 2614069249, 7843168774, 23531688976, 70598997560, 211805640865, 635432906746, 1906333059544, 5719063904204

Offset: 1

Andrew Howroyd, Sep 18 2019

Andrew Howroyd, Table of n, a(n) for n = 1..200
Index entries for linear recurrences with constant coefficients, signature (6,-6,-24,49,6,-66,36).

Column k=3 of A309748.

Cf. A000392, A056327, A284949, A327611.

concat([0,0], Vec((1 - 2*x - 4*x^2 + 13*x^3 - 9*x^4)/((1 - x)*(1 - 2*x)*(1 - 3*x)*(1 - 2*x^2)*(1 - 3*x^2)) + O(x^30)))

a(n) = A056327 - A000392(ceiling(n/2)).
a(n) = 6*a(n-1) - 6*a(n-2) - 24*a(n-3) + 49*a(n-4) + 6*a(n-5) - 66*a(n-6) + 36*a(n-7) for n > 7.
G.f.: x^3*(1 - 2*x - 4*x^2 + 13*x^3 - 9*x^4)/((1 - x)*(1 - 2*x)*(1 - 3*x)*(1 - 2*x^2)*(1 - 3*x^2)).

A327611 Number of length n reversible string structures that are not palindromic using exactly four different colors.

Original entry on oeis.org

0, 0, 0, 1, 6, 37, 182, 876, 3920, 17175, 73030, 306296, 1266916, 5198207, 21180642, 85909216, 347179440, 1399443775, 5629876910, 22616222616, 90754709276, 363889980927, 1458171985402, 5840531023856, 23385647663560, 93613189390175, 374664530448390

Offset: 1

Andrew Howroyd, Sep 18 2019

Andrew Howroyd, Table of n, a(n) for n = 1..200
Index entries for linear recurrences with constant coefficients, signature (8,-10,-60,145,100,-470,120,456,-288).

Column k=4 of A309748.

Cf. A000453, A056328, A284949, A327610.

concat([0,0,0], Vec((1 - 2*x - x^2 + 6*x^3 + 5*x^4 - 18*x^5)/((1 - x)*(1 - 2*x)*(1 + 2*x)*(1 - 3*x)*(1 - 4*x)*(1 - 2*x^2)*(1 - 3*x^2)) + O(x^30))) \\ Andrew Howroyd, Sep 18 2019

a(n) = A056328(n) - A000453(ceiling(n/2), 4).
a(n) = 8*a(n-1) - 10*a(n-2) - 60*a(n-3) + 145*a(n-4) + 100*a(n-5) - 470*a(n-6) + 120*a(n-7) + 456*a(n-8) - 288*a(n-9) for n > 9.
G.f.: x^4*(1 - 2*x - x^2 + 6*x^3 + 5*x^4 - 18*x^5)/((1 - x)*(1 - 2*x)*(1 + 2*x)*(1 - 3*x)*(1 - 4*x)*(1 - 2*x^2)*(1 - 3*x^2)).

A327612 Number of length n reversible string structures that are not palindromic using any number of colors.

Original entry on oeis.org

0, 1, 2, 9, 27, 112, 453, 2137, 10691, 58435, 340187, 2110016, 13829358, 95474679, 691538954, 5240280999, 41432965441, 341040295916, 2916376121375, 25862097370783, 237434958512487, 2253358056604465, 22076003464423853, 222979436686398848, 2319295172150784296

Offset: 1

Andrew Howroyd, Sep 18 2019

nonn

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

Row sums of A309748(n > 1).

Cf. A103293, A188164, A304972.

\\ Ach is A304972 as square matrix.
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}
seq(n)={my(A=Ach(n)); vector(n, i, sum(k=1, n, (A[i,k] + stirling(i, k, 2))/2 - stirling((i+1)\2, k, 2)))}

a(n) = A103293(n + 1) - A188164(n).

cp's OEIS Frontend

A309784 T(n,k) is the number of non-equivalent distinguishing coloring partitions of the cycle on n vertices with exactly k parts. Regular triangle read by rows, n >= 1, 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A007179 Dual pairs of integrals arising from reflection coefficients.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A309635 The number of non-equivalent distinguishing coloring partitions of the path on n vertices (n>=1) with at most k parts (k>=1). Square array read by descending antidiagonals: the rows are indexed by n, the number of vertices of the path, and the columns are indexed by k, the number of parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A327610 Number of length n reversible string structures that are not palindromic using exactly three different colors.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A327611 Number of length n reversible string structures that are not palindromic using exactly four different colors.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A327612 Number of length n reversible string structures that are not palindromic using any number of colors.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula