A161131 -id:A161131 - cp's OEIS frontend

A334279 Irregular table read by rows: T(n, k) is the coefficient of x^k in the chromatic polynomial of the 1-skeleton of the n-dimensional cross polytope, 0 <= k <= 2n.

0, 0, 1, 0, -3, 6, -4, 1, 0, -64, 154, -137, 58, -12, 1, 0, -2790, 7467, -7852, 4300, -1346, 244, -24, 1, 0, -205056, 593016, -698250, 448015, -175004, 43608, -6990, 700, -40, 1, 0, -22852200, 70164670, -89812001, 64407806, -29113410, 8790285, -1822164, 260868, -25405, 1610, -60, 1

Offset: 1

Peter Kagey, Apr 21 2020

A033815 is the number of acyclic orientations of the n-dimensional cross polytope, which is the absolute value of the chromatic polynomial evaluated at -1.
Sums of absolute values of entries in each row give A033815.
These graphs are chromatically unique, that is, there is no nonisomorphic graph with the same chromatic polynomial.
Conjectures from Peter Kagey, Apr 26 2020: (Start)
T(n,1) = -A161131(2n-1).
T(n,2n-2) = A212689(2n - 1).
T(n,2n-1) = A046092(n-1). (End)

			Table begins:
n/k| 0       1      2       3      4       5     6     7   8   9 10
---+---------------------------------------------------------------
  1| 0       0      1
  2| 0      -3      6      -4      1
  3| 0     -64    154    -137     58     -12     1
  4| 0   -2790   7467   -7852   4300   -1346   244   -24   1
  5| 0 -205056 593016 -698250 448015 -175004 43608 -6990 700 -40  1

Peter Kagey, Table of n, a(n) for n = 1..2600 (first 50 rows)
Chong-Yun Chao and George A. Novacky Jr., On maximally saturated graphs, Discrete Math., 41 (1982), 139-143.
Eric Weisstein's World of Mathematics, Chromatic Polynomial
Eric Weisstein's World of Mathematics, Cocktail Party Graph
Wikipedia, Cross-polytope
Wikipedia, Turán graph

A334278 is analogous for the n-dimensional hypercube.
Cf. A033815, A115400.
Cf. A161131, A212689, A046092.

A161132 Number of permutations of {1,2,...,n} that have no even fixed points.

Original entry on oeis.org

1, 1, 1, 4, 14, 78, 426, 3216, 24024, 229080, 2170680, 25022880, 287250480, 3884393520, 52370755920, 812752093440, 12585067447680, 220448163358080, 3854801333416320, 75225258805132800, 1465957162768492800, 31537353006189676800, 677696237345719468800

Offset: 0

Emeric Deutsch, Jul 18 2009

nonn

			a(3)=4 because we have 132, 312, 213, and 231.

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

Cf. A000166, A033815, A068106, A161131, A267383.

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(ceil((1/2)*n), j), j = 0 .. ceil((1/2)*n)) end proc: seq(a(n), n = 0 .. 22);
a := proc (n) options operator, arrow: add((-1)^j*binomial(floor((1/2)*n), j)*factorial(n-j), j = 0 .. floor((1/2)*n)) end proc; seq(a(n), n = 0 .. 22); # Emeric Deutsch, Jul 18 2009
a := n -> n!*hypergeom([-floor(n/2)], [-n], -1):
seq(simplify(a(n)), n = 0..22);  # Peter Luschny, Jul 15 2022

a[n_] := Sum[Subfactorial[n-j]*Binomial[Ceiling[n/2], j], {j, 0, Ceiling[ n/2]}]; Table[a[n], {n, 0, 22}] (* Jean-François Alcover, Feb 19 2017 *)

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

import math
f=math.factorial
def C(n, r): return f(n)/ f(r)/ f(n - r)
def A161132(n):
    s=0
    for j in range(0, (n/2)+1):
        s += (-1)**j*C(n/2, j)*f(n - j)
    return s # Indranil Ghosh, Mar 08 2017

a(n) = Sum_{j=0..ceiling(n/2)} d(n-j)*binomial(ceiling(n/2), j), where d(i) = A000166(i) are the derangement numbers.
a(n) = Sum_{j=0..floor(n/2)} (-1)^j*binomial(floor(n/2),j)*(n-j)!.
a(n) = A267383(n,ceiling(n/2)). - Alois P. Heinz, Jan 13 2016
a(n) ~ exp(-1/2) * n!. - Vaclav Kotesovec, Feb 18 2017
From Mark van Hoeij, Jul 15 2022: (Start)
a(2*n) = A033815(n),
a(2*n+1) = (A033815(n) + A033815(n+1)/(n+1))/2. (End)
From Peter Luschny, Jul 15 2022: (Start)
a(n) = n!*hypergeom([-floor(n/2)], [-n], -1).
a(n) = A068106(n, ceiling(n/2)). (End)
D-finite with recurrence +16*a(n) -24*a(n-1) +4*(-4*n^2+8*n+3)*a(n-2) +4*(2*n^2-10*n+9)*a(n-3) +2*(-4*n^2+22*n-31)*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

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

Original entry on oeis.org

1, 0, 1, 1, 1, 3, 2, 1, 14, 8, 2, 64, 42, 12, 2, 426, 234, 54, 6, 2790, 1704, 468, 72, 6, 24024, 12864, 3024, 384, 24, 205056, 120120, 32160, 5040, 480, 24, 2170680, 1145400, 272400, 37200, 3000, 120, 22852200, 13024080, 3436200, 544800, 55800

Offset: 0

Emeric Deutsch, Jul 18 2009

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

			T(3,0)=3 because we have 312, 231, 321; T(3,2)=1 because we have 123.
Triangle starts:
    1;
    0,   1;
    1,   1;
    3,   2,  1;
   14,   8,  2;
   64,  42, 12, 2;
  426, 234, 54, 6;

Indranil Ghosh, Rows 0..100, flattened

Cf. A000142, A161131, A052558, A161134.

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

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

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

T(n,k) = binomial(ceiling(n/2), k)*Sum_{j=0..ceiling(n/2)-k} (-1)^j*(n-k-j)!*binomial(ceiling(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

A334279 Irregular table read by rows: T(n, k) is the coefficient of x^k in the chromatic polynomial of the 1-skeleton of the n-dimensional cross polytope, 0 <= k <= 2n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A161132 Number of permutations of {1,2,...,n} that have no even fixed points.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

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