A054050 -id:A054050 - 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

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

Original entry on oeis.org

1, 1, 7, 74, 1474, 41876, 1540696, 68343112, 3540691525, 209612916303, 13957423192794, 1032436318269648, 83993175608894096, 7453446303042245261, 716451740543945788671, 74159075140708644544128, 8223831291824019614386868, 972718473204236819072891710

Offset: 0

Vladeta Jovovic, Apr 22 2000

nonn

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

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

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

Cf. A001372, A054050, A054732, A054746.

with(numtheory):
b:= proc(n, i) option remember; `if`(n=0, {0}, `if`(i<1, {},
      {seq(map(p-> p+j*x^i, b(n-i*j, i-1) )[], j=0..n/i)}))
    end:
a:= proc(n) option remember; add(add(mul(mul(add(coeff(s, x, d)
      *d, d=divisors(ilcm(i, j)))^(igcd(i, j)*coeff(s, x, i)*
      coeff(t, x, j)), j=1..degree(t)), i=1..degree(s))
      /mul(i^coeff(t, x, i)*coeff(t, x, i)!, i=1..degree(t))
      /mul(i^coeff(s, x, i)*coeff(s, x, i)!, i=1..degree(s))
      , t=b(2$2)), s=b(n$2))
    end:
seq(a(n), n=0..20);  # Alois P. Heinz, Aug 15 2014

b[n_, i_] := b[n, i] = If[n==0, {0}, If[i<1, {}, Table[Map[Function[{p}, p + j*x^i], b[n - i*j, i-1]], {j, 0, n/i}] // Flatten // Union]];
a[n_] := a[n] = Sum[Sum[Product[Product[With[{g = GCD[i, j]*Coefficient[s, x, i]*Coefficient[t, x, j]}, If[g==0, 1, Sum[Coefficient[s, x, d]*d, {d, Divisors[LCM[i, j]]}]^g]], {j, 1, Exponent[t, x]}], {i, 1, Exponent[s, x]}]/
Product[i^Coefficient[t, x, i]Coefficient[t, x, i]!, {i, Exponent[t, x]}]/
Product[i^Coefficient[s, x, i]Coefficient[s, x, i]!, {i, Exponent[s, x]}], {t, b[2, 2]}], {s, b[n, n]}];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Mar 16 2015, after Alois P. Heinz, updated Jan 01 2021 *)

a(n) = sum {1*s_1+2*s_2+...=n, 1*t_1+2*t_2=2} (fixA[s_1, s_2, ...;t_1, t_2]/(1^s_1*s_1!*2^s_2*s_2!*...*1^t_1*t_1!*2^t_2*t_2!)) where fixA[...] = prod {i, j>=1} ( (sum {d|lcm(i, j)} (d*s_d))^(gcd(i, j)*s_i*t_j)). - Christian G. Bower, Dec 18 2003

More terms from Alois P. Heinz, Aug 15 2014

A054052 Number of nonisomorphic n-state automata with binary inputs and outputs.

Original entry on oeis.org

4, 136, 7860, 703760, 83731616, 12434579448, 2213014106124, 459106576445584, 108787771126443552, 28987989805582701000, 8579866813375037411844, 2792769757495835238342624, 991517773420290134796904064, 381299821992680629261308708504, 157894902912089771345216547890976, 70047508374342247037912201234627760

Offset: 1

Vladeta Jovovic, Apr 29 2000

nonn

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 = p = 2) and p. 112 (Table III).]

Cf. A002854, A054050, A054747, A054732, A054053.

A054052(n) = {local(p=vector(n)); my(S=0, A() = prod(i=1, n, sumdiv(i, d, 2*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} 2*d*s_d)^(2*s_i). - [Modified from Christian G. Bower's contribution in A054050 by Petros Hadjicostas, Mar 08 2021 using Theorem 6.1 in Harrison (1965) with k = 2 inputs and p = 2 outputs.]

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

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

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

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A054052 Number of nonisomorphic n-state automata with binary inputs and outputs.

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A054051 Number of nonisomorphic connected binary n-state automata.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions