cp's OEIS Frontend

A193638 Number of permutations of the multiset {1,1,1,2,2,2,3,3,3,...,n,n,n} with no two consecutive terms equal.

%I A193638 #51 Feb 15 2025 16:26:40
%S A193638 1,0,2,174,41304,19606320,16438575600,22278418248240,
%T A193638 45718006789687680,135143407245840698880,553269523327347306412800,
%U A193638 3039044104423605600086688000,21819823367694505460651694873600,200345011881335747639978525387827200
%N A193638 Number of permutations of the multiset {1,1,1,2,2,2,3,3,3,...,n,n,n} with no two consecutive terms equal.
%H A193638 Andrew Woods, <a href="/A193638/b193638.txt">Table of n, a(n) for n = 0..101</a>
%H A193638 H. Eriksson and A. Martin, <a href="https://arxiv.org/abs/1702.04177">Enumeration of Carlitz multipermutations</a>, arXiv:1702.04177 [math.CO], 2017.
%F A193638 a(n) = A190826(n) * n! for n >= 1.
%F A193638 a(n) = A193624(n)/6^n.
%F A193638 a(n) = Sum_{s+t+u=n} (-1)^t*multinomial(n;s,t,u)*(3*s+2*t+u)!/(3!)^s. - _Alexis Martin_, Nov 16 2017
%F A193638 a(n) = (1/6^n) * Sum_{j=0..2*n} Sum_{k=ceiling(j/2)..n} (n+j)! * binomial(2*k, j) * binomial(n, k) * (-3)^(n+k-j). - _Tani Akinari_, Sep 23 2012
%F A193638 a(n) = n*( (3*n-1)*(3*n^2-5*n+4)*a(n-1) +2*(n-1)*(6*n^2-9*n-1)*a(n-2) -4*n*(n-1)*(n-2)*a(n-3) )/(2*n-2). - _Alois P. Heinz_, Jun 05 2013
%e A193638 a(2) = 2 because there are two permutations of {1,1,1,2,2,2} avoiding equal consecutive terms: 121212 and 212121.
%p A193638 a:= proc(n) option remember; `if`(n<3, (n-1)*(3*n-2)/2,
%p A193638     n*((3*n-1)*(3*n^2-5*n+4) *a(n-1) +2*(n-1)*(6*n^2-9*n-1) *a(n-2)
%p A193638     -4*n*(n-1)*(n-2) *a(n-3))/(2*n-2))
%p A193638     end:
%p A193638 seq(a(n), n=0..20);  # _Alois P. Heinz_, Jun 05 2013
%t A193638 a[n_]:= (1/6^n)*Sum[(n+j)!*Binomial[n, k]*Binomial[2k, j]*(-3)^(n+k-j), {j,0,2n}, {k, Ceiling[j/2], n}]; Table[a[n], {n, 0, 13}] (* _Jean-François Alcover_, Jul 22 2017, after _Tani Akinari_ *)
%o A193638 (Maxima) a(n):= (1/6^n)*sum((n+j)!*sum(binomial(n,k)*binomial(2*k,j)* (-3)^(n+k-j), k,ceiling(j/2),n), j,0,2*n); /* _Tani Akinari_, Sep 23 2012 */
%o A193638 (Python)
%o A193638 from sympy.core.cache import cacheit
%o A193638 @cacheit
%o A193638 def a(n): return (n-1)*(3*n-2)//2 if n<3 else n*((3*n-1)*(3*n**2 - 5*n + 4)*a(n-1) + 2*(n-1)*(6*n**2 -9*n-1)*a(n-2) - 4*n*(n-1)*(n-2)*a(n- 3))//(2*n-2)
%o A193638 print([a(n) for n in range(51)]) # _Indranil Ghosh_, Jul 22 2017, formula after Maple code
%o A193638 (Magma)
%o A193638 B:=Binomial;
%o A193638 f:= func< n,j | (&+[B(n,k)*B(2*k,j)*(-3)^(k-j): k in [Ceiling(j/2)..n]]) >;
%o A193638 A193638:= func< n | (-1/2)^n*(&+[Factorial(n+j)*f(n,j): j in [0..2*n]]) >;
%o A193638 [A193638(n): n in [0..30]]; // _G. C. Greubel_, Sep 22 2023
%o A193638 (SageMath)
%o A193638 b=binomial;
%o A193638 def f(j,n): return sum(b(n,k)*b(2*k,j)*(-3)^(k-j) for k in range((j//2),n+1))
%o A193638 def A193638(n): return (-1/2)^n*sum(factorial(n+j)*f(j,n) for j in range(2*n+1))
%o A193638 [A193638(n) for n in range(31)] # _G. C. Greubel_, Sep 22 2023
%Y A193638 Cf. A114938 = similar, with two copies instead of three.
%Y A193638 Cf. A193624 = arrangements of triples with no adjacent siblings.
%Y A193638 Cf. A190826.
%K A193638 nonn
%O A193638 0,3
%A A193638 _Andrew Woods_, Aug 01 2011