Values
=>
Cc0020;cc-rep
([],1)=>1
([],2)=>2
([(0,1)],2)=>1
([],3)=>6
([(1,2)],3)=>5
([(0,2),(1,2)],3)=>2
([(0,1),(0,2),(1,2)],3)=>1
([],4)=>24
([(2,3)],4)=>22
([(1,3),(2,3)],4)=>16
([(0,3),(1,3),(2,3)],4)=>6
([(0,3),(1,2)],4)=>18
([(0,3),(1,2),(2,3)],4)=>8
([(1,2),(1,3),(2,3)],4)=>10
([(0,3),(1,2),(1,3),(2,3)],4)=>2
([(0,2),(0,3),(1,2),(1,3)],4)=>2
([(0,2),(0,3),(1,2),(1,3),(2,3)],4)=>1
([(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)],4)=>1
([],5)=>120
([(3,4)],5)=>114
([(2,4),(3,4)],5)=>96
([(1,4),(2,4),(3,4)],5)=>66
([(0,4),(1,4),(2,4),(3,4)],5)=>24
([(1,4),(2,3)],5)=>98
([(1,4),(2,3),(3,4)],5)=>68
([(0,1),(2,4),(3,4)],5)=>74
([(2,3),(2,4),(3,4)],5)=>74
([(0,4),(1,4),(2,3),(3,4)],5)=>32
([(1,4),(2,3),(2,4),(3,4)],5)=>42
([(0,4),(1,4),(2,3),(2,4),(3,4)],5)=>7
([(1,3),(1,4),(2,3),(2,4)],5)=>34
([(0,4),(1,2),(1,3),(2,4),(3,4)],5)=>8
([(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>21
([(0,4),(1,3),(2,3),(2,4),(3,4)],5)=>12
([(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>2
([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4)],5)=>2
([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>1
([(0,4),(1,3),(2,3),(2,4)],5)=>42
([(0,1),(2,3),(2,4),(3,4)],5)=>46
([(0,3),(1,2),(1,4),(2,4),(3,4)],5)=>16
([(0,3),(0,4),(1,2),(1,4),(2,4),(3,4)],5)=>3
([(0,3),(0,4),(1,2),(1,4),(2,3)],5)=>20
([(0,1),(0,4),(1,3),(2,3),(2,4),(3,4)],5)=>2
([(0,3),(0,4),(1,2),(1,4),(2,3),(2,4),(3,4)],5)=>1
([(0,4),(1,2),(1,3),(2,3),(2,4),(3,4)],5)=>3
([(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>17
([(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>2
([(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>1
([(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4)],5)=>1
([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,4),(3,4)],5)=>1
([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>1
([(0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>1
([],6)=>720
([(4,5)],6)=>696
([(3,5),(4,5)],6)=>624
([(2,5),(3,5),(4,5)],6)=>504
([(1,5),(2,5),(3,5),(4,5)],6)=>336
([(0,5),(1,5),(2,5),(3,5),(4,5)],6)=>120
([(2,5),(3,4)],6)=>628
([(2,5),(3,4),(4,5)],6)=>508
([(1,2),(3,5),(4,5)],6)=>520
([(3,4),(3,5),(4,5)],6)=>528
([(1,5),(2,5),(3,4),(4,5)],6)=>352
([(0,1),(2,5),(3,5),(4,5)],6)=>372
([(2,5),(3,4),(3,5),(4,5)],6)=>388
([(0,5),(1,5),(2,5),(3,4),(4,5)],6)=>156
([(1,5),(2,5),(3,4),(3,5),(4,5)],6)=>221
([(0,5),(1,5),(2,5),(3,4),(3,5),(4,5)],6)=>33
([(2,4),(2,5),(3,4),(3,5)],6)=>356
([(0,5),(1,5),(2,4),(3,4)],6)=>400
([(1,5),(2,3),(2,4),(3,5),(4,5)],6)=>196
([(0,5),(1,5),(2,3),(3,4),(4,5)],6)=>220
([(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>270
([(1,5),(2,4),(3,4),(3,5),(4,5)],6)=>228
([(0,5),(1,5),(2,4),(3,4),(4,5)],6)=>184
([(0,5),(1,5),(2,3),(2,4),(3,5),(4,5)],6)=>36
([(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>123
([(0,5),(1,5),(2,4),(3,4),(3,5),(4,5)],6)=>65
([(0,5),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>7
([(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6)=>68
([(0,5),(1,4),(2,4),(2,5),(3,4),(3,5)],6)=>72
([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6)=>4
([(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>46
([(0,5),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>14
([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6)=>2
([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1
([(0,5),(1,4),(2,3)],6)=>534
([(1,5),(2,4),(3,4),(3,5)],6)=>372
([(0,1),(2,5),(3,4),(4,5)],6)=>394
([(1,2),(3,4),(3,5),(4,5)],6)=>392
([(0,5),(1,4),(2,3),(3,5),(4,5)],6)=>214
([(1,4),(2,3),(2,5),(3,5),(4,5)],6)=>238
([(0,1),(2,5),(3,4),(3,5),(4,5)],6)=>254
([(0,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6)=>79
([(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6)=>133
([(0,5),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6)=>11
([(1,4),(1,5),(2,3),(2,5),(3,4)],6)=>220
([(0,5),(1,4),(2,3),(2,4),(3,5),(4,5)],6)=>66
([(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6)=>96
([(0,5),(1,2),(1,4),(2,3),(3,5),(4,5)],6)=>106
([(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6)=>126
([(0,5),(1,4),(2,3),(3,4),(3,5),(4,5)],6)=>90
([(0,5),(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6)=>6
([(0,5),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>21
([(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6)=>53
([(0,5),(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,5),(1,4),(2,3),(2,4),(3,5)],6)=>258
([(0,1),(2,4),(2,5),(3,4),(3,5)],6)=>242
([(0,5),(1,5),(2,3),(2,4),(3,4)],6)=>273
([(0,4),(1,2),(1,3),(2,5),(3,5),(4,5)],6)=>98
([(0,4),(1,2),(1,5),(2,5),(3,4),(3,5)],6)=>139
([(0,4),(1,2),(2,5),(3,4),(3,5),(4,5)],6)=>114
([(0,1),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>143
([(0,4),(1,4),(2,3),(2,5),(3,5),(4,5)],6)=>101
([(0,3),(0,4),(1,2),(1,5),(2,5),(3,5),(4,5)],6)=>10
([(0,3),(1,4),(1,5),(2,4),(2,5),(3,5),(4,5)],6)=>32
([(0,4),(1,2),(1,5),(2,5),(3,4),(3,5),(4,5)],6)=>32
([(0,1),(0,5),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>210
([(0,5),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6)=>12
([(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>81
([(0,5),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>7
([(0,1),(0,5),(1,4),(2,4),(2,5),(3,4),(3,5)],6)=>16
([(0,3),(0,5),(1,3),(1,5),(2,4),(2,5),(3,4),(4,5)],6)=>1
([(0,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,4),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6)=>2
([(0,1),(0,5),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,4),(0,5),(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6)=>1
([(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>2
([(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>30
([(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>9
([(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,4),(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>1
([(0,4),(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1
([(0,5),(1,3),(1,4),(2,3),(2,4),(3,5),(4,5)],6)=>6
([(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>34
([(0,5),(1,3),(1,4),(2,3),(2,4),(2,5),(3,5),(4,5)],6)=>2
([(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6)=>27
([(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6)=>2
([(0,4),(0,5),(1,2),(1,3),(2,5),(3,4)],6)=>156
([(0,3),(0,5),(1,2),(1,5),(2,4),(3,4),(4,5)],6)=>15
([(0,5),(1,2),(1,4),(2,3),(3,4),(3,5),(4,5)],6)=>24
([(0,1),(0,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6)=>45
([(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>36
([(0,5),(1,3),(1,4),(2,4),(2,5),(3,4),(3,5)],6)=>19
([(0,1),(0,5),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,4),(1,3),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6)=>5
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(3,5),(4,5)],6)=>3
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6)=>1
([(0,4),(0,5),(1,2),(1,3),(2,4),(2,5),(3,4),(3,5)],6)=>2
([(0,5),(1,2),(1,3),(1,4),(2,3),(2,4),(3,5),(4,5)],6)=>3
([(0,4),(0,5),(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5)],6)=>1
([(0,4),(0,5),(1,2),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1
([(0,4),(0,5),(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1
([(0,5),(1,2),(1,3),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>26
([(0,5),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,4),(0,5),(1,2),(1,4),(2,3),(2,5),(3,4),(3,5),(4,5)],6)=>1
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6)=>1
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1
([(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1
([(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)],6)=>2
([(0,1),(0,2),(0,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1
([(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>1
([(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6)=>1
([(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1
([(0,4),(0,5),(1,2),(1,3),(2,3),(4,5)],6)=>164
([(0,2),(1,4),(1,5),(2,3),(3,4),(3,5),(4,5)],6)=>50
([(0,1),(0,5),(1,5),(2,3),(2,4),(3,4),(4,5)],6)=>54
([(0,1),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>101
([(0,1),(0,5),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6)=>5
([(0,1),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>25
([(0,1),(0,5),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,4),(0,5),(1,2),(1,3),(2,3),(2,5),(3,4),(4,5)],6)=>6
([(0,4),(0,5),(1,2),(1,3),(1,4),(2,3),(2,5),(3,5),(4,5)],6)=>1
([(0,3),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,3),(0,5),(1,2),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1
([(0,1),(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,3),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6)=>1
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4)],6)=>2
([(0,1),(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>6
([(0,3),(0,4),(1,2),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6)=>1
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6)=>1
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,5),(3,4)],6)=>2
([(0,1),(0,3),(0,5),(1,2),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1
([(0,4),(0,5),(1,2),(1,3),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6)=>1
([(0,1),(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1
([(0,2),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6)=>1
([(0,4),(0,5),(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1
([(0,4),(0,5),(1,2),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1
([(0,5),(1,2),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>26
([(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1
([(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>1
([(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>1
([(0,1),(0,4),(0,5),(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1
([(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6)=>1
([(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6)=>1
([(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1
([(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1
([(0,1),(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1
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
Description
The number of connected components of the friends and strangers graph.
Let $X$ and $Y$ be graphs with the same vertex set $\{1,\dots,n\}$. Then the friends-and-strangers graph has as vertex set the set of permutations $\mathfrak S_n$ and edges $\left(\sigma, (i, j)\circ\sigma\right)$ if $(i, j)$ is an edge of $X$ and $\left(\sigma(i), \sigma(j)\right)$ is an edge of $Y$.
This statistic is the number of connected components of the friends and strangers graphs where $X=Y$.
For example, if $X$ is a complete graph the statistic is $1$, if $X$ has no edges, the statistic is $n!$, and if $X$ is the path graph, the statistic is
$$ \sum_{k=0}^{\lfloor n/2\rfloor} (-1)^k (n-k)!\binom{n-k}{k}, $$
see [thm. 2.2, 3].
Let $X$ and $Y$ be graphs with the same vertex set $\{1,\dots,n\}$. Then the friends-and-strangers graph has as vertex set the set of permutations $\mathfrak S_n$ and edges $\left(\sigma, (i, j)\circ\sigma\right)$ if $(i, j)$ is an edge of $X$ and $\left(\sigma(i), \sigma(j)\right)$ is an edge of $Y$.
This statistic is the number of connected components of the friends and strangers graphs where $X=Y$.
For example, if $X$ is a complete graph the statistic is $1$, if $X$ has no edges, the statistic is $n!$, and if $X$ is the path graph, the statistic is
$$ \sum_{k=0}^{\lfloor n/2\rfloor} (-1)^k (n-k)!\binom{n-k}{k}, $$
see [thm. 2.2, 3].
References
[1] Defant, C., Kravitz, N. Friends and Strangers Walking on Graphs arXiv:2009.05040
[2] Alon, N., Defant, C., Kravitz, N. Typical and Extremal Aspects of Friends-and-Strangers Graphs arXiv:2009.07840
[3] Stanley, R. P. An equivalence relation on the symmetric group and multiplicity-free flag $h$-vectors MathSciNet:3029438
[2] Alon, N., Defant, C., Kravitz, N. Typical and Extremal Aspects of Friends-and-Strangers Graphs arXiv:2009.07840
[3] Stanley, R. P. An equivalence relation on the symmetric group and multiplicity-free flag $h$-vectors MathSciNet:3029438
Code
def FS(X, Y):
n = X.num_verts()
assert n == Y.num_verts()
X = X.relabel(inplace=False)
Y = Y.relabel(inplace=False)
V = list(Permutations(n))
E = []
for pi in V:
for i, j in X.edges(labels=False):
a, b = pi[i], pi[j]
if Y.has_edge(a-1, b-1):
pi1 = list(pi)
pi1[i], pi1[j] = b, a
pi1 = Permutation(pi1)
E.append((pi, pi1))
return Graph([V, E]).copy(immutable=True)
def statistic(G):
return FS(G, G).connected_components_number()
Created
Jan 21, 2022 at 17:44 by Martin Rubey
Updated
Jan 21, 2022 at 17:44 by Martin Rubey
searching the database
Sorry, this statistic was not found in the database
or
add this statistic to the database – it's very simple and we need your support!