A161132 -id:A161132 - cp's OEIS frontend

A267383 Number A(n,k) of acyclic orientations of the Turán graph T(n,k); square array A(n,k), n>=0, k>=1, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 4, 1, 1, 1, 2, 6, 14, 1, 1, 1, 2, 6, 18, 46, 1, 1, 1, 2, 6, 24, 78, 230, 1, 1, 1, 2, 6, 24, 96, 426, 1066, 1, 1, 1, 2, 6, 24, 120, 504, 2286, 6902, 1, 1, 1, 2, 6, 24, 120, 600, 3216, 15402, 41506, 1

Offset: 0

Alois P. Heinz, Jan 13 2016

An acyclic orientation is an assignment of a direction to each edge such that no cycle in the graph is consistently oriented. Stanley showed that the number of acyclic orientations of a graph G is equal to the absolute value of the chromatic polynomial X_G(q) evaluated at q=-1.

Conjecture: In general, column k > 1 is asymptotic to n! / ((k-1) * (1 - log(k/(k-1)))^((k-1)/2) * k^n * (log(k/(k-1)))^(n+1)). - Vaclav Kotesovec, Feb 18 2017

			Square array A(n,k) begins:
  1,    1,    1,    1,    1,    1,    1, ...
  1,    1,    1,    1,    1,    1,    1, ...
  1,    2,    2,    2,    2,    2,    2, ...
  1,    4,    6,    6,    6,    6,    6, ...
  1,   14,   18,   24,   24,   24,   24, ...
  1,   46,   78,   96,  120,  120,  120, ...
  1,  230,  426,  504,  600,  720,  720, ...
  1, 1066, 2286, 3216, 3720, 4320, 5040, ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened
Richard P. Stanley, Acyclic Orientations of Graphs, Discrete Mathematics, 5 (1973), pages 171-178, doi:10.1016/0012-365X(73)90108-8
Wikipedia, Acyclic orientation
Wikipedia, Turán graph

Columns k=1-10 give: A000012, A266695, A266858, A267384, A267385, A267386, A267387, A267388, A267389, A267390.
Main diagonal gives A000142.
A(2n,n) gives A033815.
A(n,ceiling(n/2)) gives A161132.
Bisection of column k=2 gives A048163.
Trisection of column k=3 gives A370961.
a(n^2,n) gives A372084.

A:= proc(n, k) option remember; local b, l, q; q:=-1;
       l:= [floor(n/k)$(k-irem(n,k)), ceil(n/k)$irem(n,k)];
       b:= proc(n, j) option remember; `if`(j=1, (q-n)^l[1]*
             mul(q-i, i=0..n-1), add(b(n+m, j-1)*
             Stirling2(l[j], m), m=0..l[j]))
           end; forget(b);
       abs(b(0, k))
    end:
seq(seq(A(n, 1+d-n), n=0..d), d=0..14);

A[n_, k_] := A[n, k] = Module[{ b, l, q}, q = -1; l = Join[Array[Floor[n/k] &, k - Mod[n, k]], Array[ Ceiling[n/k] &, Mod[n, k]]]; b[nn_, j_] := b[nn, j] = If[j == 1, (q - nn)^l[[1]]*Product[q - i, {i, 0, nn - 1}], Sum[b[nn + m, j - 1]*StirlingS2[l[[j]], m], {m, 0, l[[j]]}]]; Abs[b[0, k]]]; Table[Table[A[n, 1 + d - n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Feb 22 2016, after Alois P. Heinz *)

A161131 Number of permutations of {1,2,...,n} that have no odd fixed points.

Original entry on oeis.org

1, 0, 1, 3, 14, 64, 426, 2790, 24024, 205056, 2170680, 22852200, 287250480, 3597143040, 52370755920, 760381337520, 12585067447680, 207863095910400, 3854801333416320, 71370457471716480, 1465957162768492800, 30071395843421184000, 677696237345719468800

Offset: 0

Emeric Deutsch, Jul 18 2009

nonn

			a(3)=3 because we have 312, 231, and 321.

Alois P. Heinz, Table of n, a(n) for n = 0..450

Cf. A000166, A068106, A161132.

d[0] := 1: for n to 25 do d[n] := n*d[n-1]+(-1)^n end do: a := proc (n) options operator, arrow: add(d[n-j]*binomial(floor((1/2)*n), j), j = 0 .. floor((1/2)*n)) end proc; seq(a(n), n = 0 .. 22);
a := proc (n) options operator, arrow: add((-1)^j*binomial(ceil((1/2)*n), j)*factorial(n-j), j = 0 .. ceil((1/2)*n)) end proc; seq(a(n), n = 0 .. 22); # Emeric Deutsch, Jul 18 2009
# next Maple program:
a:= proc(n) option remember; `if`(n<4, [1, 0, 1, 3][n+1],
      (8*(n-1)*(2*n-5)*a(n-1)+2*(8*n^4-48*n^3+102*n^2-90*n+29)*a(n-2)
       -2*(2*n-1)*(n-2)*a(n-3)+(2*n-1)*(2*n-3)*(n-2)*(n-3)*a(n-4))
       /(4*(2*n-3)*(2*n-5)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Jul 15 2022
a := n -> n!*hypergeom([-ceil(n/2)], [-n], -1):
seq(simplify(a(n)), n = 0..22);  # Peter Luschny, Jul 15 2022

Table[Sum[(-1)^j*Binomial[Ceiling[n/2], j]*(n-j)!, {j, 0, Ceiling[n/2]}], {n, 0, 30}] (* Vaclav Kotesovec, Feb 18 2017 *)

for(n=0, 30, print1(sum(j=0, ceil(n/2), (-1)^j*binomial(ceil(n/2), j)*(n - j)!),", ")) \\ Indranil Ghosh, Mar 08 2017

a(n) = Sum_{j=0..floor(n/2)} d(n-j)*binomial(floor(n/2), j), where d(i)=A000166(i) are the derangement numbers.
a(n) = Sum_{j=0..ceiling(n/2)} (-1)^j*binomial(ceiling(n/2), j)*(n-j)!. - Emeric Deutsch, Jul 18 2009
a(n) ~ exp(-1/2) * n!. - Vaclav Kotesovec, Feb 18 2017
From Peter Luschny, Jul 15 2022: (Start)
a(n) = n!*hypergeom([-ceiling(n/2)], [-n], -1).
a(n) = A068106(n, floor(n/2)). (End)
D-finite with recurrence +16*a(n) -24*a(n-1) -4*(2*n-1)*(2*n-3)*a(n-2) +4*(2*n^2-10*n+15)*a(n-3) +2*(-10*n+29)*a(n-4) +2*(n-2)*(n-4)*a(n-5) +(n-4)*(n-5)*a(n-6)=0. - R. J. Mathar, Jul 26 2022

A161134 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having exactly k even fixed points (0 <= k <= floor(n/2)).

Original entry on oeis.org

1, 1, 1, 1, 4, 2, 14, 8, 2, 78, 36, 6, 426, 234, 54, 6, 3216, 1512, 288, 24, 24024, 12864, 3024, 384, 24, 229080, 108960, 22320, 2400, 120, 2170680, 1145400, 272400, 37200, 3000, 120, 25022880, 11998800, 2563200, 309600, 21600, 720, 287250480

Offset: 0

Emeric Deutsch, Jul 18 2009

Row n contains 1 + floor(n/2) entries.
Sum of row n is n! = A000142(n).
T(n,0) = A161132(n).
Sum_{k>=0} k*T(n,k) = A052591(n-1).

			T(3,0)=4 because we have 132, 312, 213, 231; T(3,1)=2 because we have 123 and 321.
Triangle starts:
    1;
    1;
    1,   1;
    4,   2;
   14,   8,   2;
   78,  36,   6;
  426, 234,  54,   6;

Indranil Ghosh, Rows 0..125, flattened

Cf. A000142, A052591, A161132, A161133.

T := proc (n, k) options operator, arrow: binomial(floor((1/2)*n), k)*add((-1)^j*binomial(floor((1/2)*n)-k, j)*factorial(n-k-j), j = 0 .. floor((1/2)*n)-k) end proc: for n from 0 to 12 do seq(T(n, k), k = 0 .. floor((1/2)*n)) end do; # yields sequence in triangular form

Flatten[Table[Binomial[Floor[n/2], k]*Sum[(-1)^j*(n - k - j)!*Binomial[Floor[n/2] - k, j], {j, 0, Floor[n/2] - k}],{n, 0, 12}, {k, 0, Floor[n/2]}]] (* Indranil Ghosh, Mar 08 2017 *)

tabf(nn) = { for(n=0, nn, for(k = 0, floor(n/2), print1(binomial(floor(n/2), k) * sum(j=0, floor(n/2) - k, (-1)^j*(n - k - j)! * binomial(floor(n/2) - k, j)),", ");); print();); };
tabf(12); \\ Indranil Ghosh, Mar 08 2017

from sympy import factorial, binomial
def T(n,k):
    s=0
    for j in range(n//2 - k+1):
        s+=(-1)**j * factorial(n-k-j) * binomial(n//2 - k, j)
    return binomial(n//2, k)* s
i=0
for n in range(26):
    for k in range(n//2 + 1):
        print(str(i)+" "+str(T(n,k)))
        i+=1
# Indranil Ghosh, Mar 08 2017

T(n,k) = binomial(floor(n/2), k)*Sum_{j=0..floor(n/2)-k}(-1)^j*(n-k-j)!*binomial(floor(n/2)-k, j).

A187847 Number of permutations p of [n] with p(i) <> i^2.

Original entry on oeis.org

1, 0, 1, 4, 14, 78, 504, 3720, 30960, 256320, 2656080, 30078720, 369774720, 4906137600, 69894316800, 1064341555200, 16190733081600, 279499828608000, 5100017213491200, 98087346669312000, 1983334021853184000, 42063950934061056000, 933754193111900160000

Offset: 0

Alois P. Heinz, Apr 11 2011

nonn

Also number of permutations of [n] that have no square fixed points.

			a(3) = 4: (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1).

Alois P. Heinz, Table of n, a(n) for n = 0..200

Cf. A161131, A161132, A247978.

with(LinearAlgebra):
a:= n-> `if`(n=0, 1, Permanent(Matrix(n, (i, j)-> `if`(j<>i^2, 1, 0)))):
seq(a(n), n=0..15);
# second Maple program:
a:= n->(p->add((-1)^(j)*binomial(p, j)*(n-j)!, j=0..p))(floor(sqrt(n))):
seq(a(n), n=0..25);  # Alois P. Heinz, Nov 02 2014

a[n_] := With[{p = Floor[Sqrt[n]]}, Sum[(-1)^j*Binomial[p, j]*(n-j)!, {j, 0, p}]]; Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 0, 25}] (* Jean-François Alcover, Jan 07 2016, adapted from Maple *)

a(n) = Sum_{j=0..floor(sqrt(n))} (-1)^j*C(floor(sqrt(n)),j)*(n-j)!.

A247978 Number of permutations of [n] that have no prime fixed points.

Original entry on oeis.org

1, 1, 1, 3, 14, 64, 426, 2790, 24024, 229080, 2399760, 25022880, 312273360, 3884393520, 56255149440, 869007242880, 14266826784000, 233845982899200, 4309095479673600, 79300508301907200, 1620482929875532800, 34699018357638835200, 777011144137311283200

Offset: 0

Alois P. Heinz, Nov 02 2014

nonn

			a(2) = 1: 21.
a(3) = 3: 132, 231, 312.
a(4) = 14: 1324, 1342, 1423, 2143, 2314, 2341, 2413, 3124, 3142, 3412, 3421, 4123, 4312, 4321.

Alois P. Heinz, Table of n, a(n) for n = 0..400

Cf. A000720, A161131, A161132, A187847.

with(numtheory):
a:= n-> add((-1)^(j)*binomial(pi(n), j)*(n-j)!, j=0..pi(n)):
seq(a(n), n=0..25);

a[n_] := Sum[(-1)^j*Binomial[PrimePi[n], j]*(n-j)!, {j, 0, PrimePi[n]}]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Feb 26 2017, translated from Maple *)

for(n=0, 25, print1(sum(j=0, primepi(n), (-1)^j*binomial(primepi(n), j)*(n - j)!), ", ")) \\ Indranil Ghosh, Mar 08 2017

a(n) = Sum_{j=0..pi(n)} (-1)^(j)*C(pi(n),j)*(n-j)!, with pi = A000720.

cp's OEIS Frontend

A267383 Number A(n,k) of acyclic orientations of the Turán graph T(n,k); square array A(n,k), n>=0, k>=1, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A161131 Number of permutations of {1,2,...,n} that have no odd fixed points.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A161134 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having exactly k even fixed points (0 <= k <= floor(n/2)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A187847 Number of permutations p of [n] with p(i) <> i^2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A247978 Number of permutations of [n] that have no prime fixed points.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula