A001372 -id:A001372 - cp's OEIS frontend

A368830 Number of square unlabeled endofunctions from n points to themselves.

1, 1, 2, 4, 9, 20, 47, 105

Offset: 0

Keith J. Bauer, Jan 07 2024

Also known as square maps or square mapping patterns.

Two endofunctions are taken to be equivalent up to labeling if one is the conjugation of the other by a permutation. (Conjugation is applying the inverse permutation, the endofunction, and then the permutation, in that order. This is equivalent to permuting the "labels" of the set.)

			The a(3) = 4 square endofunctions are:
  1->1, 2->2, 3->3
  1->1, 2->1, 3->1 (equivalent to any constant function)
  1->1, 2->2, 3->1 (equivalent to any function consisting of 2 1-cycles)
  1->2, 2->3, 3->1 (equivalent to any 3-cycle)
Each function listed here is its own square root, except for the 3-cycle, whose square root is its inverse.

Cf. A001372, A102687 (labeled version).

A002823 Number of period-n solutions to a certain "universal" equation related to transformations on the unit interval.

Original entry on oeis.org

1, 1, 3, 4, 9, 14, 27, 48, 93, 163, 315, 576, 1085

Offset: 3

N. J. A. Sloane

a(n) <= A000048(n), since the solutions counted here are a subset of the solutions counted by A000048 (called U sequence in the paper). The observed equality for prime n means that there are in this case no harmonics, which would disappear. - M. F. Hasler, Nov 05 2014

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).

N. Metropolis, M. L. Stein and P. R. Stein, On finite limit sets for transformations on the unit interval, J. Combin. Theory, A 15 (1973), 25-44; reprinted in P. Cvitanovic, ed., Universality in Chaos, Hilger, Bristol, 1986, pp. 187-206.
P. R. Stein, Letter to N. J. A. Sloane, Jun 02 1971

Cf. A000048, A001372.

A027853 Functions on n points with a single labeled point.

Original entry on oeis.org

0, 1, 4, 15, 52, 175, 571, 1838, 5834, 18363, 57372, 178271, 551344, 1698782, 5217266, 15979465, 48825416, 148877730, 453124341, 1376890744, 4177819301, 12659943750, 38317731349, 115851225052, 349924919167

Offset: 0

Christian G. Bower

nonn

Convolution of A038002 with A001372.

A127120 Column limit of A127119.

Original entry on oeis.org

1, 3, 12, 41, 140, 457, 1485, 4732, 14986, 47025, 146784, 455683, 1409122, 4341456, 13336440, 40858875, 124894889, 380993722, 1160145321, 3527008680, 10707133507, 32461710583, 98300107420, 297348593017, 898559807247, 2712889137261, 8183743165156, 24668014337837

Offset: 0

Franklin T. Adams-Watters, Jan 05 2007

nonn

Number of endofunctions on a set with m+n elements, where the maximum indegree is m, when m > n. Increasing m just adds additional points with empty preimage that map to the unique element with indegree m.

Cf. A001372, A127119, A127122.

\\ Needs F from A127119.
seq(n)={my(m=2*n-1); Vecrev(F(m)[m,n..m])} \\ Andrew Howroyd, Feb 21 2020

Terms a(5) and beyond from Andrew Howroyd, Feb 21 2020

A127136 Triangle read by rows: T(n,k) is the number of endofunctions on n objects with k components.

Original entry on oeis.org

1, 2, 1, 4, 2, 1, 9, 7, 2, 1, 20, 17, 7, 2, 1, 51, 48, 21, 7, 2, 1, 125, 127, 60, 21, 7, 2, 1, 329, 352, 174, 65, 21, 7, 2, 1, 862, 963, 504, 190, 65, 21, 7, 2, 1, 2311, 2689, 1456, 570, 196, 65, 21, 7, 2, 1, 6217, 7496, 4212, 1684, 590, 196, 65, 21, 7, 2, 1

Offset: 1

Franklin T. Adams-Watters, Jan 05 2007

