A127911
Number of nonisomorphic partial functional graphs with n points which are not functional graphs.
Original entry on oeis.org
0, 1, 3, 9, 26, 74, 208, 586, 1647, 4646, 13135, 37247, 105896, 301880, 862498, 2469480, 7083690, 20353886, 58571805, 168780848, 486958481, 1406524978, 4066735979, 11769294050, 34090034328, 98820719105, 286672555274
Offset: 0
a(0) = 0 because the null graph is trivially both partial functional and functional.
a(1) = 1 because there are two partial functional graphs on one point: the point with, or without, a loop; the point with loop is the identity function, but without a loop the naked point is the unique merely partial functional case.
a(2) = 3 because there are A126285(2) enumerates the 6 partial functional graphs on 2 points, of which 3 are functional, 6 - 3 = 3.
a(3) = A126285(3) - A001372(3) = 16 - 7 = 9.
a(4) = 45 - 19 = 26.
a(5) = 121 - 47 = 74.
a(6) = 338 - 130 = 208.
a(7) = 929 - 343 = 586.
a(8) = 2598 - 951 = 1647.
a(9) = 7261 - 2615 = 4646.
a(10) = 20453 - 7318 = 13135.
- S. Skiena, "Functional Graphs." Section 4.5.2 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 164-165, 1990.
A127912
Number of nonisomorphic disconnected mappings (or mapping patterns) from n points to themselves; number of disconnected endofunctions.
Original entry on oeis.org
0, 1, 3, 10, 27, 79, 218, 622, 1753, 5007, 14274, 40954, 117548, 338485, 975721, 2817871, 8146510, 23581381, 68322672, 198138512, 575058726, 1670250623, 4854444560, 14117859226, 41081418963, 119606139728
Offset: 0
a(0) = 0, as the null digraph is formally neither connected nor disconnected.
a(1) = 0, as the unique endofunction on one point is the identity function on one value and is connected.
a(2) = 1, as there are 3 endofunctions on two points, two of which are "prime endofunctions" and one of which is the direct sum of two copies of the unique endofunction on one point, namely two points-with-loops, or the identity function on two values; 3 - 2 = 1.
a(3) = A001372(3) - A002861(3) = 7 - 4 = 3.
a(4) = A001372(4) - A002861(4) = 19 - 9 = 10.
a(5) = A001372(5) - A002861(5) = 47 - 20 = 27.
a(6) = 130 - 51 = 79.
a(7) = 343 - 125 = 218.
a(8) = 951 - 329 = 622.
a(9) = 2615 - 862 = 1753.
a(10) = 7318 - 2311 = 5007.
- Steven R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.6.6.
- R. A. Fisher, Contributions to Mathematical Statistics, Wiley, 1950, 41.399 and 41.401.
Original entry on oeis.org
1, 3, 7, 16, 36, 87, 212, 541, 1403, 3714, 9931, 26880, 73230, 200944, 554216, 1535969, 4273508, 11933297, 33425583, 93891713, 264401743, 746269426, 2110694255, 5981068081, 16977958318, 48271041858
Offset: 1
a(26) = 1 + 2 + 4 + 9 + 20 + 51 + 125 + 329 + 862 + 2311 + 6217 + 16949 + 46350 + 127714 + 353272 + 981753 + 2737539 + 7659789 + 21492286 + 60466130 + 170510030 + 481867683 + 1364424829 + 3870373826 + 10996890237 + 31293083540.
A217859
Triangular array read by rows. T(n,k) is the number of functions on n unlabeled nodes that have exactly k unique components (n >= 1, k >= 1).
Original entry on oeis.org
1, 3, 5, 2, 12, 7, 21, 25, 1, 58, 63, 9, 126, 178, 39, 341, 466, 140, 4, 867, 1253, 470, 25, 2334, 3418, 1431, 135, 6218, 9365, 4358, 544, 6, 17016, 25924, 12871, 2042, 50, 46351, 72207, 37993, 7056, 291, 127842, 202345, 111142, 23483, 1383, 4, 353297, 568822, 325359, 75701, 5754, 60
Offset: 1
Triangle begins:
1;
3,
5, 2;
12, 7;
21, 25, 1;
58, 63, 9;
126, 178, 39;
341, 466, 140, 4;
867, 1253, 470, 25;
2334, 3418, 1431, 135;
6218, 9365, 4358, 544, 6;
17016, 25924, 12871, 2042, 50;
46351, 72207, 37993, 7056, 291;
127842, 202345, 111142, 23483, 1383, 4;
353297, 568822, 325359, 75701, 5754, 60;
T(3,2)=2 because (in the link) the third and the fifth digraphs on 3 nodes are composed of 2 unique components.
-
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[((y x^i +1-x^i)/(1-x^i))^c[[i]],{i,1,nn-1}],{x,0,15}],{x,y}]//Grid
(* after code given by Robert A. Russell in A000081 *)
A217896
Number of unlabeled functions on n nodes that have at least one fixed point.
Original entry on oeis.org
0, 1, 2, 5, 13, 34, 90, 243, 660, 1818, 5045, 14102, 39639, 111982, 317533, 903464, 2577724, 7372542, 21130127, 60672017, 174492633, 502568607, 1449360241, 4184719174, 12095325486, 34993693260, 101332159421, 293669741860, 851722291650, 2471948910379, 6824540110584
Offset: 0
-
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];cf=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];fd=CoefficientList[Series[Product[1/(1-x^i)^cfd[[i]],{i,1,nn-1}],{x,0,nn}],x];f=CoefficientList[Series[Product[1/(1-x^i)^cf[[i]],{i,1,nn-1}],{x,0,nn}],x];f-fd (* Geoffrey Critzer, Oct 14 2012, after code given by Robert A. Russell in A000081 *)
A217898
Number of fixed points over all unlabeled functions on n nodes.
Original entry on oeis.org
0, 1, 3, 8, 22, 58, 158, 426, 1170, 3224, 8977, 25105, 70680, 199739, 566842, 1613454, 4605788, 13177776, 37782903, 108522417, 312207970, 899460505, 2594638480, 7493254511, 21663019843, 62687523055, 181561095507, 526275453283, 1526600618192, 4431347014046, 12516888508178
Offset: 0
-
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[D[Product[1/(1-x^i)^cfd[[i]]/(1-y x^i)^rt[[i]], {i,1,nn-1}],y]/.y->1,{x,0,nn}],x] (* after code given by Robert A. Russell in A000081 *)
A225772
Number of 2-element sets of mapping patterns from n points to themselves; the number of 2-element sets of transformations on n points up to conjugation.
Original entry on oeis.org
0, 4, 67, 1455, 41829, 1540566, 68342769, 3540690574, 209612913688, 13957423185476, 1032436318249157, 83993175608836193, 7453446303042081363, 716451740543945322472, 74159075140708643215135
Offset: 1
- J. D. Mitchell, Semigroups data (contains links to files containing the 2-element sets of transformations on n points up to conjugation)
A350571
Triangular array read by rows. T(n,k) is the number of unlabeled partial functions on [n] with exactly k undefined points, n>=0, 0<=k<=n.
Original entry on oeis.org
1, 1, 1, 3, 2, 1, 7, 6, 2, 1, 19, 16, 7, 2, 1, 47, 45, 19, 7, 2, 1, 130, 121, 57, 20, 7, 2, 1, 343, 338, 158, 60, 20, 7, 2, 1, 951, 929, 457, 170, 61, 20, 7, 2, 1, 2615, 2598, 1286, 498, 173, 61, 20, 7, 2, 1, 7318, 7261, 3678, 1421, 510, 174, 61, 20, 7, 2, 1
Offset: 0
Triangle T(n,k) begins:
1;
1, 1;
3, 2, 1;
7, 6, 2, 1;
19, 16, 7, 2, 1;
47, 45, 19, 7, 2, 1;
130, 121, 57, 20, 7, 2, 1;
343, 338, 158, 60, 20, 7, 2, 1;
951, 929, 457, 170, 61, 20, 7, 2, 1;
...
- O. Ganyushkin and V. Mazorchuk, Classical Finite Transformation Semigroups, Springer, 2009.
-
nn = 10; A002861 = Cases[Import["https://oeis.org/A002861/b002861.txt",
"Table"], {, }][[;; nn, 2]];
A000081 = Drop[Cases[ Import["https://oeis.org/A000081/b000081.txt",
"Table"], {, }][[;; nn + 1, 2]], 1];
Map[Select[#, # > 0 &] &, CoefficientList[Series[ Product[1/(1 - y x^i)^A000081[[i]], {i, 1, nn}] Product[1/(1 - x^i)^A002861[[i]], {i, 1, nn}], {x, 0, nn}], {x,y}]] // Grid
A368858
Number of perfect cube unlabeled endofunctions from n points to themselves.
Original entry on oeis.org
1, 1, 3, 5, 12, 22, 49, 99
Offset: 0
Comments