Peter J. Cameron - cp's OEIS frontend

A376766 a(n) = 1 + Sum_{k=1..n, j=1..k} binomial(n,k)binomial(n,j)|Stirling_1(k,j)|*j!.

1, 2, 9, 67, 709, 9766, 165751, 3342081, 78023905, 2069303986, 61440372701, 2018742611535, 72713594116285, 2848845086153782, 120610707912196867, 5486918880456879061, 266925386719765703169, 13827085272988988990146, 759855686741314297312177, 44152359275709028329389627

Offset: 0

Peter J. Cameron, Nov 03 2024

nonn

If Stirling_1 in the definition is changed to Stirling_2, we get A000169.

Paolo Xausa, Table of n, a(n) for n = 0..375

Cf. A000169, A000312, A002720, A007840, A376765.

A376766 := proc(n) local k,j;
1 + sum(sum(binomial(n,k)*binomial(n,j)*abs(stirling1(k,j))*j!,j=1..k),k=1..n);
end; # N. J. A. Sloane, Nov 03 2024

A376766[n_] := 1 + Sum[Binomial[n, k]*Binomial[n, j]*Abs[StirlingS1[k, j]]*j!, {k, n}, {j, k}];
Array[A376766, 25, 0] (* Paolo Xausa, Nov 04 2024 *)

a(n) ~ c * d^n * n^n / exp(n), where d = A226572 = -LambertW(-1, -exp(-2)) and c = 1.350274261169912007066341887216772613236351893372220769387... - Vaclav Kotesovec, Nov 09 2024

Definition corrected by N. J. A. Sloane, Nov 09 2024

A359367 a(n) = number of regular polytopes of rank m-n with group S_m, up to isomorphism and duality (this is independent of m if m >= 2n+3).

Original entry on oeis.org

1, 1, 7, 9, 35, 48, 135

Offset: 1

Peter J. Cameron, Dec 28 2022

Also known as string C-groups for S_m.

			a(1)=1 since the only regular polytope of rank m-1 with group S_m is the simplex.

Peter J. Cameron, Maria Elisa Fernandes and Dimitri Leemans, The number of string C-groups of high rank, arXiv:2212.12723 [math.GR], 2022.
Dimitri Leemans and Jessica Mulpas, Two gluing methods for string C-group representations of the symmetric groups, arXiv:2504.17535 [math.CO], 2025. See p. 14.

a(7) from Peter J. Cameron, Jan 19 2023

A248905 Array read by antidiagonals: the number of automata over an n-letter alphabet whose states are determined by the last k symbols read.

Original entry on oeis.org

1, 1, 2, 1, 5, 5, 1, 30, 192, 15, 1, 1247

Offset: 1

Collin Bleak and Peter J. Cameron, Mar 06 2015

T(n,k) is the number of automata over an n-letter alphabet whose states are determined by the last k symbols read. These therefore correspond to a count of a special class of synchronized automata as in the Road Coloring Problem solved by Trahtman.

Also, T(n,k) counts equivalence relations on de Bruijn graphs compatible with edge labels.

			Below is the table T(n,k) for row n = alphabet size, and column k = synchronizing word length. Top left entry is T(1,1).
1   1     1      1      1     1   ...
2   5     30     1247   ?
5   192   ?      ?
15  98721 ?
203 ?
.
.
.

Collin Bleak, Table of a(n,k) listed as antidiagonal ordered sequence in index m = 1..15.
Collin Bleak, Peter J. Cameron, and Feyishayo Olukoya, Automorphisms of shift spaces and the Higman-Thomspon groups: the one-sided case, arXiv:2004.08478 [math.GR], 2020.
Avraham N. Trahtman, The Road Coloring Problem, arXiv:0709.0099 [cs.DM], 2007.
Avraham N. Trahtman, The Road Coloring Problem, Israel Journal of Mathematics, 172 (2009), 51-60.

Cf. A000110 (first column).

T(n,1) = A000110(n).

A244972 Orders of primitive groups not synchronizing a rank 3 map.

Original entry on oeis.org

3, 9, 21, 27, 45, 81, 153, 243, 441, 495, 729

Offset: 1

Peter J. Cameron, Nov 12 2014

Also, orders of graphs with clique number and chromatic number 3 which have primitive automorphism groups.

			The graphs on 3^n vertices are the Hamming graphs over 3-letter alphabet; the graphs with 21, 45 and 153 vertices are the line graphs of the 6-cage, 8-cage, and Biggs-Smith graph respectively.

