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, 48908080, 58990800, 70749393

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 Seq., Vol. 7 (2004), Article 04.1.5.

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

a(n) = (1/20)*n*(n+1)*(n^2+1)*(n^2+2*n+2).

a(n) = 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

Sum_{n>=1} 1/a(n) = 20 - 6*Pi*coth(Pi). - Amiram Eldar, Nov 02 2025

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) my(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, A085462, A085463, A085464.

Sequence in context: A093739 A205431 A383665 * A205424 A384202 A219624

Adjacent sequences: A085462 A085463 A085464 * A085466 A085467 A085468

Keyword

nonn,easy

Author

Goran Kilibarda and Vladeta Jovovic, Jul 01 2003

Status

approved