login
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).
2

%I #39 Feb 17 2024 09:29:40

%S 1,2,7,67,1080,25287,794545,31858034,1573857867,93345011951,

%T 6514819011216,526593974392123,48658721593531669,5084549201524804642,

%U 595348294459678745663,77500341343460209843627,11140107960738185817545800,1757660562895916320583653791

%N 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).

%C Column 2 of A207981.

%C 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

%C 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}.

%C 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

%H Alois P. Heinz, <a href="/A207978/b207978.txt">Table of n, a(n) for n = 0..288</a> (terms n = 1..40 from R. H. Hardin)

%H Rosa Orellana, Nancy Wallace, and Mike Zabrocki, <a href="https://arxiv.org/abs/2306.17326">Representations of the quasi-partition algebras</a>, arXiv:2306.17326 [math.RT], 2023.

%F a(n) = Sum_{s=0..2n} (-1)^s binomial(2n-2,s) Bell(2n-s). - _Mike Zabrocki_, May 23 2023

%F a(n) = A011968(2*n-1) for n>=1. - _Alois P. Heinz_, May 30 2023

%e Some solutions for n=4:

%e ..0..0....0..0....0..0....0..0....0..0....0..0....0..1....0..0....0..0....0..1

%e ..1..1....1..1....1..1....1..1....1..1....1..1....0..1....1..1....1..1....2..1

%e ..2..3....2..0....2..0....2..2....0..2....0..0....0..1....0..2....0..2....0..1

%e ..2..0....3..3....1..0....3..4....3..1....1..1....0..1....3..4....0..1....0..1

%e 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

%p a:=n->add((-1)^s*binomial(2*n-2, s) * combinat[bell](2*n-s), s = 0 .. 2*n); # _Mike Zabrocki_, May 23 2023

%p # second Maple program:

%p b:= proc(n) option remember; `if`(n=0, 1,

%p add(b(n-j)*binomial(n-1, j-1), j=1..n))

%p end:

%p a:= n-> `if`(n=0, 1, b(2*n-1)+b(2*n-2)):

%p seq(a(n), n=0..19); # _Alois P. Heinz_, May 30 2023

%t b[n_] := b[n] = If[n == 0, 1, Sum[b[n-j] Binomial[n-1, j-1], {j, 1, n}]];

%t a[n_] := If[n == 0, 1, b[2n-1] + b[2n-2]];

%t Table[a[n], {n, 0, 19}] (* _Jean-François Alcover_, Feb 17 2024, after _Alois P. Heinz_ *)

%o (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

%Y Cf. A000110, A011968, A207981.

%K nonn

%O 0,2

%A _R. H. Hardin_, Feb 22 2012

%E New description and a formula added by _Mike Zabrocki_, May 23 2023

%E a(0)=1 prepended by _Alois P. Heinz_, May 30 2023