For k > n/2, T(n,k) = T(n-1,k-1). - Geoffrey Critzer, Oct 13 2012

			For n = 3, the 7 endofunctions are (1,2,3) -> (1,1,1), (1,1,2), (1,2,1), (2,1,1), (1,2,3), (1,3,2) and (2,3,1). The components are respectively 123, 123, 13|2, 123, 1|2|3, 1|23 and 123; the number of components is thus 1, 1, 2, 1, 2, 3, 2, 1, so row 3 is 4,2,1.
The triangle starts:
   1;
   2,  1;
   4,  2,  1;
   9,  7,  2,  1;
  20, 17,  7,  2,  1;

Cf. A001372 (row sums), A127124, A127125, A002861 (first column).

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-y x^i)^c[[i]],{i,1,nn-1}],{x,0,10}],{x,y}]//Grid  (* Geoffrey Critzer, Oct 13 2012, after code given by Robert A. Russell in A000081 *)

G.f.: Product_{k>=1} 1/(1 - x^k*y)^A002861(k).

More terms from Geoffrey Critzer, Oct 13 2012

Corrected and extended by Alois P. Heinz, May 24 2013

A217897 Triangular array read by rows. T(n,k) is the number of unlabeled functions on n nodes that have exactly k fixed points, n >= 0, 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 1, 1, 1, 2, 3, 1, 1, 6, 7, 4, 1, 1, 13, 19, 9, 4, 1, 1, 40, 47, 27, 10, 4, 1, 1, 100, 130, 68, 29, 10, 4, 1, 1, 291, 343, 195, 76, 30, 10, 4, 1, 1, 797, 951, 523, 220, 78, 30, 10, 4, 1, 1, 2273, 2615, 1477, 600, 228, 79, 30, 10, 4, 1, 1, 6389, 7318, 4096, 1708, 625, 230, 79, 30, 10, 4, 1, 1

Offset: 0

Geoffrey Critzer, Oct 14 2012

Row sums are A001372;
  Column for k=0 is A001373;
  Column for k=1 is A001372. (offset)

			Triangle begins:
     1;
     0,    1;
     1,    1,    1;
     2,    3,    1,   1;
     6,    7,    4,   1,   1;
    13,   19,    9,   4,   1,  1;
    40,   47,   27,  10,   4,  1,  1;
   100,  130,   68,  29,  10,  4,  1,  1;
   291,  343,  195,  76,  30, 10,  4,  1, 1;
   797,  951,  523, 220,  78, 30, 10,  4, 1, 1;
  2273, 2615, 1477, 600, 228, 79, 30, 10, 4, 1, 1;

N. J. A. Sloane, Illustration of initial terms of A001372

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}];cfd=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,2,30}]],1]; CoefficientList[Series[Product[1/(1-x^i)^cfd[[i]]/(1-y x^i)^rt[[i]],{i,1,nn-1}],{x,0,10}],{x,y}]//Grid (* after code given by Robert A. Russell in A000081 *)

O.g.f.: Product_{n>=1} 1/((1-x^n)^A002862(n) * (1 - y*x^n)^A000081(n) ).

A244519 Expansion of Product_{n>=1} (1 + H(x^n)) where H(x) is the g.f. of A000081.

Original entry on oeis.org

1, 1, 2, 4, 8, 16, 35, 76, 175, 414, 1009, 2510, 6382, 16448, 42961, 113352, 301715, 808932, 2182739, 5921803, 16143975, 44199809, 121477237, 335015538, 926814691, 2571322157, 7152404733, 19942874638, 55729271645, 156051344975, 437801148097, 1230423785329, 3463777894236, 9766002585763, 27574869734583, 77965430442158

Offset: 0

Joerg Arndt, Jul 10 2014

nonn

Which combinatorial objects does this sequence count?

Joerg Arndt, Table of n, a(n) for n = 0..500

Cf. A001372 (expansion of 1/Product_{n>=1} (1 - H(x^n))).

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);
T=prod(n=1,N, 1 + H(x^n));
Vec(T)

