A186783 -id:A186783 - cp's OEIS frontend

A325007 Array read by descending antidiagonals: A(n,k) is the number of achiral colorings of the facets of a regular n-dimensional orthotope using up to k colors.

1, 2, 1, 3, 6, 1, 4, 18, 10, 1, 5, 40, 55, 15, 1, 6, 75, 200, 126, 21, 1, 7, 126, 560, 700, 252, 28, 1, 8, 196, 1316, 2850, 1996, 462, 36, 1, 9, 288, 2730, 9261, 11376, 5004, 792, 45, 1, 10, 405, 5160, 25480, 50127, 38550, 11440, 1287, 55, 1, 11, 550, 9075, 61776, 181027, 225225, 116160, 24310, 2002, 66, 1

Offset: 1

Robert A. Russell, May 27 2019

Also called hypercube, n-dimensional cube, and measure polytope. For n=1, the figure is a line segment with two vertices. For n=2 the figure is a square with four edges. For n=3 the figure is a cube with six square faces. For n=4, the figure is a tesseract with eight cubic facets. The Schläfli symbol, {4,3,...,3}, of the regular n-dimensional orthotope (n>1) consists of a four followed by n-2 threes. Each of its 2n facets is an (n-1)-dimensional orthotope. An achiral coloring is identical to its reflection.

Also the number of achiral colorings of the vertices of a regular n-dimensional orthoplex using up to k colors.

			Array begins with A(1,1):
1  2   3     4      5      6       7        8         9        10 ...
1  6  18    40     75    126     196      288       405       550 ...
1 10  55   200    560   1316    2730     5160      9075     15070 ...
1 15 126   700   2850   9261   25480    61776    135675    275275 ...
1 21 252  1996  11376  50127  181027   559728   1529892   3784627 ...
1 28 462  5004  38550 225225 1053304  4119648  13942908  41918800 ...
1 36 792 11440 116160 881595 5263336 25794288 107427420 390891160 ...
For a(2,2)=6, all colorings are achiral: two with just one of the colors, two with one color on just one edge, one with opposite colors the same, and one with opposite colors different.

Robert A. Russell, Table of n, a(n) for n = 1..325
Robin Chapman, answer to Coloring the faces of a hypercube, Math StackExchange, September 30, 2010.

Cf. A325004 (oriented), A325005 (unoriented), A325006 (chiral), A325011 (exactly k colors).
Other n-dimensional polytopes: A325001 (simplex), A325015 (orthoplex).
Rows 1-2 are A000027, A002411; column 2 is A186783(n+2).

Table[Binomial[Binomial[d-n+2,2]+n-1,n]-Binomial[Binomial[d-n+1,2],n],{d,1,11},{n,1,d}] // Flatten

a(n, k) = binomial(binomial(k+1, 2)+n-1, n) - binomial(binomial(k, 2), n)
array(rows, cols) = for(x=1, rows, for(y=1, cols, print1(a(x, y), ", ")); print(""))
/* Print initial 6 rows and 8 columns of array as follows: */
array(6, 8) \\ Felix Fröhlich, May 30 2019

A(n,k) = binomial(binomial(k+1,2) + n-1, n) - binomial(binomial(k,2),n).
A(n,k) = Sum_{j=1..2*n} A325011(n,j) * binomial(k,j).
A(n,k) = 2*A325005(n,k) - A325004(n,k) = (A325004(n,k) - 2*A325006(n,k)) / 2 = A325005(n,k) + A325006(n,k).
G.f. for row n: Sum{j=1..2*n} A325011(n,j) * x^j / (1-x)^(j+1).
Linear recurrence for row n: T(n,k) = Sum_{j=0..2*n} binomial(-2-j,2*n-j) * T(n,k-1-j).
G.f. for column k: 1/(1-x)^binomial(k+1,2) - (1+x)^binomial(k,2).

A039745 Diameter of symmetric group S_n when generated by (1,2) and (1,2,3,...,n).

Original entry on oeis.org

0, 1, 2, 6, 11, 18, 25, 35, 45, 58, 71, 87, 103, 122, 141

Offset: 1

David desJardins

a(n) is smallest number such that every element of S_n can be written as a product of at most a(n) terms each of which is the transposition (1,2) or the n-cycle (1,2,3,...,n).

The distinction between A039745 (this sequence) and A186783 comes from whether we treat the Cayley graph of the generating set as directed or undirected (alternatively, whether we allow multiplication by inverses of generators when constructing elements). A039745 deals with the directed Cayley graph, while A186783 deals with the undirected one. - Max Alekseyev, Sep 09 2011

			a(3)=2 because (1,3,2) = (1,2,3)(1,2).

Dmytro Fedoriaka, Growth function for n=15.

Cf. A378881 (antipodal permutations), A186144 (number of them).

Cf. A186783 (LRE diameter).

a[n_] := GraphDiameter[CayleyGraph[SymmetricGroup[n]]] (* Ben Whitmore, Nov 13 2020 *)

def a(n): return PermutationGroup([[(1,2)],[tuple(1..n)]]).cayley_graph().diameter() # Max Alekseyev, Mar 02 2010

a(12)-a(13) by Ben Whitmore, Nov 12 2020
a(14) by Dmytro Fedoriaka, Jun 30 2025
a(15) by Dmytro Fedoriaka, Jul 14 2025

A186752 Length of minimum representation of the permutation [n,n-1,...,1] as the product of transpositions (1,2) and left and right rotations (1,2,...,n).

Original entry on oeis.org

0, 1, 2, 4, 8, 13, 19, 26, 34, 43, 53, 64, 76

Offset: 1

Tony Bartoletti, Feb 26 2011

Example: Taking "0" to indicate the "left" rotation (1,2,...,n) -> (2,3,...,n,1), "1" to represent the transposition (1,2), and "2" to indicate the "right" rotation (1,2,...,n) -> (n,1,2,...n-1), the sequence 10010121 (length = 8) is a minimal sequence producing the reverse permutation on S_5.
It was suggested that a(10) = 61, but this cannot be correct. It would conflict with A186783(10)=45, the diameter of the set under these same operations. We must have a(n) <= A186783(n) for all n. - Tony Bartoletti, Mar 08 2019
Conjecture: for n>=4, a(n)=A186783(n)-2. Conjecture holds for n<=13. - Dmitry Kamenetsky, Jun 15 2025

Danilo Bazzanella, Antonio Di Scala, Simone Dutto, and Nadir Murru, Primality tests, linear recurrent sequences and the Pell equation, arXiv:2002.08062 [math.NT], 2020.
Sai Satwik Kuppili, C++ program for generating the moves for a given n
Sai Satwik Kuppili and Bhadrachalam Chitturi, An Upper Bound for Sorting R_n with LRE, arXiv:2002.07342 [cs.DS], 2020.

Cf. A378834 (number of ways), A048200 (LE reversal distance).

def a186752(n): t = tuple(1..n); G = PermutationGroup([[(1, 2)], [t], PermutationGroupElement([t])^(-1)]); return G.cayley_graph().distance(G.one(),G(list(t)[::-1])) # Max Alekseyev, Sep 09 2011

a(9) from Max Alekseyev, Sep 09 2011
Incorrect value for a(10) deleted by N. J. A. Sloane, Mar 09 2019
a(10) and a(11) added by Sai Satwik Kuppili and Bhadrachalam Chitturi, Mar 28 2019
a(12) and a(13) from Kevin Ryde, Dec 12 2024

cp's OEIS Frontend

A325007 Array read by descending antidiagonals: A(n,k) is the number of achiral colorings of the facets of a regular n-dimensional orthotope using up to k colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A039745 Diameter of symmetric group S_n when generated by (1,2) and (1,2,3,...,n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Sage

Extensions

A186752 Length of minimum representation of the permutation [n,n-1,...,1] as the product of transpositions (1,2) and left and right rotations (1,2,...,n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Sage

Extensions