A188404 Number of (3*n) X n binary arrays with rows in nonincreasing order, 3 ones in every column and no more than 3 ones in any row.

1, 4, 23, 214, 2698, 44288, 902962, 22262244, 648446612, 21940389584, 849992734124, 37273085398456, 1831837147680872, 100066601315825216, 6031974947471801512, 398733149802770699792, 28744536471179273843088, 2248840133521868856571456, 190105368229118222009348848

Offset

1,2

Comments

Also, number of labeled graphs on n nodes with degree set {2,3}, with multiple edges and loops allowed. - N. J. A. Sloane, Sep 02 2013

Links

Vaclav Kotesovec, Table of n, a(n) for n = 1..320

Frédéric Chyzak, Marni Mishna, Bruno Salvy, Effective Scalar Products for D-finite Symmetric Functions, arXiv:math/0310132v3 (version 2012)

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009, pp. 584-585.

Goulden, I. P. and Jackson, D. M., Labelled graphs with small vertex degrees and $P$-recursiveness, SIAM J. Algebraic Discrete Methods 7(1986), no. 1, 60-66. MR0819706 (87k:05093).

Formula

See Goulden and Jackson for the e.g.f. - N. J. A. Sloane, Sep 02 2013

Recurrence (for n>9): 12*(3*n - 10)*(27*n^3 - 225*n^2 + 483*n - 281)*a(n) = 6*(243*n^5 - 2835*n^4 + 10989*n^3 - 16911*n^2 + 9186*n - 728)*a(n-1) + 9*(n-1)^2*(81*n^5 - 1026*n^4 + 4563*n^3 - 8256*n^2 + 4904*n + 296)*a(n-2) + 3*(n-2)*(n-1)*(81*n^5 - 945*n^4 + 3915*n^3 - 7239*n^2 + 6068*n - 1892)*a(n-3) + (n-3)*(n-2)*(n-1)*(243*n^5 - 2754*n^4 + 10395*n^3 - 14454*n^2 + 4458*n + 1820)*a(n-4) - 4*(n-4)*(n-3)*(n-2)*(n-1)*(81*n^4 - 864*n^3 + 2781*n^2 - 3117*n + 1112)*a(n-5) - (n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(9*n^2 - 60*n + 85)*(27*n^3 - 144*n^2 + 114*n + 4)*a(n-6) + (n-6)*(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(3*n + 2)*(27*n^3 - 225*n^2 + 483*n - 281)*a(n-7) + (n-7)*(n-6)*(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(3*n - 7)*(27*n^3 - 144*n^2 + 114*n + 4)*a(n-8). - Vaclav Kotesovec, Sep 14 2014

Asymptotics (Chyzak, 2003): a(n) ~ c * (n!)^(3/2) * (sqrt(3)/2)^n * exp(sqrt(3*n)) / n^(3/4), where c = 1/sqrt(2) * exp(3/4) / (2*Pi)^(3/4) = 0.37719937314536... . - Vaclav Kotesovec, Sep 14 2014

Example

All solutions for 6 X 2:
..1..1....1..0....1..1....1..1
..1..1....1..0....1..0....1..1
..1..0....1..0....1..0....1..1
..0..1....0..1....0..1....0..0
..0..0....0..1....0..1....0..0
..0..0....0..1....0..0....0..0

Mathematica

max=20; f[x_]:=Sum[a[n]*(x^(n)/n!), {n, 0, max}]; a[0]=1; a[1]=1; coef = CoefficientList[9*x^3*(x^4 - x^2 + x-2)*f''[x] - 3*(x^10 - 2*x^8 + 2*x^6 - 6*x^5 + 8*x^4 + 2*x^3 + 8*x^2 + 16*x - 8)*f'[x] + (x^11 + x^10 - 6*x^9 - 4*x^8 + 11*x^7 - 15*x^6 + 8*x^5 - 2*x^3 + 12*x^2 - 24*x - 24)*f[x], x]; Table[a[n], {n, 0, max}]/.Solve[Thread[coef[[2;; max]]==0]][[1]]//Rest (* Vaclav Kotesovec, Sep 14 2014 *)
Flatten[{1, RecurrenceTable[{-(-7+n) * (-6+n) * (-5+n) * (-4+n) * (-3+n) * (-2+n) * (-1+n) * (-7+3 * n) * (4+114 * n-144 * n^2+27 * n^3) * a[-8+n]-(-6+n) * (-5+n) * (-4+n) * (-3+n) * (-2+n) * (-1+n) * (2+3 * n) * (-281+483 * n-225 * n^2+27 * n^3) * a[-7+n]+(-5+n) * (-4+n) * (-3+n) * (-2+n) * (-1+n) * (85-60 * n+9 * n^2) * (4+114 * n-144 * n^2+27 * n^3) * a[-6+n]+4 * (-4+n) * (-3+n) * (-2+n) * (-1+n) * (1112-3117 * n+2781 * n^2-864 * n^3+81 * n^4) * a[-5+n]-(-3+n) * (-2+n) * (-1+n) * (1820+4458 * n-14454 * n^2+10395 * n^3-2754 * n^4+243 * n^5) * a[-4+n]-3 * (-2+n) * (-1+n) * (-1892+6068 * n-7239 * n^2+3915 * n^3-945 * n^4+81 * n^5) * a[-3+n]-9 * (-1+n)^2 * (296+4904 * n-8256 * n^2+4563 * n^3-1026 * n^4+81 * n^5) * a[-2+n]-6 * (-728+9186 * n-16911 * n^2+10989 * n^3-2835 * n^4+243 * n^5) * a[-1+n]+12 * (-10+3 * n) * (-281+483 * n-225 * n^2+27 * n^3) * a[n]==0, a[2]==4, a[3]==23, a[4]==214, a[5]==2698, a[6]==44288, a[7]==902962, a[8]==22262244, a[9]==648446612}, a, {n, 2, 20}]}] (* Vaclav Kotesovec, Sep 15 2014 *)

Crossrefs

Row 3 of A188403.

Cf. A005814, A228694.

Sequence in context: A265677 A221371 A056785 * A105747 A099692 A283499

Adjacent sequences: A188401 A188402 A188403 * A188405 A188406 A188407

Keyword

nonn

Author

R. H. Hardin, Mar 30 2011

Extensions

More terms from Vaclav Kotesovec, Sep 14 2014

Status

approved