A008610 -id:A008610 - cp's OEIS frontend

A054771 Number of nonnegative integer 3 X 3 matrices with sum of elements equal to n, up to rotational symmetry.

1, 3, 13, 43, 129, 327, 761, 1619, 3238, 6098, 10974, 18930, 31550, 50930, 80030, 122666, 183999, 270525, 390755, 555205, 777287, 1073297, 1463583, 1972533, 2630044, 3471508, 4539660, 5884564, 7565868, 9652788, 12226860, 15381924

Offset: 0

Vladeta Jovovic, May 18 2000

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Row n=3 of A343874.

Cf. A008610, A054343.

G.f.: (x^8 - 2*x^7 + 6*x^6 + 2*x^5 + 2*x^4 + 2*x^3 + 6*x^2 - 2*x + 1)/((1 - x^4)^2*(1 - x^2)^2*(1 - x)^5).

A054773 Number of nonnegative integer 4 X 4 matrices with sum of elements equal to n, up to rotational symmetry.

Original entry on oeis.org

1, 4, 36, 204, 980, 3876, 13596, 42636, 122666, 326876, 817388, 1931540, 4346404, 9360540, 19390548, 38779380, 75136675, 141430680, 259292440, 463991880, 811990680, 1391975640, 2341057896, 3867821640, 6285222804, 10056336264

Offset: 0

Vladeta Jovovic, May 19 2000

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Row n=4 of A343874.

Cf. A008610.

G.f.: (x^16 - 4*x^15 + 28*x^14 - 12*x^13 + 76*x^12 + 60*x^11 + 196*x^10 - 44*x^9 + 422*x^8 - 44*x^7 + 196*x^6 + 60*x^5 + 76*x^4 - 12*x^3 + 28*x^2 - 4*x + 1)/ ((x - 1)^16*(x + 1)^8*(x^2 + 1)^4).

A032195 Number of necklaces with 10 black beads and n-10 white beads.

Original entry on oeis.org

1, 1, 6, 22, 73, 201, 504, 1144, 2438, 4862, 9252, 16796, 29414, 49742, 81752, 130752, 204347, 312455, 468754, 690690, 1001603, 1430715, 2016144, 2804880, 3856892, 5245128, 7060984, 9414328, 12440668, 16301164

Offset: 10

Christian G. Bower

nonn

The g.f. is Z(C_10,x)/x^10, the 10-variate cycle index polynomial for the cyclic group C_10, with substitution x[i]->1/(1-x^i), i=1,...,10. By Polya enumeration, a(n+10) is the number of cyclically inequivalent 10-necklaces whose 10 beads are labeled with nonnegative integers such that the sum of labels is n, for n=0,1,2,... See A102190 for Z(C_10,x). See the comment in A032191 on the equivalence of this problem with the one given in the `Name' line. - Wolfdieter Lang, Feb 15 2005

C. G. Bower, Transforms (2)
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
Index entries for sequences related to necklaces
Index entries for linear recurrences with constant coefficients, signature (4,-2,-12,17,9,-32,10,29,-29,-9,28,-7,-5,-5,-7,28,-9,-29,29,10,-32,9,17,-12,-2,4,-1).

Column k=10 of A047996.

Cf. A004526, A007997, A008610, A008646, A032191, A032192, A032193, A032194.

k = 10; Table[Apply[Plus, Map[EulerPhi[ # ]Binomial[n/#, k/# ] &, Divisors[GCD[n, k]]]]/n, {n, k, 30}] (* Robert A. Russell, Sep 27 2004 *)

"CIK[ 10 ]" (necklace, indistinct, unlabeled, 10 parts) transform of 1, 1, 1, 1...
G.f.: (x^10)*(1-3*x+4*x^2+12*x^3-8*x^4-x^5+31*x^6-4*x^8+16*x^9 +11*x^10 +3*x^11+8*x^12+4*x^13+4*x^14+x^15+x^16) /((1-x)^4*(1-x^2)^4 *(1-x^5)*(1-x^10)).
G.f.: (1/10)*x^10*(1/(1 - x)^10 + 1/(1 - x^2)^5 + 4/(1 - x^5)^2 + 4/(1 - x^10)^1). - Herbert Kociemba, Oct 22 2016

A032196 Number of necklaces with 11 black beads and n-11 white beads.

Original entry on oeis.org

1, 1, 6, 26, 91, 273, 728, 1768, 3978, 8398, 16796, 32066, 58786, 104006, 178296, 297160, 482885, 766935, 1193010, 1820910, 2731365, 4032015, 5864750, 8414640, 11920740, 16689036, 23107896, 31666376, 42975796

Offset: 11

Christian G. Bower

nonn

The g.f. is Z(C_11,x)/x^11, the 11-variate cycle index polynomial for the cyclic group C_11, with substitution x[i]->1/(1-x^i), i=1..11. By Polya enumeration, a(n+11) is the number of cyclically inequivalent 11-necklaces whose 11 beads are labeled with nonnegative integers such that the sum of labels is n, for n=0,1,2,... See A102190 for Z(C_11,x). See the comment in A032191 on the equivalence of this problem with the one given in the `Name' line. - Wolfdieter Lang, Feb 15 2005