A112578 Number of indecomposable 3-D arrays of 0's and 1's with plane sums 2.

Original entry on oeis.org

0, 8, 900, 359424, 370828800, 820150272000, 3435918974208000, 24957654229057536000, 294060698786444083200000, 5334667831784096818790400000, 42889554205720574193041408000000

Offset: 1

Peter J. Cameron, Sep 14 2005

			a(2)=8: six pairs of opposite edges and two inscribed tetrahedra.

P. J. Cameron and T. W. Mueller, Decomposable functors and the exponential principle, II, in preparation

P. J. Cameron and T. W. Mueller, Decomposable functors and the exponential principle, II, arXiv:0911.3760 [math.CO]

Cf. A010796 (2-D case), A112579, A112580.

a(1)=0, a(n) = (n!)^2*b(n)/2^n for n>1, where b(0)=1 and sum (n-1 choose k-1)*((2n-2k-1)!!)^2*b(k) = ((2n-1)!!)^2.

A112579 Number of 3-D arrays of 0's and 1's with plane sums 2.

Original entry on oeis.org

0, 8, 900, 366336, 378028800, 833156928000, 3477528928742400, 25183876050321408000, 296058177312000019660800, 5362158372805111867637760000, 143458227395428379364635443200000

Offset: 1

Peter J. Cameron, Sep 14 2005

			a(2)=8: six pairs of opposite edges and two inscribed tetrahedra.

P. J. Cameron and T. W. Mueller, Decomposable functors and the exponential principle, II, in preparation

P. J. Cameron and T. W. Mueller, Decomposable functors and the exponential principle, II, arXiv:0911.3760 [math.CO]

Cf. A001499 (2-D case), A112578, A112580.

a(n) = b(n) + Sum (k/n)*(n choose k)^3*b(k)*a(n-k), where b(n) counts indecomposable arrays (A112578).

A112580 Number of 3-D arrays of nonnegative integers with plane sums 2.

Original entry on oeis.org

1, 12, 1152, 431424, 427723200, 920031955200, 3777894212198400, 27039993414897254400, 315084437077115278540800, 5667616936309704095784960000, 150796432741520745587273564160000

Offset: 1

Peter J. Cameron, Sep 14 2005

			a(2)=12: eight 0-1 arrays and four with 2s at opposite vertices.

P. J. Cameron and T. W. Mueller, Decomposable functors and the exponential principle, II, in preparation

P. J. Cameron and T. W. Mueller, Decomposable functors and the exponential principle, II, arXiv:0911.3760 [math.CO]

Cf. A001499 (2-D case), A112578, A112579.

a(n) = b(n) + Sum (k/n)*(n choose k)^3*b(k)*a(n-k), where b(n) counts indecomposable arrays (A112578 with first term 1).

A101370 Number of zero-one matrices with n ones and no zero rows or columns.

Original entry on oeis.org

1, 4, 24, 196, 2016, 24976, 361792, 5997872, 111969552, 2324081728, 53089540992, 1323476327488, 35752797376128, 1040367629940352, 32441861122796672, 1079239231677587264, 38151510015777089280, 1428149538870997774080, 56435732691153773665280

Offset: 1

Peter J. Cameron, Jan 14 2005

a(n) = (1/(4*n!)) * Sum_{r, s>=0} (r*s)_n / 2^(r+s), where (m)_n is the falling factorial m * (m-1) * ... * (m-n+1). [Maia and Mendez]

			a(2)=4:
[1 1] [1] [1 0] [0 1]
..... [1] [0 1] [1 0]
From _Gus Wiseman_, Nov 14 2018: (Start)
The a(3) = 24 matrices:
  [111]
.
  [11][11][110][101][10][100][011][01][010][001]
  [10][01][001][010][11][011][100][11][101][110]
.
  [1][10][10][10][100][100][01][01][010][01][010][001][001]
  [1][10][01][01][010][001][10][10][100][01][001][100][010]
  [1][01][10][01][001][010][10][01][001][10][100][010][100]
(End)

Georg Cantor, Gesammelte Abhandlungen mathematischen und philosophischen Inhalts, p. 435 (IV, 4. Mitteilungen zur Lehre vom Transfiniten, VIII Nr. 13), Springer, Berlin. [Rainer Rosenthal, Apr 10 2007]

