A085464 Number of monotone n-weightings of complete bipartite digraph K(4,2).

1, 19, 134, 586, 1919, 5173, 12124, 25572, 49677, 90343, 155650, 256334, 406315, 623273, 929272, 1351432, 1922649, 2682363, 3677374, 4962706, 6602519, 8671069, 11253716, 14447980, 18364645, 23128911, 28881594, 35780374, 44001091

Offset

1,2

Comments

A monotone n-(vertex) weighting of a digraph D=(V,E) is a function w: V -> {0,1,..,n-1} such that w(v1)<=w(v2) for every arc (v1,v2) from E.

Links

G. C. Greubel, Table of n, a(n) for n = 1..1000

Goran Kilibarda and Vladeta Jovovic, Antichains of Multisets, J. Integer Seqs., Vol. 7, 2004.

Formula

a(n) = n + 17*binomial(n, 2) + 80*binomial(n, 3) + 160*binomial(n, 4) + 144*binomial(n, 5) + 48*binomial(n, 6).

a(n) = (1/30)*n*(n+1)*(2*n^4+4*n^3+6*n^2+4*n-1).

a(n) = Sum_{i=1..n} ((n+1-i)^4-(n-i)^4)*i^2.

a(n) = Sum_{i=1..n} ((n+1-i)^2-(n-i)^2)*i^4.

More generally, number of monotone n-weightings of complete bipartite digraph K(s, t) is Sum_{i=1..n} ((n+1-i)^s-(n-i)^s)*i^t = Sum_{i=1..n} ((n+1-i)^t-(n-i)^t)*i^s.

G.f.: x*(1+x)^2*(1+10*x+x^2)/(1-x)^7. - Colin Barker, Apr 01 2012

a(n) = sum(i=1..n, sum (j=1..n, min(i,j)^4)). - Enrique Pérez Herrero, Jan 16 2013

Mathematica

Table[(1/30)*n*(n+1)*(2*n^4+4*n^3+6*n^2+4*n-1), {n, 1, 50}] (* G. C. Greubel, Oct 07 2017 *)

Prog

(PARI) a(n)=n*(n+1)*(2*n^4+4*n^3+6*n^2+4*n-1)/30 \\ Charles R Greathouse IV, Jan 16 2013
(Magma) [(1/30)*n*(n+1)*(2*n^4+4*n^3+6*n^2+4*n-1): n in [1..25]]; // G. C. Greubel, Oct 07 2017

Crossrefs

Cf. A006322, A006325, A079547, A085461, A085462, A085463, A085465.

Sequence in context: A108673 A041692 A078977 * A215863 A101090 A213122

Adjacent sequences: A085461 A085462 A085463 * A085465 A085466 A085467

Keyword

nonn,easy

Author

Goran Kilibarda and Vladeta Jovovic, Jul 01 2003

Status

approved