A272641 - OEIS

%I #25 Jun 02 2018 13:07:03

%S 1,2,2,24,64,80,3408,9856,13440,1377792,4139520,5913600,1191370752,

%T 3659335680,5381376000,1878991994880,5854937088000,8782405632000,

%U 4877246236262400,15351645044736000,23361198981120000,19383120526049280000,61467986759122944000

%N Number of permutations of [1..n] that achieve a lower bound on the dominating set.

%H Michael De Vlieger, <a href="/A272641/b272641.txt">Table of n, a(n) for n = 1..477</a>

%H C. Coscia, J. DeWitt, F. Yang, Y. Zhang, <a href="http://arxiv.org/abs/1509.08876">Online and Random Domination of Graphs</a>, arXiv preprint arXiv:1509.08876 [math.CO], 2015.

%H Jonathan Dewitt, Christopher Coscia, Fan Yang, Yiguang Zhang, <a href="https://dmtcs.episciences.org/4145">Best and Worst Case Permutations for Random Online Domination of the Path</a>, Discrete Mathematics & Theoretical Computer Science, December 20, 2017, Vol. 19 no. 2, Permutation Patterns 2016.

%F Section 4 of Coscia et al. 2015 gives formulas.

%p A272641 := proc(n)

%p     if modp(n,3) = 0 then

%p         n!/3^(n/3) ;

%p     elif modp(n,3) = 1 then

%p         if n > 7 then

%p         720*binomial(n,7)*(n-4)/3*(n-7)!/3^((n-7)/3)

%p         +2*(24*binomial(n,2)*binomial(n-2,5)*(n-7)!/3^((n-7)/3) *(n-4)/3 +9*binomial(n,4) *(n-4)! /3^((n-4)/3) )

%p         +6*binomial(n,4)*(n-4)!/3^((n-4)/3)

%p         +24^2 *binomial(10,5) *binomial(n,10) *binomial((n-4)/3,2) *(n-10)! /3^((n-10)/3) ;

%p         elif n = 1 then

%p             1;

%p         elif n = 4 then

%p             24;

%p         elif n = 7 then

%p             3408;

%p         end if;

%p     else

%p         if n > 2 then

%p             24*binomial(n,5) *(n-5)! /3^((n-5)/3) *(n-2)/3 +2*binomial(n,2) *(n-2)! /3^((n-2)/3) ;

%p         else

%p             2;

%p         end if;

%p     end if ;

%p end proc: # _R. J. Mathar_, May 11 2016

%t a[n_] := Which[Mod[n, 3] == 0, n!/3^(n/3), Mod[n, 3] == 1, Which[n > 7, 720*Binomial[n, 7]*(n - 4)/3*(n - 7)!/3^((n - 7)/3) + 2*(24*Binomial[n, 2]*Binomial[n - 2, 5]*(n - 7)!/3^((n - 7)/3)*(n - 4)/3 + 9*Binomial[n, 4] *(n - 4)! /3^((n - 4)/3)) + 6*Binomial[n, 4]*(n - 4)!/3^((n - 4)/3) + 24^2 *Binomial[10, 5]*Binomial[n, 10]*Binomial[(n - 4)/3, 2]*(n - 10)! /3^((n - 10)/3), n == 1, 1, n == 4, 24, n == 7, 3408], True, If[n > 2, 24*Binomial[n, 5]*(n - 5)! /3^((n - 5)/3)*(n - 2)/3 + 2*Binomial[n, 2] * (n - 2)! /3^((n - 2)/3), 2]];

%t Array[a, 23] (* _Jean-François Alcover_, Dec 03 2017, after _R. J. Mathar_ *)

%o (PARI)

%o a(n) = {

%o   if (n == 1, return(1));

%o   my(c=(n,k)->binomial(n,k), b=n->if(n>=0, n!/3^(n\3), 0), r=n%3);

%o   if (r == 0, b(n), r == 2, 24*c(n,5)*b(n-5)*((n-2)\3) + 2*c(n,2)*b(n-2),

%o   720*c(n,7)*((n-4)\3)*b(n-7) + 24^2*c(10,5)*c(n,10)*c((n-4)\3,2)*b(n-10) +

%o   6*c(n,4)*b(n-4) + 18*c(n,4)*b(n-4) + 48*c(n,2)*c(n-2,5)*b(n-7)*((n-4)\3));

%o };

%o vector(23, n, a(n)) \\ _Gheorghe Coserea_, Jun 02 2018

%Y Cf. A113583, A272640.

%K nonn

%O 1,2

%A _N. J. A. Sloane_, May 06 2016