login
A272641
Number of permutations of [1..n] that achieve a lower bound on the dominating set.
2
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
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
Sequence in context: A261517 A131448 A156447 * A334123 A127261 A239531
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, May 06 2016
STATUS
approved