login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A085465 Number of monotone n-weightings of complete bipartite digraph K(3,3). 7
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 26 10:35 EDT 2021. Contains 346294 sequences. (Running on oeis4.)