***************************************************************************** * www.FindStat.org - The Combinatorial Statistic Finder * * * * Copyright (C) 2019 The FindStatCrew * * * * This information is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. * ***************************************************************************** ----------------------------------------------------------------------------- Statistic identifier: St001765 ----------------------------------------------------------------------------- Collection: Graphs ----------------------------------------------------------------------------- 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]. ----------------------------------------------------------------------------- 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]] ----------------------------------------------------------------------------- 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() ----------------------------------------------------------------------------- Statistic values: ([],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 ----------------------------------------------------------------------------- Created: Jan 21, 2022 at 17:44 by Martin Rubey ----------------------------------------------------------------------------- Last Updated: Jan 21, 2022 at 17:44 by Martin Rubey