A207978 Number of n X 2 nonnegative integer arrays with new values 0 upwards introduced in row major order and no element equal to any diagonal or antidiagonal neighbor (colorings ignoring permutations of colors).

1, 2, 7, 67, 1080, 25287, 794545, 31858034, 1573857867, 93345011951, 6514819011216, 526593974392123, 48658721593531669, 5084549201524804642, 595348294459678745663, 77500341343460209843627, 11140107960738185817545800, 1757660562895916320583653791

Offset

0,2

Comments

Column 2 of A207981.

a(n) is equal to the number of set partitions of {1,2,...,2n} such that k and k+2 do not appear in the same block for any k. - Andrew Howroyd , May 23 2023

a(n) is equal to the number of set partitions of {1,2,...,2n} such that the only sets of size 1 in the set partition are either {1} or {2}.

a(n) is also the dimension of the centralizer algebra End_{S_m}((V^{(m-1,1)}_{S_m})^{\otimes n-1} \otimes V_m ) where V^{(m-1,1)}_{S_m} is an irreducible S_m module indexed by (m-1,1) and V_m is the permutation module for S_m (with the condition that m is sufficiently large). - Mike Zabrocki, May 23 2023

Links

Alois P. Heinz, Table of n, a(n) for n = 0..288 (terms n = 1..40 from R. H. Hardin)

Rosa Orellana, Nancy Wallace, and Mike Zabrocki, Representations of the quasi-partition algebras, arXiv:2306.17326 [math.RT], 2023.

Formula

a(n) = Sum_{s=0..2n} (-1)^s binomial(2n-2,s) Bell(2n-s). - Mike Zabrocki, May 23 2023

a(n) = A011968(2*n-1) for n>=1. - Alois P. Heinz, May 30 2023

Example

Some solutions for n=4:
..0..0....0..0....0..0....0..0....0..0....0..0....0..1....0..0....0..0....0..1
..1..1....1..1....1..1....1..1....1..1....1..1....0..1....1..1....1..1....2..1
..2..3....2..0....2..0....2..2....0..2....0..0....0..1....0..2....0..2....0..1
..2..0....3..3....1..0....3..4....3..1....1..1....0..1....3..4....0..1....0..1
The set partitions of 4 where at most {1} and {2} are the only sets of size 1 are {1234}, {1|234}, {2|134}, {12|34}, {13|24}, {14|23}, {1|2|34} - Mike Zabrocki, May 23 2023

Maple

a:=n->add((-1)^s*binomial(2*n-2, s) * combinat[bell](2*n-s), s = 0 .. 2*n); # Mike Zabrocki, May 23 2023
# second Maple program:
b:= proc(n) option remember; `if`(n=0, 1,
      add(b(n-j)*binomial(n-1, j-1), j=1..n))
    end:
a:= n-> `if`(n=0, 1, b(2*n-1)+b(2*n-2)):
seq(a(n), n=0..19);  # Alois P. Heinz, May 30 2023

Mathematica

b[n_] := b[n] = If[n == 0, 1, Sum[b[n-j] Binomial[n-1, j-1], {j, 1, n}]];
a[n_] := If[n == 0, 1, b[2n-1] + b[2n-2]];
Table[a[n], {n, 0, 19}] (* Jean-François Alcover, Feb 17 2024, after Alois P. Heinz *)

Prog

(Sage) a = lambda n: sum((-1)**s*binomial(2*n-2, s)*bell_number(2*n-s) for s in range(2*n-2+1)) # Mike Zabrocki, May 23 2023

Crossrefs

Cf. A000110, A011968, A207981.

Sequence in context: A133237 A099660 A341088 * A307246 A225156 A260968

Adjacent sequences: A207975 A207976 A207977 * A207979 A207980 A207981

Keyword

nonn

Author

R. H. Hardin, Feb 22 2012

Extensions

New description and a formula added by Mike Zabrocki, May 23 2023

a(0)=1 prepended by Alois P. Heinz, May 30 2023

Status

approved