A054745 -id:A054745 - cp's OEIS frontend

A001372 Number of unlabeled mappings (or mapping patterns) from n points to themselves; number of unlabeled endofunctions.

1, 1, 3, 7, 19, 47, 130, 343, 951, 2615, 7318, 20491, 57903, 163898, 466199, 1328993, 3799624, 10884049, 31241170, 89814958, 258604642, 745568756, 2152118306, 6218869389, 17988233052, 52078309200, 150899223268, 437571896993, 1269755237948, 3687025544605, 10712682919341, 31143566495273, 90587953109272, 263627037547365

Offset: 0

N. J. A. Sloane

			The a(3) = 7 mappings are:
1->1, 2->2, 3->3
1->1, 2->2, 3->1 (equiv. to 1->1, 2->2, 3->2, or 1->1, 2->1, 3->3, etc.)
1->1, 2->3, 3->2
1->1, 2->1, 3->2
1->1, 2->1, 3->1
1->2, 2->3, 3->1
1->2, 2->1, 3->1

F. Bergeron, G. Labelle, and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, pp. 41, 209.
S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.6.6.
R. A. Fisher, Contributions to Mathematical Statistics, Wiley, 1950, 41.401.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 70, Table 3.4.1.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 501 terms from Christian G. Bower)
A. L. Agore, A. Chirvasitu, and G. Militaru, The set-theoretic Yang-Baxter equation, Kimura semigroups and functional graphs, arXiv:2303.06700 [math.QA], 2023.
N. G. de Bruijn, Enumeration of mapping patterns, J. Combin. Theory, 12 (1972), 14-20.
N. G. de Bruijn and D. A. Klarner, Multisets of aperiodic cycles, SIAM J. Algebraic Discrete Methods 3 (1982), no. 3, 359--368. MR0666861(84i:05008).
Robert L. Davis, The number of structures of finite relations, Proc. Amer. Math. Soc. 4 (1953), 486-495.
Oscar Defrain, Antonio E. Porreca and Ekaterina Timofeeva, Polynomial-delay generation of functional digraphs up to isomorphism, arXiv:2302.13832 [cs.DS], 2023-2024.
Oscar Defrain, Antonio E. Porreca and Ekaterina Timofeeva, Polynomial-delay generation of functional digraphs up to isomorphism, Disc. Appl. Math., vol 357 (2024), pp. 24-33.
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, 2009; see page 480
Alexander Heaton, Songpon Sriwongsa, and Jeb F. Willenbring, Branching from the General Linear Group to the Symmetric Group and the Principal Embedding, Algebraic Combinatorics, vol. 4, issue 2 (2021), p. 189-200.
Florent Hivert, Jean-Christophe Novelli, and Jean-Yves Thibon, Commutative combinatorial Hopf algebras, arXiv:math/0605262 [math.CO], 2006.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 144
Sujoy Mukherjee and Petr Vojtěchovský, Minimal representatives of endofunctions, Univ. Denver (2024).
Ronald C. Read, Note on number of functional digraphs, Math. Ann., vol. 143 (1961), pp. 109-111.
Marko Riedel, stackexchange.com, Enumeration of functions by Simultaneous Power Group Enumeration (SPGE)
Marko Riedel, Maple code for sequence using SPGE
Sara Riva, Factorisation of Discrete Dynamical Systems, Ph.D. Thesis, Univ. Côte d'Azur (France 2023).
N. J. A. Sloane, Illustration of initial terms
N. J. A. Sloane, Transforms
P. R. Stein, Letter to N. J. A. Sloane, Jun 02 1971

Cf. A000312, A002861, A006961, A001373, A054050, A054745.

with(combstruct): M[ 2671 ] := [ F,{F=Set(K), K=Cycle(T), T=Prod(Z,Set(T))},unlabeled ]:
a:=seq(count(M[2671],size=n),n=0..27); # added by W. Edwin Clark, Nov 23 2010

Needs["Combinatorica`"];
nn=30;s[n_,k_]:=s[n,k]=a[n+1-k]+If[n<2 k,0,s[n-k,k]];a[1]=1;a[n_]:=a[n]=Sum[a[i] s[n-1,i] i,{i,1,n-1}]/(n-1);rt=Table[a[i],{i,1,nn}];c=Drop[Apply[Plus,Table[Take[CoefficientList[CycleIndex[CyclicGroup[n],s]/.Table[s[j]->Table[Sum[rt[[i]] x^(k*i),{i,1,nn}],{k,1,nn}][[j]],{j,1,nn}],x],nn],{n,1,30}]],1];CoefficientList[Series[Product[1/(1-x^i)^c[[i]],{i,1,nn-1}],{x,0,nn}],x]  (* after code given by Robert A. Russell in A000081 *) (* Geoffrey Critzer, Oct 12 2012 *)
max = 40; A[n_] := A[n] = If[n <= 1, n, Sum[DivisorSum[j, #*A[#]&]*A[n-j], {j, 1, n-1}]/(n-1)]; H[t_] := Sum[A[n]*t^n, {n, 0, max}]; F = 1 / Product[1 - H[x^n], {n, 1, max}] + O[x]^max; CoefficientList[F, x] (* Jean-François Alcover, Dec 01 2015, after Joerg Arndt *)

N=66;  A=vector(N+1, j, 1);
for (n=1, N, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d * A[d]) * A[n-k+1] ) );
A000081=concat([0], A);
H(t)=subst(Ser(A000081, 't), 't, t);
x='x+O('x^N);
F=1/prod(n=1,N, 1 - H(x^n));
Vec(F)
\\ Joerg Arndt, Jul 10 2014

Euler transform of A002861.

a(n) ~ c * d^n / sqrt(n), where d = A051491 = 2.9557652856519949747148... (Otter's rooted tree constant), c = 0.442876769782206479836... (for a closed form see "Mathematical Constants", p.308). - Vaclav Kotesovec, Mar 17 2015

More terms etc. from Paul Zimmermann, Mar 15 1996

Name edited by Keith J. Bauer, Jan 07 2024

A048888 a(n) = Sum_{m=1..n} T(m,n+1-m), array T as in A048887.

Original entry on oeis.org

0, 1, 2, 4, 7, 13, 23, 42, 76, 139, 255, 471, 873, 1627, 3044, 5718, 10779, 20387, 38673, 73561, 140267, 268065, 513349, 984910, 1892874, 3643569, 7023561, 13557019, 26200181, 50691977, 98182665, 190353369, 369393465, 717457655

Offset: 0

Clark Kimberling

nonn

From Marc LeBrun, Dec 12 2001: (Start)
Define a "numbral arithmetic" by replacing addition with binary bitwise inclusive-OR (so that [3] + [5] = [7] etc.) and multiplication becomes shift-&-OR instead of shift-&-add (so that [3] * [3] = [7] etc.). [d] divides [n] means there exists an [e] with [d] * [e] = [n]. For example the six divisors of [14] are [1], [2], [3], [6], [7] and [14]. Then it appears that this sequence gives the number of proper divisors of [2^n-1]. Conjecture confirmed by Richard C. Schroeppel, Dec 14 2001. (End)
The number of "prime endofunctions" on n points, meaning the cardinality of the subset of the A001372(n) mappings (or mapping patterns) up to isomorphism from n (unlabeled) points to themselves (endofunctions) which are neither the sum of prime endofunctions (i.e., whose disjoint connected components are prime endofunctions) nor the categorical product of prime endofunctions. The n for which a(n) is prime (n such that the number of prime endofunctions on n points is itself prime) are 2, 4, 5, 6, 9, 13, 19, ... - Jonathan Vos Post, Nov 19 2006
For n>=1, compositions p(1)+p(2)+...+p(m)=n such that p(k)<=p(1)+1, see example. - Joerg Arndt, Dec 28 2012

			From _Joerg Arndt_, Dec 28 2012: (Start)
There are a(6)=23 compositions p(1)+p(2)+...+p(m)=6 such that p(k)<=p(1)+1:
[ 1]  [ 1 1 1 1 1 1 ]
[ 2]  [ 1 1 1 1 2 ]
[ 3]  [ 1 1 1 2 1 ]
[ 4]  [ 1 1 2 1 1 ]
[ 5]  [ 1 1 2 2 ]
[ 6]  [ 1 2 1 1 1 ]
[ 7]  [ 1 2 1 2 ]
[ 8]  [ 1 2 2 1 ]
[ 9]  [ 2 1 1 1 1 ]
[10]  [ 2 1 1 2 ]
[11]  [ 2 1 2 1 ]
[12]  [ 2 1 3 ]
[13]  [ 2 2 1 1 ]
[14]  [ 2 2 2 ]
[15]  [ 2 3 1 ]
[16]  [ 3 1 1 1 ]
[17]  [ 3 1 2 ]
[18]  [ 3 2 1 ]
[19]  [ 3 3 ]
[20]  [ 4 1 1 ]
[21]  [ 4 2 ]
[22]  [ 5 1 ]
[23]  [ 6 ]
(End)

D. Applegate, M. LeBrun, N. J. A. Sloane, Dismal Arithmetic, J. Int. Seq. 14 (2011) # 11.9.8.
A. Frosini and S. Rinaldi, On the Sequence A079500 and Its Combinatorial Interpretations, J. Integer Seq., Vol. 9 (2006), Article 06.3.1.

Cf. A007059.

Cf. A000312, A001372, A002861, A006961, A001373, A054050, A054745, A125024.

N = 66;  x = 'x + O('x^N);
gf = sum(n=0,N,  (1-x^n)*x^n/(1-2*x+x^(n+1)) ) + 'c0;
v = Vec(gf);  v[1]-='c0;  v
/* Joerg Arndt, Apr 14 2013 */

G.f.: Sum_{k>0} x^k*(1-x^k)/(1-2*x+x^(k+1)). - Vladeta Jovovic, Feb 25 2003

a(m) = Sum_{ n=2..m+1 } Fn(m) where Fn is a Fibonacci n-step number (Fibonacci, tetranacci, etc.) indexed as in A000045, A000073, A000078. - Gerald McGarvey, Sep 25 2004

A054050 Number of nonisomorphic binary n-state automata.

Original entry on oeis.org

1, 10, 129, 2836, 83061, 3076386, 136647824, 7081061404, 419223006090, 27914819962058, 2064872379041701, 167986348586006675, 14906892578198245332, 1432903480780688968334, 148318150277923875087238, 16447662583606982784243526, 1945436946407977282783367806, 244476687257496605058725664611

Offset: 1

Vladeta Jovovic, Apr 29 2000

nonn

Also, number of isomorphism classes of ordered pairs of endofunctions (i.e., an order pair (f,g) of functions) from {1,...,n} to itself. - Christian G. Bower, Dec 18 2003

			From _Petros Hadjicostas_, Mar 08 2021: (Start)
For n = 2, we have the partitions 1*2 + 2*0 and 1*0 + 2*1 of 2 (in frequency notation). The corresponding denominators in _Christian G. Bower_'s formula are 1^2*2!*2^0*0! = 2 and 1^0*0!*2^1*1! = 2.
Also, fixA[s_1 = 2, s_2 = 0] = (Sum_{d|1} d*s_d)^(2*s_1) * (Sum_{d|2} d*s_d)^(2*s_2) = (1*s_1)^(2*s_1) = 16. In addition, fixA[s_1 = 0, s_2 = 1] = (Sum_{d|1} d*s_d)^(2*s_1) * (Sum_{d|2} d*s_d)^(2*s_2) = (1*s_1 + 2*s_2)^(2*s_2) = (0 + 2)^2 = 4. Hence a(2) = 16/2 + 4/2 = 10. (End)

F. Harary and E. Palmer, Graphical Enumeration, 1973.

M. A. Harrison, A census of finite automata, Canad. J. Math., 17, No. 1, (1965), 100-113. [See p. 107 (Theorem 6.1 with k = 2 and p = 1) and p. 110 (Table I).]

Cf. A001372, A002854, A054745, A054051.

A054050(n)={local(p=vector(n));
my(S=0, A() = prod(i=1, n, sumdiv(i, d, d*p[d])^(2*p[i])),
inc()=!forstep(i=n, 1, -1, p[i]n, p[i]=n); next(2))); t==n && S+ = A()/prod(i=1, n, i^p[i]*p[i]!)); S} \\ This is a modification of M. F. Hasler's PARI program from A002854. - Petros Hadjicostas, Mar 08 2021

a(n) = Sum_{1*s_1+2*s_2+...=n} fixA[s_1, s_2, ...]/(1^s_1*s_1!*2^s_2*s_2!*...), where fixA[s_1, s_2, ...] = Product_{i>=1} (Sum_{d|i} d*s_d)^(2*s_i). - Christian G. Bower, Dec 18 2003 [Corrected by Petros Hadjicostas, Mar 08 2021 using Theorem 6.1 in Harrison (1965) with k = 2 inputs and p = 1 output.]

a(16)-a(18) from Petros Hadjicostas, Mar 08 2021

A054746 Number of nonisomorphic connected binary n-state automata without output under input permutations.

Original entry on oeis.org

1, 6, 67, 1379, 40000, 1488212, 66468616, 3459744878, 205517092374, 13719689837415, 1016860316477931, 82855990193202263, 7361905026684383986, 708398087768889272827, 73390382551302560225067, 8144731151602797676232825, 963990026196934640329291135

Offset: 1

Vladeta Jovovic, Apr 22 2000

nonn

Inverse Euler transform of A054745.

			There are 40000 nonisomorphic connected binary 5-state automata under input permutations.

F. Harary and E. Palmer, Graphical Enumeration, 1973.

Alois P. Heinz, Table of n, a(n) for n = 1..45
M. A. Harrison, A census of finite automata, Canad. J. Math., 17, No. 1, 1965, p. 110.

Cf. A054732, A027834.

More terms from Alois P. Heinz, Feb 20 2017

A362897 Array read by antidiagonals: T(n,k) is the number of nonisomorphic multisets of endofunctions on an n-set with k endofunctions.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 7, 7, 1, 1, 1, 13, 74, 19, 1, 1, 1, 22, 638, 1474, 47, 1, 1, 1, 34, 4663, 118949, 41876, 130, 1, 1, 1, 50, 28529, 7643021, 42483668, 1540696, 343, 1, 1, 1, 70, 151600, 396979499, 33179970333, 23524514635, 68343112, 951, 1

Offset: 0

Andrew Howroyd, May 10 2023

Isomorphism is up to permutations of the elements of the n-set.

			Array begins:
======================================================================
n/k| 0   1       2           3               4                   5 ...
---+------------------------------------------------------------------
0  | 1   1       1           1               1                   1 ...
1  | 1   1       1           1               1                   1 ...
2  | 1   3       7          13              22                  34 ...
3  | 1   7      74         638            4663               28529 ...
4  | 1  19    1474      118949         7643021           396979499 ...
5  | 1  47   41876    42483668     33179970333      20762461502595 ...
6  | 1 130 1540696 23524514635 274252613077267 2559276179593762172 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (first 51 antidiagonals).

Columns k=0..3 are A000012, A001372, A054745, A362898.
Row n=2 is A002623.
Main diagonal is A277839.
Cf. A362644.

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(v,m) = {prod(i=1, #v, my(g=gcd(v[i],m), e=v[i]/g); sum(j=1, #v, my(t=v[j]); if(e%(t/gcd(t,m))==0, t))^g)}
T(n,k) = {if(n==0, 1, my(s=0); forpart(q=n, s+=permcount(q) * polcoef(exp(sum(m=1, k, K(q,m)*x^m/m, O(x*x^k))), k)); s/n!)}

T(0,k) = T(1,k) = 1.

A362900 Number of nonisomorphic unordered pairs of fixed-point-free endofunctions on an n-set.

Original entry on oeis.org

1, 0, 1, 9, 162, 4527, 172335, 7861940, 416446379, 25076668511, 1692214417496, 126525497074469, 10384653020019554, 928348695659951013, 89797089935616345473, 9344984104905250973209, 1041167026926648579218267, 123655975822561996200923033, 15595901625395079379351443550

Offset: 0

Andrew Howroyd, May 10 2023

nonn

Isomorphism is up to permutation of the elements of the n-set.

			In the following example the notation 211 corresponds to the fixed-point-free mapping {1->2, 2->1, 3->1}.
The a(3) = 9 nonisomorphic pairs of endofunctions are: {211, 211}, {211, 212}, {211, 231}, {211, 232}, {211, 311}, {211, 312}, {211, 332}, {231, 231}, {231, 312}.

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

Column k=2 of A362899.

Cf. A054745 (allowing fixed-points).

A362898 Number of nonisomorphic unordered triples of endofunctions on an n-set.

Original entry on oeis.org

1, 1, 13, 638, 118949, 42483668, 23524514635, 18477841853059, 19526400231564564, 26714255854638149145, 45938634690184528585855, 96990967579564469350287613, 246664446832722382952639028437, 743740463651636548809953508690270, 2623456914417867939801667337352637825

Offset: 0

Andrew Howroyd, May 10 2023

nonn

Isomorphism is up to permutation of the elements of the n-set.

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

Column k=3 of A362897.

Cf. A001372, A054745.

A054051 Number of nonisomorphic connected binary n-state automata.

Original entry on oeis.org

1, 9, 119, 2662, 79154, 2962062, 132536919, 6904606698, 410379198542, 27406396140548, 2031843175944876, 165592123280454675, 14715292998356150461, 1416127682894394114138, 146723247630856311651736, 16284075762705841850155071, 1927434528878738556115924081, 242361176791511465207020367116

Offset: 1

Vladeta Jovovic, Apr 29 2000

nonn

Inverse Euler transform of A054050.

F. Harary and E. Palmer, Graphical Enumeration, 1973. [See Section 6.5, pp. 146-150.]

Christian G. Bower, PARI programs for transforms, 2007.
Michael A. Harrison, A census of finite automata, Canad. J. Math., 17, No. 1 (1965), 100-113. [See Theorem 6.1 (p. 107) with k = 2 and p = 1 and Theorem 7.2 (p. 110). See also Table I on p. 110.]
N. J. A. Sloane, Maple programs for transforms, 2001-2020.

Cf. A054050, A054745, A054746.

/* This program is a modification of Christian G. Bower's PARI program for the inverse Euler transform from the link above. */
lista(nn) = {local(A=vector(nn+1)); for(n=1, nn+1, A[n]=if(n==1, 1, A054050(n-1))); local(B=vector(#A-1, n, 1/n), C); A[1] = 1; C = log(Ser(A)); A=vecextract(A, "2.."); for(i=1, #A, A[i] = polcoeff(C, i)); A = dirdiv(A, B); } \\ Petros Hadjicostas, Mar 08 2021

Terms a(16)-a(18) from Petros Hadjicostas, Mar 08 2021

A230326 Number of nonisomorphic strongly connected binary n-state automata without output under input permutations.

Original entry on oeis.org

1, 4, 29, 460, 10701, 329794, 12310961, 538586627, 26959384899, 1518185815760

Offset: 1

Marek Szykula, Oct 16 2013

			For n=2 there are 4 such automata: [0 a 1,0 b 1,1 a 0,1 b 0], [0 a 0,0 b 1,1 a 0,1 b 0], [0 a 0,0 b 1,1 a 1,1 b 0] and [0 a 0,0 b 1,1 a 0,1 b 1].

A. Kisielewicz and M. Szykuła. Generating Small Automata and the Černý Conjecture. In Implementation and Application of Automata, volume 7982 of LNCS, pages 340-348, 2013.

Cf. A054745, A054746, A027835.

A124933 Number of prime divisors (counted with multiplicity) of number of endofunctions on n points (A001372).

Original entry on oeis.org

0, 0, 1, 1, 1, 1, 3, 3, 2, 2, 2, 2, 2, 4, 2, 3, 5, 3, 3, 3, 3, 5, 3, 2, 7, 9, 5, 3, 5, 5, 6, 3, 5, 6, 1, 2, 5, 4, 3, 4, 3, 3, 7, 7, 5, 7, 8, 4, 12, 7, 8, 1, 7, 4, 2, 4, 5, 4, 2, 5, 4, 3, 5, 6, 12, 2, 3, 5, 2, 3, 4, 4, 3, 5, 6, 2, 6, 3, 5, 3, 7, 2, 3, 7, 7, 8, 6, 5, 2, 7, 7, 4, 10, 11, 7, 7, 5, 4, 5, 6

Offset: 0

Jonathan Vos Post, Nov 12 2006

nonn

Number of prime divisors (counted with multiplicity) of A001372 Number of mappings (or mapping patterns) from n points to themselves; number of endofunctions. {n: a(n) = 1} give the primes, beginning: A001372(2) = 3, A001372(3) = 7, A001372(4) = 19, A001372(2) = 47. {n: a(n) = 2} give the semiprimes, beginning: A001372(8) = 951 = 3 * 317, A001372(9) = 2615 = 5 * 523, A001372(10) = 7318 = 2 * 3659, A001372(11) = 20491 = 31 * 661, A001372(12) = 57903 = 3 * 19301, A001372(14) = 466199 = 107 * 4357, A001372(23) = 6218869389 = 3 * 2072956463. 3-almost primes begin: A001372(6) = 130 = 2 * 5 * 13, A001372(7) = 343 = 7^3, A001372(15) = 1328993 = 19 * 113 * 619, A001372(17) = 10884049 = 11 * 353 * 2803, A001372(18) = 31241170 = 2 * 5 * 3124117, A001372(19) = 89814958 = 2 * 5113 * 8783, A001372(20) = 258604642 = 2 * 101 * 1280221, A001372(22) = 2152118306 = 2 * 13 * 82773781, A001372(27) = 437571896993.

Harald Fripertinger and Peter Schopf, Endofunctions of given cycle type, The Annales des Sciences Mathematiques du Quebec 23 (2), 173 - 187, 1999. Web page links to PDF. Relates combinatorial species theory to more classical enumeration.

Cf. A000040, A000312, A002861, A006961, A001372, A001373, A054050, A054745.

a(n) = Omega(A001372(n)) = A001222(A001372(n)).

More terms from R. J. Mathar, Sep 23 2007

cp's OEIS Frontend

A001372 Number of unlabeled mappings (or mapping patterns) from n points to themselves; number of unlabeled endofunctions.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A048888 a(n) = Sum_{m=1..n} T(m,n+1-m), array T as in A048887.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A054050 Number of nonisomorphic binary n-state automata.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A054746 Number of nonisomorphic connected binary n-state automata without output under input permutations.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A362897 Array read by antidiagonals: T(n,k) is the number of nonisomorphic multisets of endofunctions on an n-set with k endofunctions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A362900 Number of nonisomorphic unordered pairs of fixed-point-free endofunctions on an n-set.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A362898 Number of nonisomorphic unordered triples of endofunctions on an n-set.

Views

Author

Keywords

Comments

Links

Crossrefs

A054051 Number of nonisomorphic connected binary n-state automata.

Views

Author

Keywords

Comments