A085465 Number of monotone n-weightings of complete bipartite digraph K(3,3).

1, 15, 102, 442, 1443, 3885, 9100, 19188, 37269, 67771, 116754, 192270, 304759, 467481, 696984, 1013608, 1442025, 2011815, 2758078, 3722082, 4951947, 6503365, 8440356, 10836060, 13773565, 17346771, 21661290, 26835382, 33000927, 40304433

Offset: 1

Author

Goran Kilibarda, 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.

a(n) = number of proper mergings of a 3-antichain and an (n-1)-chain. - Henri Mühle, Aug 17 2012

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.
• H. Mühle, Counting Proper Mergings of Chains and Antichains, arXiv:1206.3922 [math.CO], 2012.
• Index entries for linear recurrences with constant coefficients, signature (7,-21,35,-35,21,-7,1).

Crossrefs

Cf. A006003, A006322, A006325, A079547, A085461-A085465.

Programs

Magma

[1/20*n*(n+1)*(n^2+1)*(n^2+2*n+2): n in [1..40]]; // Vincenzo Librandi, Oct 06 2017

Mathematica

Rest[CoefficientList[Series[x*(1 + 4*x + x^2)^2/(1 - x)^7, {x, 0, 50}], x]] (* G. C. Greubel, Oct 06 2017 *)
LinearRecurrence[{7, -21, 35, -35, 21, -7, 1}, {1, 15, 102, 442, 1443, 3885, 9100}, 40] (* Vincenzo Librandi, Oct 06 2017 *)

PARI

x='x+O('x^50); Vec(x*(1+4*x+x^2)^2/(1-x)^7) \\ G. C. Greubel, Oct 06 2017

Formula

a(n) = n + 13*binomial(n, 2) + 60*binomial(n, 3) + 120*binomial(n, 4) + 108*binomial(n, 5) + 36*binomial(n, 6) = 1/20*n*(n+1)*(n^2+1)*(n^2+2*n+2) = Sum_{i=1..n} ((n+1-i)^3-(n-i)^3)*i^3. 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+4*x+x^2)^2/(1-x)^7. - Colin Barker, Apr 01 2012

a(n) = A006003(n)*A006003(n+1)/5 for n>0. - Bruno Berselli, Jun 26 2018