***************************************************************************** * 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: St000644 ----------------------------------------------------------------------------- Collection: Integer partitions ----------------------------------------------------------------------------- Description: The number of graphs with given frequency partition. The frequency partition of a graph on $n$ vertices is the partition obtained from its degree sequence by recording and sorting the frequencies of the numbers that occur. For example, the complete graph on $n$ vertices has frequency partition $(n)$. The path on $n$ vertices has frequency partition $(n-2,2)$, because its degree sequence is $(2,\dots,2,1,1)$. The star graph on $n$ vertices has frequency partition is $(n-1, 1)$, because its degree sequence is $(n-1,1,\dots,1)$. There are two graphs having frequency partition $(2,1)$: the path and an edge together with an isolated vertex. ----------------------------------------------------------------------------- References: [1] [[wikipedia:Frequency_partition_of_a_graph]] ----------------------------------------------------------------------------- Code: def statistic(la): """The number of graphs with frequency partition la. The frequency partition of a graph on n vertices is the partition obtained by taking the frequencies of the degrees of its vertices. sage: statistic([2,1]) 2 """ c = 0 la = Partition(la) for G in graphs(la.size()): s = G.degree_sequence() if Partition(sorted([s.count(i) for i in Set(s)], reverse=True)) == la: c += 1 return c ----------------------------------------------------------------------------- Statistic values: [] => 1 [1] => 1 [2] => 2 [1,1] => 0 [3] => 2 [2,1] => 2 [1,1,1] => 0 [4] => 4 [3,1] => 2 [2,2] => 3 [2,1,1] => 2 [1,1,1,1] => 0 [5] => 3 [4,1] => 8 [3,2] => 8 [3,1,1] => 6 [2,2,1] => 7 [2,1,1,1] => 2 [1,1,1,1,1] => 0 [6] => 8 [5,1] => 8 [4,2] => 32 [4,1,1] => 18 [3,3] => 4 [3,2,1] => 34 [3,1,1,1] => 20 [2,2,2] => 16 [2,2,1,1] => 14 [2,1,1,1,1] => 2 [1,1,1,1,1,1] => 0 [7] => 6 [6,1] => 30 [5,2] => 40 [5,1,1] => 60 [4,3] => 42 [4,2,1] => 184 [4,1,1,1] => 82 [3,3,1] => 80 [3,2,2] => 104 [3,2,1,1] => 246 [3,1,1,1,1] => 30 [2,2,2,1] => 84 [2,2,1,1,1] => 54 [2,1,1,1,1,1] => 2 [1,1,1,1,1,1,1] => 0 [8] => 22 [7,1] => 44 [6,2] => 238 [6,1,1] => 210 [5,3] => 66 [5,2,1] => 588 [5,1,1,1] => 622 [4,4] => 160 [4,3,1] => 766 [4,2,2] => 1134 [4,2,1,1] => 1588 [4,1,1,1,1] => 426 [3,3,2] => 342 [3,3,1,1] => 1398 [3,2,2,1] => 1756 [3,2,1,1,1] => 1740 [3,1,1,1,1,1] => 30 [2,2,2,2] => 374 [2,2,2,1,1] => 630 [2,2,1,1,1,1] => 210 [2,1,1,1,1,1,1] => 2 [1,1,1,1,1,1,1,1] => 0 ----------------------------------------------------------------------------- Created: Nov 04, 2016 at 22:15 by Martin Rubey ----------------------------------------------------------------------------- Last Updated: Nov 04, 2016 at 22:15 by Martin Rubey