A110706 Number of linear arrangements of n blue, n red and n green items such that there are no adjacent items of the same color.

1, 6, 30, 174, 1092, 7188, 48852, 339720, 2403588, 17236524, 124948668, 913820460, 6732898800, 49918950240, 372104853600, 2786716100592, 20955408717396, 158149624268220, 1197390368733804, 9091866006950892, 69214297980023256, 528150412279712856

Offset: 0

Author

Max Alekseyev, Aug 04 2005

Keywords

• nonn

Comments

The number of circular arrangements is given by A110707 and A110710.

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..1110 (terms 1..200 from Vincenzo Librandi)
• Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems.
• L. Q. Eifler, K. B. Reid Jr., D. P. Roselle, Sequences with adjacent elements unequal, Aequationes Mathematicae (1971), 6 (2-3), 256-262.

Crossrefs

Cf. A110707, A110710.

Programs

Magma

[2*(&+[Binomial(n-1, k)*(Binomial(n-1, k)*Binomial(2*n+1-2*k, n+1) + Binomial(n-1, k+1)*Binomial(2*n-2*k, n+1)): k in [0..Floor(n/2)]]): n in [1..25]]; // G. C. Greubel, Nov 24 2018

Maple

a:= proc(n) option remember; `if`(n<2, 1+5*n,
      ((7*n-4)*a(n-1)+8*(n-2)^2*a(n-2)/(n+1))/n)
    end:
seq(a(n), n=0..21);  # Alois P. Heinz, Sep 09 2023

Mathematica

Table[2*(Sum[Binomial[n-1,k]*(Binomial[n-1,k]*Binomial[2n+1-2k, n+1]+Binomial[n-1,k+1]*Binomial[2n-2k,n+1]),{k,0,Floor[n/2]}]),{n,1,20}] (* Vaclav Kotesovec, Oct 18 2012 *)
Table[2 (Binomial[2 n + 1, n + 1] HypergeometricPFQ[{1 - n, 1 - n, 1/2 - n/2, -(n/2)}, {1, -(1/2) - n, -n}, 1] + (n - 1) Binomial[2 n, n + 1] HypergeometricPFQ[{1 - n, 2 - n, 1/2 - n/2, 1 - n/2}, {2, 1/2 - n, -n}, 1]), {n, 10}] (* Eric W. Weisstein, May 26 2017 *)
RecurrenceTable[{n(n+1)*a[n] == (n+1)*(7*n-4)*a[n-1] +8*(n-2)^2*a[n-2], a[1]==6, a[2]==30}, a, {n, 10}] (* Eric W. Weisstein, May 27 2017 *)

PARI

a(n)=2*sum(k=0,n\2,binomial(n-1,k)*(binomial(n-1,k)*binomial(2*n+1-2*k,n+1)+binomial(n-1,k+1)*binomial(2*n-2*k,n+1)))

Sage

[2*sum(binomial(n-1, k)*(binomial(n-1, k)*binomial(2*n+1-2*k, n+1) + binomial(n-1, k+1)*binomial(2*n-2*k, n+1))  for k in range(1+floor(n/2))) for n in (1..25)] # G. C. Greubel, Nov 24 2018

Formula

a(n) = 2 *( Sum_{k=0..floor(n/2)} binomial(n-1, k) * ( binomial(n-1, k) * binomial(2n+1-2k, n+1) + binomial(n-1, k+1)*binomial(2n-2k, n+1)) ).

a(n) = ((3*n-1)*A000172(n-1) + (3*n+2)*A000172(n))/(n+1).

D-finite with recurrence: n*(n+1)*a(n) = (n+1)*(7*n-4)*a(n-1) + 8*(n-2)^2*a(n-2). - Vaclav Kotesovec, Oct 18 2012

a(n) ~ 9*sqrt(3)*2^(3*n-2)/(Pi*n). - Vaclav Kotesovec, Oct 18 2012

G.f.: (2-x)*(1-8*x)^(-1/3)*(x+1)^(-2/3)*hypergeom([1/3, 1/3],[1],27*x^2/(8*x-1)/(x+1)^2) + 3*x*(2*x-1)^2*(1-8*x)^(-4/3)*(x+1)^(-8/3) * hypergeom([4/3, 4/3],[2],27*x^2/(8*x-1)/(x+1)^2) - 2. - Mark van Hoeij, May 14 2013

a(n) = 6*A190917(n) for n >= 1. - R. J. Mathar, Nov 01 2015

Extensions

a(0)=1 prepended by Alois P. Heinz, Sep 09 2023