C. G. Bower, Transforms (2)
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
Index entries for sequences related to necklaces
Index entries for linear recurrences with constant coefficients, signature (10,-45,120,-210,252,-210,120,-45,10,-1,1,-10,45,-120,210,-252,210,-120,45,-10,1).

Column k=11 of A047996.

Cf. A004526, A007997, A008610, A008646, A032191, A032192, A032193, A032194, A032195.

k = 11; Table[Apply[Plus, Map[EulerPhi[ # ]Binomial[n/#, k/# ] &, Divisors[GCD[n, k]]]]/n, {n, k, 30}] (* Robert A. Russell, Sep 27 2004 *)
DeleteCases[CoefficientList[Series[(x^11) (1 - 9 x + 41 x^2 - 109 x^3 + 191 x^4 - 229 x^5 + 191 x^6 - 109 x^7 + 41 x^8 - 9 x^9 + x^10)/((1 - x)^10 (1 - x^11)), {x, 0, 39}], x], 0] (* Michael De Vlieger, Oct 10 2016 *)

"CIK[ 11 ]" (necklace, indistinct, unlabeled, 11 parts) transform of 1, 1, 1, 1...
G.f.: (x^11) * (1 - 9*x + 41*x^2 - 109*x^3 + 191*x^4 - 229*x^5 + 191*x^6 - 109*x^7 + 41*x^8 - 9*x^9 + x^10) / ((1-x)^10 * (1-x^11)).
a(n) = ceiling(binomial(n, 11)/n) (conjecture Wolfdieter Lang).
From Herbert Kociemba, Oct 11 2016: (Start)
This conjecture indeed is true.
Sketch of proof:
There are binomial(n,11) ways to place the 11 black beads in the necklace with n beads. If n is not divisible by 11 there are no necklaces with a rotational symmetry. So exactly n necklaces are equivalent up to rotation and there are binomial(n,11)/n = ceiling(binomial(n,11)/n) equivalence classes.
If n is divisible by 11 the only way to get a necklace with rotational symmetry is to space out the 11 black beads evenly. There are n/11 ways to do this and all ways are equivalent up to rotation. So there are  binomial(n,11) - n/11 unsymmetric necklaces which give binomial(n,11)/n - 1/11 equivalence classes. If we add the single symmetric equivalence class we get Binomial(n,11)/n - 1/11 + 1 which also is ceiling(binomial(n,11)/n). (End)
G.f.: (10/(1 - x^11) + 1/(1 - x)^11)*x^11/11. - Herbert Kociemba, Oct 16 2016

A032197 Number of necklaces with 12 black beads and n-12 white beads.

Original entry on oeis.org

1, 1, 7, 31, 116, 364, 1038, 2652, 6310, 14000, 29414, 58786, 112720, 208012, 371516, 643856, 1086601, 1789515, 2883289, 4552275, 7056280, 10752060, 16128424, 23841480, 34769374, 50067108, 71250060, 100276894, 139672312

Offset: 12

Christian G. Bower

nonn

The g.f. is Z(C_12,x)/x^12, the 12-variate cycle index polynomial for the cyclic group C_12, with substitution x[i]->1/(1-x^i), i=1,...,12. Therefore by Polya enumeration a(n+12) is the number of cyclically inequivalent 12-necklaces whose 12 beads are labeled with nonnegative integers such that the sum of labels is n, for n=0,1,2,... See A102190 for Z(C_12,x). See the comment in A032191 on the equivalence of this problem with the one given in the `Name' line. - Wolfdieter Lang, Feb 15 2005

C. G. Bower, Transforms (2)
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
Index entries for sequences related to necklaces
Index entries for linear recurrences with constant coefficients, signature (4,-4,-2,4,-4,12,-12,2,2,-12,24,-18,4,4,-6,15,-20,0,10,-4,10,0,-20,15,-6,4,4,-18,24,-12,2,2,-12,12,-4,4,-2,-4,4,-1).

Column k=12 of A047996.

Cf. A004526, A007997, A008610, A008646, A032191, A032192-A032196.

k = 12; Table[Apply[Plus, Map[EulerPhi[ # ]Binomial[n/#, k/# ] &, Divisors[GCD[n, k]]]]/n, {n, k, 30}] (* Robert A. Russell, Sep 27 2004 *)

"CIK[ 12 ]" (necklace, indistinct, unlabeled, 12 parts) transform of 1, 1, 1, 1...
G.f.: (x^12)*(1-3*x+7*x^2+9*x^3+18*x^4+38*x^5+72*x^6+92*x^7+168*x^8+160*x^9+238*x^10+230*x^11+296*x^12+234*x^13+330*x^14+248*x^15+284*x^16+238*x^17+230*x^18+166*x^19+172*x^20+78*x^21+80*x^22+38*x^23+21*x^24+7*x^25+3*x^26+x^27) /((1+x)*(1-x)*(1-x^2)*(1-x^3)*(1-x)^5*(1+x+x^2)*(1-x^4)^2*(1-x^6)*(1-x^12)). - Wolfdieter Lang, Feb 15 2005 (see comment)
G.f.: 1/12 x^12 ((1 - x)^-12 + (1 - x^2)^-6 + 2 (1 - x^3)^-4 + 2 (1 - x^4)^-3 + 2 (1 - x^6)^-2 + 4 (1 - x^12)^-1). - Herbert Kociemba, Oct 22 2016

A337747 Maximal number of 4-point circles passing through n points on a plane.

Original entry on oeis.org

0, 0, 0, 1, 1, 3, 6, 12, 14, 22, 30, 45

Offset: 1

Dmitry Kamenetsky, Sep 17 2020

This is a variant of the orchard-planting problem that uses circles instead of straight lines.
The maximal number of 3-point circles passing through n points on a plane is binomial(n,3). Given an arrangement of n points in general position, any choice of three points defines a circle. - Peter Kagey, Oct 05 2020
Paul Panzer provides upper and lower bounds:
  a(n) <= floor(n*(n-1)*(n-2)/24).
  a(n) >= 2 + n*((n-2)*(n-2) + 4)/32 for n == 0 (mod 4) and n >= 8.
  a(n) >= 2 + (n-1)*((n-1)*(n-5) + 16)/32 for n == 1 (mod 4) and n >= 9.
  a(n) >= 2 + n*(n-2)*(n-2)/32 for n == 2 (mod 4) and n >= 10.
  a(n) >= 2 + (n-1)*((n-3)*(n-3) + 16)/32 for n == 3 (mod 4) and n >= 11.
It seems that a(n) = n*((n-2)*(n-2) + 4)/32 + 2*A008610(n/2-4) if n == 0 (mod 4) and n >= 8. - Zhao Hui Du, Dec 14 2022
The number of 4-point circles passing through n points (2*cos(t_k), sin(t_k)) where t_k = (2k-1)*Pi/n, k=1,2,...,n is A008610(n-4), so A337747(n) >= A008610(n-4), so A337747(n) ~ n^3/24 for sufficiently large n. - Zhao Hui Du, Dec 15 2022

			See examples in links.

Zhao Hui Du, Source code and running data to show there are at most 30 circles for 11 trees.
Zhao Hui Du, A group of solutions with 30 circles for 11 trees.
Zhao Hui Du, Geogebra dynamic graph for a group of solution to 12 trees 45 circles (4 trees per circle).
Zhao Hui Du, Best known solution for 14 trees (73 circles), removing point I from the solution to form a solution with 13 trees and 53 circles so that a(13) >= 53, a(14) >= 73.
Zhao Hui Du, Graph for 14 trees 73 circles (all black circles have same patterns as that in that in two co-center regular polygons (Paul Panzer's solution) while red circles are those extra circles).
Zhao Hui Du, Graph for 16 trees with 120 circles.
Zhao Hui Du, Geogebra graph for 16 trees with 120 circles (parameter d and m could be any real value and point PP could be moving too), removing any tree to form 15 trees with 90 circles so that a[15]>=90, a[16]>=120.
Zhao Hui Du, Chinese webpage to show that the number of 4 points circle through the n points in ellipse could be transformed to the number to pick 4 different numbers k1,k2,k3,k4 from 1 to n so that n|2+k1+k2+k3+k4, which is equal to A008610(n-4).
Dmitry Kamenetsky, Best known solutions for n <= 13.
Dmitry Kamenetsky, Orchard planting problem, Puzzling StackExchange, August 2020.
Dmitry Kamenetsky, General orchard planting problem, Puzzling StackExchange, September 2020.

Cf. A003035 (the original orchard problem), A006065.

a(11) from Zhao Hui Du, Nov 22 2022

a(12) from Zhao Hui Du, Dec 01 2022

cp's OEIS Frontend

A054771 Number of nonnegative integer 3 X 3 matrices with sum of elements equal to n, up to rotational symmetry.

Views

Author

Keywords

Links

Crossrefs

Formula

A054773 Number of nonnegative integer 4 X 4 matrices with sum of elements equal to n, up to rotational symmetry.

Views

Author

Keywords

Links

Crossrefs

Formula

A032195 Number of necklaces with 10 black beads and n-10 white beads.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A032196 Number of necklaces with 11 black beads and n-11 white beads.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A032197 Number of necklaces with 12 black beads and n-12 white beads.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A337747 Maximal number of 4-point circles passing through n points on a plane.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions