|
%I #52 Nov 02 2020 11:52:38
%S 0,1,3,31,675,25231,1441923,116914351,12764590275,1805409270031,
%T 321113303226243,70146437009397871,18462286083671614275,
%U 5762225835975165678031,2104263061425865873128963,888881838896989670838028591,430058409024841744606172532675
%N Let X_{m,n}(q) be the chromatic polynomial of the complete bipartite graph K_{m,n}. Then a(n) is the negative of the coefficient of the linear term of X_{n,n}(q).
%C From _Arvind Ayyer_, Oct 25 2020: (Start)
%C Equivalently, a(n) is the number of acyclic orientations with a unique sink in K_{n,n}.
%C a(n) is also the number of toppleable permutations in S_{2n-1}. A toppleable permutation pi in S_{2n-1} satisfies pi_i <= n-1+i for 1 <= i <= n-1 and pi_i >= i-n+1 for n <= i <= 2n-1. The a(3)=3 toppleable permutations in S_3 are 123, 213 and 132. (End)
%H Alois P. Heinz, <a href="/A092552/b092552.txt">Table of n, a(n) for n = 0..238</a>
%H A. Ayyer, D. Hathcock and P. Tetali, <a href="https://arxiv.org/abs/2010.11236"> Toppleable Permutations, Excedances and Acyclic Orientations</a>, arXiv:2010.11236 [math.CO], 2020. For the precise definition of a toppleable permutation.
%F From _Alois P. Heinz_, Apr 30 2012: (Start)
%F a(n) = (-1) * [q] Sum_{j=1..n} (q-j)^n*S2(n,j)*Product_{i=0..j-1} (q-i).
%F a(n) = (-1) * A212084(n,2n-1). (End)
%F E.g.f.: Sum_{n>=1} (1 - exp(-n*x))^n / n. - _Paul D. Hanna_, Dec 06 2012
%F a(n) = Sum_{k=1..n} k!*(k-1)! * Stirling2(n, k)^2. - _Paul D. Hanna_, Dec 30 2012, corrected by _Vaclav Kotesovec_, Jun 21 2013
%F O.g.f.: Sum_{n>=1} n^(n-1) * n! * x^n / Product_{k=1..n} (1 + n*k*x). - _Paul D. Hanna_, Jan 05 2013
%F a(n) = A136126(2*n-1,n), where triangle A136126(n,k) is the number of permutations of {1,2,...,k+n} having excedance set {1,2,...,k}. - _Paul D. Hanna_, Feb 01 2013
%F a(n) ~ sqrt(Pi) * n^(2*n-1/2) / (sqrt(1-log(2)) * exp(2*n) * (log(2))^(2*n)). - _Vaclav Kotesovec_, Nov 07 2014
%F a(n) = A306209(2n-1,n-1) for n > 0. - _Alois P. Heinz_, Feb 01 2019
%e a(2) = 3 since the chromatic polynomial of K_{2,2}(q) is q^4-4*q^3+6*q^2-3*q.
%e E.g.f.: A(x) = x + 3*x^2/2! + 31*x^3/3! + 675*x^4/4! + 25231*x^5/5! +...
%e where A(x) = (1-exp(-x)) + (1-exp(-2*x))^2/2 + (1-exp(-3*x))^3/3 +... - _Paul D. Hanna_, Dec 06 2012
%e O.g.f.: F(x) = x + 3*x^2 + 31*x^3 + 675*x^4 + 25231*x^5 +...
%e where F(x) = x/(1+x) + 2^1*2!*x^2/((1+2*1*x)*(1+2*2*x)) + 3^2*3!*x^3/((1+3*1*x)*(1+3*2*x)*(1+3*3*x)) + 4^3*4!*x^4/((1+4*1*x)*(1+4*2*x)*(1+4*3*x)*(1+4*4*x)) +... - _Paul D. Hanna_, Jan 05 2013
%p a:= n-> -coeff(add(Stirling2(n, k) *mul(q-i, i=0..k-1)
%p *(q-k)^n, k=1..n), q, 1):
%p seq(a(n), n=0..20); # _Alois P. Heinz_, Apr 30 2012
%t Table[Sum[k!*(k-1)!*StirlingS2[n,k]^2,{k,1,n}],{n,0,20}] (* _Vaclav Kotesovec_, Jun 21 2013 *)
%o (PARI) {a(n)=n!*polcoeff(sum(k=1,n,(1-exp(-k*x+x*O(x^n)))^k/k),n)} \\ _Paul D. Hanna_, Dec 06 2012
%o for(n=0,20,print1(a(n),", "))
%o (PARI) {Stirling2(n, k)=n!*polcoeff(((exp(x+x*O(x^n))-1)^k)/k!, n)}
%o {a(n)=if(n<=0, 0, sum(k=1, n, k!*(k-1)! * Stirling2(n, k)^2))} \\ _Paul D. Hanna_, Dec 30 2012
%o for(n=0, 20, print1(a(n), ", "))
%o (PARI) {a(n)=if(n<1,0,polcoeff(sum(m=1, n, m^(m-1)*m!*x^m/prod(k=1, m, 1+m*k*x+x*O(x^n))), n))} \\ _Paul D. Hanna_, Jan 05 2013
%Y Cf. A008277, A212084, A220179, A136126, A306209.
%K nonn
%O 0,3
%A Michael Lugo (mtlugo(AT)mit.edu), Apr 09 2004
|
