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

1, 2, 2, 24, 64, 80, 3408, 9856, 13440, 1377792, 4139520, 5913600, 1191370752, 3659335680, 5381376000, 1878991994880, 5854937088000, 8782405632000, 4877246236262400, 15351645044736000, 23361198981120000, 19383120526049280000, 61467986759122944000

Offset

1,2

Links

Michael De Vlieger, Table of n, a(n) for n = 1..477

C. Coscia, J. DeWitt, F. Yang, Y. Zhang, Online and Random Domination of Graphs, arXiv preprint arXiv:1509.08876 [math.CO], 2015.

Jonathan Dewitt, Christopher Coscia, Fan Yang, Yiguang Zhang, Best and Worst Case Permutations for Random Online Domination of the Path, Discrete Mathematics & Theoretical Computer Science, December 20, 2017, Vol. 19 no. 2, Permutation Patterns 2016.

Formula

Section 4 of Coscia et al. 2015 gives formulas.

Maple

A272641 := proc(n)
    if modp(n, 3) = 0 then
        n!/3^(n/3) ;
    elif modp(n, 3) = 1 then
        if n > 7 then
        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) ;
        elif n = 1 then
            1;
        elif n = 4 then
            24;
        elif n = 7 then
            3408;
        end if;
    else
        if n > 2 then
            24*binomial(n, 5) *(n-5)! /3^((n-5)/3) *(n-2)/3 +2*binomial(n, 2) *(n-2)! /3^((n-2)/3) ;
        else
            2;
        end if;
    end if ;
end proc: # R. J. Mathar, May 11 2016

Mathematica

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]];
Array[a, 23] (* Jean-François Alcover, Dec 03 2017, after R. J. Mathar *)

Prog

(PARI)
a(n) = {
  if (n == 1, return(1));
  my(c=(n, k)->binomial(n, k), b=n->if(n>=0, n!/3^(n\3), 0), r=n%3);
  if (r == 0, b(n), r == 2, 24*c(n, 5)*b(n-5)*((n-2)\3) + 2*c(n, 2)*b(n-2),
  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) +
  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));
};
vector(23, n, a(n)) \\ Gheorghe Coserea, Jun 02 2018

Crossrefs

Cf. A113583, A272640.

Sequence in context: A261517 A131448 A156447 * A334123 A127261 A239531

Adjacent sequences: A272638 A272639 A272640 * A272642 A272643 A272644

Keyword

nonn

Author

N. J. A. Sloane, May 06 2016

Status

approved