Alois P. Heinz, Table of n, a(n) for n = 1..400
P. J. Cameron, D. A. Gewurz and F. Merola, Product action, Discrete Math., 308 (2008), 386-394.
Giulio Cerbai and Anders Claesson, Enumerative aspects of Caylerian polynomials, arXiv:2411.08426 [math.CO], 2024. See pp. 3, 19.
Loïc Foissy, Claudia Malvenuto, and Frédéric Patras, Matrix symmetric and quasi-symmetric functions and noncommutative representation theory, arXiv:2503.14417 [math.CO], 2025. See p. 20.
M. Maia and M. Mendez, On the arithmetic product of combinatorial species, arXiv:math/0503436 [math.CO], 2005.

Cf. A000670 (the sequence P(n)), A049311 (row and column permutations allowed), A120733, A122725, A135589, A283877, A321446, A321587.

P:=function(n) return Sum([1..n],x->Stirling2(n,x)*Factorial(x)); end;

F:=function(n) return Sum([1..n],x->(-1)^(n-x)*Stirling1(n,x)*P(x)^2)/Factorial(n); end;

m = 17; a670[n_] = Sum[ StirlingS2[n, k]*k!, {k, 0, n}]; Rest[ CoefficientList[ Series[ Sum[ a670[n]^2*(Log[1 + x]^n/n!), {n, 0, m}], {x, 0, m}], x]] (* Jean-François Alcover, Sep 02 2011, after g.f.  *)
Table[Length[Select[Subsets[Tuples[Range[n],2],{n}],And[Union[First/@#]==Range[Max@@First/@#],Union[Last/@#]==Range[Max@@Last/@#]]&]],{n,5}] (* Gus Wiseman, Nov 14 2018 *)

{A000670(n)=sum(k=0,n,stirling(n, k,2)*k!)}
{a(n)=polcoeff(sum(m=0,n,A000670(m)^2*log(1+x+x*O(x^n))^m/m!),n)}
/* Paul D. Hanna, Nov 07 2009 */

a(n) = (Sum s(n, k) * P(k)^2)/n!, where P(n) is the number of labeled total preorders on {1, ..., n} (A000670), s are signed Stirling numbers of the first kind.
G.f.: Sum_{m>=0,n>=0} Sum_{j=0..n} (-1)^(n-j)*binomial(n,j)*((1+x)^j-1)^m. - Vladeta Jovovic, Mar 25 2006
Inverse binomial transform of A007322. - Vladeta Jovovic, Aug 17 2006
G.f.: Sum_{n>=0} 1/(2-(1+x)^n)/2^(n+1). - Vladeta Jovovic, Sep 23 2006
G.f.: Sum_{n>=0} A000670(n)^2*log(1+x)^n/n! where 1/(1-x) = Sum_{n>=0} A000670(n)*log(1+x)^n/n!. - Paul D. Hanna, Nov 07 2009
a(n) ~ n! / (2^(2+log(2)/2) * (log(2))^(2*(n+1))). - Vaclav Kotesovec, Dec 31 2013

A049313 Switching classes of tournaments on n nodes.

Original entry on oeis.org

1, 1, 1, 2, 2, 6, 12, 79, 792, 19576, 886288, 75369960, 11856006240, 3467430423264, 1893448825054528, 1938818712501985736, 3737086626658278741376, 13606268915761294708760704, 93863103860384959101157737728

Offset: 1

Peter J. Cameron

			a(4)=2: the "local orders" form one switching class and the class containing a 3-cycle dominating a point the other.

L. Babai and P. J. Cameron, Automorphisms and enumeration of switching classes of tournaments, Electron. J. Combin., 7 (2000), no. 1, Research Paper 38, 25 pp.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

Cf. A002854.

Same as for switching classes of graphs but summed only over "level" permutations (same power of 2 divides all cycle lengths)

More terms from Vladeta Jovovic, Mar 01 2000

A049311 Number of (0,1) matrices with n ones and no zero rows or columns, up to row and column permutations.

Original entry on oeis.org

1, 3, 6, 16, 34, 90, 211, 558, 1430, 3908, 10725, 30825, 90156, 273234, 848355, 2714399, 8909057, 30042866, 103859678, 368075596, 1335537312, 4958599228, 18820993913, 72980867400, 288885080660, 1166541823566, 4802259167367, 20141650236664

Offset: 1

Peter J. Cameron

Also the number of bipartite graphs with n edges, no isolated vertices and a distinguished bipartite block, up to isomorphism.
The EULERi transform (A056156) is also interesting.
a(n) is also the number of non-isomorphic set multipartitions (multisets of sets) of weight n. - Gus Wiseman, Mar 17 2017

			E.g. a(2) = 3: two ones in same row, two ones in same column, or neither.
a(3) = 6 is coefficient of x^3 in (1/36)*((1 + x)^9 + 6*(1 + x)^3*(1 + x^2)^3 + 8*(1 + x^3)^3 + 9*(1 + x)*(1 + x^2)^4 + 12*(1 + x^3)*(1 + x^6))=1 + x + 3*x^2 + 6*x^3 + 7*x^4 + 7*x^5 + 6*x^6 + 3*x^7 + x^8 + x^9.
There are a(3) = 6 binary matrices with 3 ones, with no zero rows or columns, up to row and column permutation:
  [1 0 0] [1 1 0] [1 0] [1 1] [1 1 1] [1]
  [0 1 0] [0 0 1] [1 0] [1 0] ....... [1].
  [0 0 1] ....... [0 1] ............. [1]
Non-isomorphic representatives of the a(3)=6 set multipartitions are: ((123)), ((1)(23)), ((2)(12)), ((1)(1)(1)), ((1)(2)(2)), ((1)(2)(3)). - _Gus Wiseman_, Mar 17 2017

Aliaksandr Siarhei, Table of n, a(n) for n = 1..102
Peter J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Peter J. Cameron, D. A. Gewurz and F. Merola, Product action, Discrete Math., 308 (2008), 386-394.
Peter J. Cameron, Problems on Permutation Groups, see Problem 3
Index entries for sequences related to binary matrices.

Main diagonal of A321609.
Cf. A049312, A048194, A028657, A055192, A055599, A052371, A052370, A053304, A053305, A007716, A002724.
Cf. A057149, A057150, A057151, A057152.
Cf. A034691, A056156, A089259, A116540, A283877.

WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v,n,(-1)^(n-1)/n))))-1,-#v)}
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
K(q, t, k)={WeighT(Vec(sum(j=1, #q, gcd(t, q[j])*x^lcm(t, q[j])) + O(x*x^k), -k))}
a(n)={my(s=0); forpart(q=n, s+=permcount(q)*polcoef(exp(x*Ser(sum(t=1, n, K(q, t, n)/t))), n)); s/n!} \\ Andrew Howroyd, Jan 16 2023

Calculate number of connected bipartite graphs + number of connected bipartite graphs with no duality automorphism, then apply EULER transform.

a(n) is the coefficient of x^n in the cycle index Z(S_n X S_n; 1+x, 1+x^2, ...), where S_n X S_n is Cartesian product of symmetric groups S_n of degree n.

More terms and formula from Vladeta Jovovic, Jul 29 2000
a(19)-a(28) from Max Alekseyev, Jul 22 2009
a(29)-a(102) from Aliaksandr Siarhei, Dec 13 2013
Name edited by Gus Wiseman, Dec 18 2018

cp's OEIS Frontend

User: Peter J. Cameron

A376766 a(n) = 1 + Sum_{k=1..n, j=1..k} binomial(n,k)*binomial(n,j)*|Stirling_1(k,j)|*j!.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A359367 a(n) = number of regular polytopes of rank m-n with group S_m, up to isomorphism and duality (this is independent of m if m >= 2n+3).

Views

Author

Keywords

Comments

Examples

Links

Extensions

A248905 Array read by antidiagonals: the number of automata over an n-letter alphabet whose states are determined by the last k symbols read.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A244972 Orders of primitive groups not synchronizing a rank 3 map.

Views

Author

Keywords

Comments

Examples

A112578 Number of indecomposable 3-D arrays of 0's and 1's with plane sums 2.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Formula

A112579 Number of 3-D arrays of 0's and 1's with plane sums 2.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Formula

A112580 Number of 3-D arrays of nonnegative integers with plane sums 2.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Formula

A101370 Number of zero-one matrices with n ones and no zero rows or columns.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

GAP

Mathematica

PARI

Formula

A049313 Switching classes of tournaments on n nodes.

A376766 a(n) = 1 + Sum_{k=1..n, j=1..k} binomial(n,k)binomial(n,j)|Stirling_1(k,j)|*j!.