- FindStat

edit this statistic or download as text // json

Identifier

St000634: Posets ⟶ ℤ

Values

([],2) => 4

([(0,1)],2) => 3

([],3) => 27

([(1,2)],3) => 12

([(0,1),(0,2)],3) => 11

([(0,2),(2,1)],3) => 10

([(0,2),(1,2)],3) => 11

([],4) => 256

([(2,3)],4) => 80

([(1,2),(1,3)],4) => 48

([(0,1),(0,2),(0,3)],4) => 67

([(0,2),(0,3),(3,1)],4) => 40

([(0,1),(0,2),(1,3),(2,3)],4) => 36

([(1,2),(2,3)],4) => 44

([(0,3),(3,1),(3,2)],4) => 40

([(1,3),(2,3)],4) => 48

([(0,3),(1,3),(3,2)],4) => 40

([(0,3),(1,3),(2,3)],4) => 67

([(0,3),(1,2)],4) => 36

([(0,3),(1,2),(1,3)],4) => 31

([(0,2),(0,3),(1,2),(1,3)],4) => 36

([(0,3),(2,1),(3,2)],4) => 35

([(0,3),(1,2),(2,3)],4) => 40

([],5) => 3125

([(3,4)],5) => 750

([(2,3),(2,4)],5) => 325

([(1,2),(1,3),(1,4)],5) => 340

([(0,1),(0,2),(0,3),(0,4)],5) => 629

([(0,2),(0,3),(0,4),(4,1)],5) => 265

([(0,1),(0,2),(0,3),(2,4),(3,4)],5) => 167

([(0,1),(0,2),(0,3),(1,4),(2,4),(3,4)],5) => 178

([(1,3),(1,4),(4,2)],5) => 205

([(0,3),(0,4),(4,1),(4,2)],5) => 221

([(1,2),(1,3),(2,4),(3,4)],5) => 185

([(0,2),(0,3),(2,4),(3,4),(4,1)],5) => 133

([(0,3),(0,4),(3,2),(4,1)],5) => 141

([(0,2),(0,3),(2,4),(3,1),(3,4)],5) => 135

([(0,1),(0,2),(1,3),(1,4),(2,3),(2,4)],5) => 133

([(2,3),(3,4)],5) => 300

([(1,4),(4,2),(4,3)],5) => 205

([(0,4),(4,1),(4,2),(4,3)],5) => 262

([(2,4),(3,4)],5) => 325

([(1,4),(2,4),(4,3)],5) => 205

([(0,4),(1,4),(4,2),(4,3)],5) => 145

([(1,4),(2,4),(3,4)],5) => 340

([(0,4),(1,4),(2,4),(4,3)],5) => 262

([(0,4),(1,4),(2,4),(3,4)],5) => 629

([(0,4),(1,4),(2,3)],5) => 128

([(0,4),(1,3),(2,3),(2,4)],5) => 99

([(0,4),(1,3),(1,4),(2,3),(2,4)],5) => 145

([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4)],5) => 197

([(0,4),(1,4),(2,3),(4,2)],5) => 147

([(0,4),(1,3),(2,3),(3,4)],5) => 221

([(0,4),(1,4),(2,3),(2,4)],5) => 151

([(0,4),(1,4),(2,3),(3,4)],5) => 265

([(1,4),(2,3)],5) => 245

([(1,4),(2,3),(2,4)],5) => 160

([(0,4),(1,2),(1,4),(2,3)],5) => 105

([(0,3),(1,2),(1,3),(2,4),(3,4)],5) => 135

([(1,3),(1,4),(2,3),(2,4)],5) => 185

([(0,3),(0,4),(1,3),(1,4),(4,2)],5) => 130

([(0,3),(0,4),(1,3),(1,4),(3,2),(4,2)],5) => 133

([(0,4),(1,2),(1,4),(4,3)],5) => 129

([(0,4),(1,2),(1,3)],5) => 128

([(0,4),(1,2),(1,3),(1,4)],5) => 151

([(0,2),(0,4),(3,1),(4,3)],5) => 155

([(0,4),(1,2),(1,3),(3,4)],5) => 128

([(0,2),(0,3),(1,4),(2,4),(3,1)],5) => 136

([(0,4),(1,2),(1,3),(2,4),(3,4)],5) => 167

([(0,3),(0,4),(1,2),(1,4)],5) => 99

([(0,3),(0,4),(1,2),(1,3),(1,4)],5) => 145

([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4)],5) => 197

([(0,3),(0,4),(1,2),(1,3),(2,4)],5) => 109

([(0,3),(1,2),(1,4),(3,4)],5) => 105

([(0,3),(0,4),(1,2),(2,3),(2,4)],5) => 130

([(1,4),(3,2),(4,3)],5) => 180

([(0,3),(3,4),(4,1),(4,2)],5) => 147

([(1,4),(2,3),(3,4)],5) => 205

([(0,4),(1,2),(2,4),(4,3)],5) => 154

([(0,3),(1,4),(4,2)],5) => 126

([(0,4),(3,2),(4,1),(4,3)],5) => 154

([(0,4),(1,2),(2,3),(2,4)],5) => 129

([(0,4),(2,3),(3,1),(4,2)],5) => 126

([(0,3),(1,2),(2,4),(3,4)],5) => 141

([(0,4),(1,2),(2,3),(3,4)],5) => 155

([(0,3),(1,4),(2,4),(3,1),(3,2)],5) => 133

([],6) => 46656

([(4,5)],6) => 9072

([(3,4),(3,5)],6) => 3024

([(2,3),(2,4),(2,5)],6) => 2484

([(1,2),(1,3),(1,4),(1,5)],6) => 3780

([(0,1),(0,2),(0,3),(0,4),(0,5)],6) => 7781

([(0,2),(0,3),(0,4),(0,5),(5,1)],6) => 2620

([(0,1),(0,2),(0,3),(0,4),(3,5),(4,5)],6) => 1231

([(0,1),(0,2),(0,3),(0,4),(2,5),(3,5),(4,5)],6) => 1004

([(0,1),(0,2),(0,3),(0,4),(1,5),(2,5),(3,5),(4,5)],6) => 1430

([(1,3),(1,4),(1,5),(5,2)],6) => 1596

([(0,3),(0,4),(0,5),(5,1),(5,2)],6) => 1867

([(1,2),(1,3),(1,4),(3,5),(4,5)],6) => 1008

([(1,2),(1,3),(1,4),(2,5),(3,5),(4,5)],6) => 1074

([(0,2),(0,3),(0,4),(2,5),(3,5),(4,5),(5,1)],6) => 693

>>> Load all 404 entries. <<<

search for individual values

searching the database for the individual values of this statistic

/ search for generating function

searching the database for statistics with the same generating function

click to show known generating functions

$F_{2} = q^{3} + q^{4}$

$F_{3} = q^{10} + 2\ q^{11} + q^{12} + q^{27}$

$F_{4} = q^{31} + q^{35} + 3\ q^{36} + 4\ q^{40} + q^{44} + 2\ q^{48} + 2\ q^{67} + q^{80} + q^{256}$

$F_{5} = 2\ q^{99} + 2\ q^{105} + q^{109} + 2\ q^{126} + 3\ q^{128} + 2\ q^{129} + 2\ q^{130} + 4\ q^{133} + 2\ q^{135} + q^{136} + 2\ q^{141} + 3\ q^{145} + 2\ q^{147} + 2\ q^{151} + 2\ q^{154} + 2\ q^{155} + q^{160} + 2\ q^{167} + q^{178} + q^{180} + 2\ q^{185} + 2\ q^{197} + 4\ q^{205} + 2\ q^{221} + q^{245} + 2\ q^{262} + 2\ q^{265} + q^{300} + 2\ q^{325} + 2\ q^{340} + 2\ q^{629} + q^{750} + q^{3125}$

$F_{6} = q^{234} + q^{275} + q^{290} + q^{302} + 2\ q^{333} + 2\ q^{342} + 2\ q^{362} + q^{373} + 2\ q^{378} + 2\ q^{388} + q^{390} + 2\ q^{396} + 2\ q^{400} + q^{401} + 4\ q^{406} + 2\ q^{410} + 2\ q^{416} + q^{417} + 6\ q^{418} + 2\ q^{421} + 2\ q^{425} + q^{426} + 2\ q^{427} + 2\ q^{433} + 2\ q^{435} + 2\ q^{440} + q^{446} + q^{462} + 2\ q^{466} + 2\ q^{470} + 2\ q^{471} + 2\ q^{472} + q^{473} + 2\ q^{475} + q^{477} + 2\ q^{481} + 2\ q^{484} + q^{488} + 3\ q^{490} + q^{493} + q^{494} + 4\ q^{496} + 2\ q^{499} + 3\ q^{500} + 2\ q^{502} + q^{504} + 4\ q^{509} + 2\ q^{510} + 2\ q^{513} + 2\ q^{515} + 4\ q^{517} + 2\ q^{519} + q^{520} + 2\ q^{521} + 3\ q^{523} + 2\ q^{524} + 2\ q^{528} + 2\ q^{529} + 4\ q^{533} + 2\ q^{538} + 2\ q^{546} + q^{550} + 4\ q^{552} + 2\ q^{555} + 2\ q^{556} + q^{560} + 2\ q^{561} + 2\ q^{562} + 2\ q^{571} + q^{573} + 2\ q^{579} + 2\ q^{581} + 4\ q^{586} + 2\ q^{593} + 2\ q^{600} + q^{603} + 2\ q^{605} + 2\ q^{606} + 2\ q^{610} + 2\ q^{611} + 2\ q^{612} + 2\ q^{619} + 2\ q^{626} + 2\ q^{629} + 2\ q^{636} + 2\ q^{640} + 2\ q^{641} + q^{646} + 6\ q^{650} + 2\ q^{652} + q^{660} + q^{662} + 2\ q^{680} + 2\ q^{692} + 2\ q^{693} + 2\ q^{700} + 4\ q^{704} + 2\ q^{709} + 2\ q^{717} + q^{729} + 2\ q^{737} + 2\ q^{745} + 2\ q^{760} + q^{762} + 2\ q^{763} + 2\ q^{774} + 2\ q^{780} + 2\ q^{783} + 2\ q^{786} + 2\ q^{801} + 4\ q^{804} + 2\ q^{816} + q^{822} + 2\ q^{824} + 2\ q^{832} + 2\ q^{852} + 2\ q^{868} + 2\ q^{874} + 3\ q^{876} + 2\ q^{888} + q^{900} + 2\ q^{901} + 2\ q^{912} + 4\ q^{918} + 2\ q^{930} + 2\ q^{936} + q^{951} + 2\ q^{963} + 2\ q^{970} + 2\ q^{1004} + 2\ q^{1005} + 2\ q^{1008} + 2\ q^{1045} + 2\ q^{1053} + q^{1074} + 2\ q^{1122} + 2\ q^{1167} + 3\ q^{1188} + 2\ q^{1231} + 2\ q^{1291} + 3\ q^{1332} + 2\ q^{1368} + q^{1430} + 4\ q^{1512} + 2\ q^{1578} + 2\ q^{1596} + 2\ q^{1782} + 2\ q^{1867} + 2\ q^{1976} + q^{2304} + 2\ q^{2484} + 2\ q^{2558} + 2\ q^{2620} + q^{2808} + 2\ q^{3024} + 2\ q^{3780} + 2\ q^{7781} + q^{9072} + q^{46656}$

Description

The number of endomorphisms of a poset.

References

[1] Prince, R. Whether a total order set of size $n$ has the fewest endomorphisms among posets of size $n$ MathOverflow:252899

Code

def statistic(P):
    return len(poset_endomorphisms(P))

def poset_endomorphisms(P):
    P = P.relabel()
    r = P.cardinality()
    S = cartesian_product([range(r)]*r)
    return [pi for pi in S if P.is_poset_morphism(lambda i: pi[i], P)]

(* Mathematica code using depth first recursion *)

endoCount::usage := "If rel is a reflexive relation on 1,2,..,Max[rel], then \
endoCount[rel] is the number of self maps f for which {f[a],f[b]} is in the \
relation whenever {a,b} is in the relation.”

endoCount[rel_] := morphismCount[rel, rel]

morphismCount[rel1_List, rel2_List] :=
Module[{max1 = Max[rel1], max2 = Max[rel2], down, checkdown, num, ans},
 Do[down[i] = Select[rel1, Max[#] == i &], {i, max1}];
 checkdown[f_List] := AllTrue[down[Length[f]], MemberQ[rel2, f[[#1]]] &];
 num[{}] := Sum[num[{i}], {i, max2}];
 num[f_List] :=
  If[checkdown[f],
   If[Length[f] == max1, 1, Sum[num[Append[f, i]], {i, max2}]], 0];
 ans = num[{}]; Clear[checkdown, down]; ans]

(* example *)

endoCount[{{1, 1}, {1, 2}, {1, 10}, {2, 2}, {3, 2}, {3, 3}, {3,
  4}, {4, 4}, {5, 4}, {5, 5}, {5, 6}, {6, 6}, {7, 6}, {7, 7}, {7,
  8}, {8, 8}, {9, 8}, {9, 9}, {9, 10}, {10, 10}}]

(* gives 10030 *)

(* Sanity checks are to be added. For instance we must have 
  Union @@ rel == Range[Max[rel]]
*)

Created

Oct 24, 2016 at 12:49 by Martin Rubey

Updated

Nov 13, 2022 at 11:36 by Martin Rubey