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

Author

Goran Kilibarda and Vladeta Jovovic, Jul 01 2003

Keywords

• nonn
• easy

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.

Crossrefs

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

Programs

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

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 *)

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

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