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

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

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

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

Prog

(PARI) x='x+O('x^50); Vec(x*(1+4*x+x^2)^2/(1-x)^7) \\ G. C. Greubel, Oct 06 2017
(Magma) [1/20*n*(n+1)*(n^2+1)*(n^2+2*n+2): n in [1..40]]; // Vincenzo Librandi, Oct 06 2017

Crossrefs

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

Sequence in context: A111370 A093739 A205431 * A205424 A219624 A219170

Adjacent sequences: A085462 A085463 A085464 * A085466 A085467 A085468

Keyword

nonn,easy

Author

Goran Kilibarda, Vladeta Jovovic, Jul 01 2003

Status

approved