# Multigraphs with a given degree sequence

This challenge will give you an input of a degree sequence in the form of a partition of an even number. Your goal will be to write a program that will output the number of loop-free labeled multigraphs that have this degree sequence.

## Example

For example, given the input [3,3,1,1], you should output the number of labeled multigraphs on four vertices $$\\{v_1, v_2, v_3, v_4\}\$$ such that $$\\deg(v_1) = \deg(v_2) = 3\$$ and $$\\deg(v_3) = \deg(v_4) = 1\$$. In this example, there are three such multigraphs:

See Gus Wiseman's links on OEIS sequence A209816 for more examples.

## Target data

input           | output
----------------+--------
[6,2]           | 0
[5,3,2]         | 1
[3,3,1,1]       | 3
[4,3,1,1,1]     | 6
[4,2,1,1,1,1]   | 10
[1,1,1,1,1,1]   | 15
[3,2,2,2,1]     | 15
[2,2,2,2,2]     | 22
[7,6,5,4,3,2,1] | 7757


# Challenge

This is so shortest code in bytes wins.

f(h:t)=sum[f l|l<-mapM(\n->[0..n])t,sum t-sum l==h]
f _=1


Try it online!

e=[]:e
h a b=mapM id$b<$a
f a=length[0|x<-h a$h a[0..maximum a],x==foldr(zipWith(:))e x,all(<1)$zipWith(!!)x[0..],map sum x==a]


Try it online!

Very very inefficient (superexponential), but I believe it should work in theory. Exceeds Tio's 60 second limit with [3, 3, 1, 1] as input, but works with [1, 1, 1, 1].

Considers the adjacency matrices of the multigraphs.

h a$h a[0..maximum a] is a list of all square matrices with entries between 0 and maximum a, with size length a. x==foldr(zipWith(:))e x checks if a matrix is symmetric. all(<1)$zipWith(!!)x[0..] checks that the diagonal entries are zero, since there are no loops.

map sum x==a checks that each vertex has the proper degree.

f(h:t)=sum$f<$>h%t

It's faster (and easier to understand) when i<-[0..r] is replaced by i<-[0..min r h]. Also, it's faster to give the degrees (whose order obviously doesn't matter) in increasing order.
• i<-[0..h] seems to be the better way to trade time for code length... Oct 29 '19 at 20:20