6
\$\begingroup\$

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:

multigraphs corresponding to (3,3,1,1)

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.

\$\endgroup\$
4
\$\begingroup\$

Haskell, 57 bytes

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

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Haskell, 127 bytes

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.

\$\endgroup\$
3
\$\begingroup\$

Haskell, 75 bytes

f(h:t)=sum$f<$>h%t
f[]=1
r%(h:t)=[h-i:x|i<-[0..r],x<-(r-i)%t]
r%_=[[]|r==0]

Try it online!

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.

\$\endgroup\$
  • \$\begingroup\$ i<-[0..h] seems to be the better way to trade time for code length... \$\endgroup\$ – Christian Sievers Oct 29 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.