A368943 Number of unlabeled mappings from n points to themselves with unique square root (endofunctions).

Original entry on oeis.org

1, 1, 1, 1, 3, 7, 11, 23, 50

Offset: 0

Keith J. Bauer, Jan 11 2024

A mapping f has a unique square root if there exists a unique g such that gg = f.

Two mappings (endofunctions) are taken to be equivalent up to labeling if one is the conjugation of the other by a permutation. (Conjugation is applying the inverse permutation, the endofunction, and then the permutation, in that order. This is equivalent to permuting the "labels" of the set.)

			For n = 4, representatives of the a(4) = 3 mappings up to relabeling are
  1->1 2->1 3->2 4->1
  1->2 2->3 3->1 4->1
  1->2 2->3 3->1 4->4
whose unique square roots are respectively
  1->1 2->1 3->4 4->2
  1->3 2->1 3->2 4->2
  1->3 2->1 3->2 4->4

Keith J. Bauer, Visualization of a(6)

The labeled version is A368867.

Cf. A000700 (permutations only) < this sequence < A368830 (any square maps) < A001372 (all maps).

a(8) from Andrew Howroyd, Jan 10 2024

A381123 Number of unlabeled endofunctions on n points whose self-referencing elements are mapped from another element.

Original entry on oeis.org

1, 0, 2, 4, 12, 28, 83, 213, 608, 1664, 4703, 13173, 37412, 105995, 302301, 862794, 2470631, 7084425, 20357121, 58573788, 168789684, 486964114, 1406549550, 4066751083, 11769363663, 34090076148, 98820914068, 286672673725, 832183340955, 2417270306657, 7025657374736, 20430883575932, 59444386613999, 173039084438093

Offset: 0

Peter Dolland, Feb 14 2025

nonn

Equivalently, the number of digraphs on n unlabeled nodes where each node has an out degree 1 and, if it is self-referencing, it is referenced from at least one other node.

			For n = 2 one node must reference the other one, this one may reference itself or the first one. So a(2) = 2.
For n = 3 there are 7 = A001372(3) endofunctions, but 3 = A001372(2) of them have at least 1 isolated element. So a(3) = 7 - 3 = 4.

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Partial differences of A001372.

a(0) = 1; a(n) = A001372(n) - A001372(n - 1) for n > 0.

A032176 Functions of n points with no symmetries.

Original entry on oeis.org

1, 1, 3, 6, 15, 34, 82, 193, 464, 1111, 2683, 6482, 15730, 38232, 93177, 227458, 556323, 1362639, 3342504, 8209130, 20185204, 49684404, 122413446, 301870406, 745019874, 1840103575, 4548008306, 11248190948

Offset: 1

Christian G. Bower

nonn

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 328. (4.4.31).

C. G. Bower, Transforms (2)
N. J. A. Sloane, Transforms

Cf. A001372.

WEIGH transform of A032175. Also g.f. = (1-B(x^2))/(1-B(x)), B(x)=g.f. of A004111.

cp's OEIS Frontend

A368830 Number of square unlabeled endofunctions from n points to themselves.

Views

Author

Keywords

Comments

Examples

Crossrefs

A002823 Number of period-n solutions to a certain "universal" equation related to transformations on the unit interval.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A027853 Functions on n points with a single labeled point.

Views

Author

Keywords

Formula

A127120 Column limit of A127119.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Extensions

A127136 Triangle read by rows: T(n,k) is the number of endofunctions on n objects with k components.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A217897 Triangular array read by rows. T(n,k) is the number of unlabeled functions on n nodes that have exactly k fixed points, n >= 0, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Programs

Mathematica

Formula

A244519 Expansion of Product_{n>=1} (1 + H(x^n)) where H(x) is the g.f. of A000081.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A368943 Number of unlabeled mappings from n points to themselves with unique square root (endofunctions).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A381123 Number of unlabeled endofunctions on n points whose self-referencing elements are mapped from another element.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A032176 Functions of n points with no symmetries.

Views