- FindStat

Identifier

St000644: Integer partitions ⟶ ℤ

Values

=>
                            Cc0002;cc-rep
                            
                            
                            

                        []=>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
                    

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

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

Created

Nov 04, 2016 at 22:15 by Martin Rubey

Updated

Nov 04, 2016 at 22:15 by Martin Rubey