cp's OEIS Frontend

A098813 For a string of letters of length k, say abc...def, let f(k) be the string of length k-1 consisting of the adjacent pairs ab, bc, cd, ..., de, ef. Given n, let U be the string of length 2n consisting of n 1's followed by n 2's: 11...122...2. Then a(n) is the number of the C(2n,n) permutations V of U such that f(U) and f(V) agree in exactly one place.

%I A098813 #28 May 22 2025 10:21:35
%S A098813 1,1,4,19,57,178,543,1591,4598,13117,36999,103514,287653,794847,
%T A098813 2186054,5988339,16347999,44497490,120804023,327217525,884531586,
%U A098813 2386747391,6429784509,17296261734,46465809007,124678595953,334173980818,894778164125
%N A098813 For a string of letters of length k, say abc...def, let f(k) be the string of length k-1 consisting of the adjacent pairs ab, bc, cd, ..., de, ef. Given n, let U be the string of length 2n consisting of n 1's followed by n 2's: 11...122...2. Then a(n) is the number of the C(2n,n) permutations V of U such that f(U) and f(V) agree in exactly one place.
%C A098813 The number of V's such that f(U) and f(V) agree in no positions gives the A051292(n+1) sequence (Whitney numbers): 1, 4, 9, 21, 52, 127, 313, 778, 1941, 4863, 12228, 30817, ...
%e A098813 For n=1, U = 12 and only one V, 12 is a 1-match, so a(1)=1.
%e A098813 For n=2, U = 1122, f(U) = 11,12,22 and only one V, 2121 is a 1-match, with f(v) = 21,12,21, so a(2)=1.
%e A098813 For n=3, U = 111222 and only the four V's 112212, 121122, 121221 and 221211 are 1-matches, so a(3)=4.
%p A098813 with(combinat): for n from 1 to 10 do y:=0:B:=array: M:=[seq(11,i=1..n-1),seq(12,i=n),seq(22,i=n+1..2*n-1)]: S:=[seq(i,i=1..2*n)]: L:=choose(S,n): for j from 1 to binomial(2*n,n) do for k from 1 to 2*n-1 do if member(k,L[j]) then B[k]:=10 else B[k]:=20 end if: if member(k+1,L[j]) then B[k]:=B[k]+1 else B[k]:=B[k]+2 end if end do: x:=0: for l from 1 to 2*n-1 do if B[l]=M[l] then x:=x+1 end if end do: if x=1 then y:=y+1 end if end do: print(y) end do: # _Miklos Kristof_, Oct 07 2004
%o A098813 (Python)
%o A098813 def find(bits_in, n0, n1, match):
%o A098813     global count, U
%o A098813     bitsleft = n0 + n1
%o A098813     if bitsleft==0:
%o A098813         if match:
%o A098813             count += 1
%o A098813     else:
%o A098813         bitsleft -= 1
%o A098813         if n0 > 0:
%o A098813             bits_out = bits_in<<1
%o A098813             new_match = (bits_out&3) == ((U >> bitsleft)&3)
%o A098813             if not (match and new_match):
%o A098813                 find(bits_out, n0-1, n1, match or new_match)
%o A098813         if n1 > 0:
%o A098813             bits_out = (bits_in<<1)|1;
%o A098813             new_match = (bits_out&3) == ((U >> bitsleft)&3)
%o A098813             if not (match and new_match):
%o A098813                 find(bits_out, n0, n1-1, match or new_match)
%o A098813 def A098813(n):
%o A098813     global count, U
%o A098813     count = 0 ; U = (1<<n)-1
%o A098813     find(0, n-1, n, False)
%o A098813     find(1, n, n-1, False)
%o A098813     return count
%o A098813 # _Bert Dobbelaere_, Dec 23 2018
%Y A098813 Cf. A051292.
%K A098813 nonn,nice
%O A098813 1,3
%A A098813 _Zerinvary Lajos_ (with help from _Miklos Kristof_), Oct 07 2004
%E A098813 a(13)-a(15) from _Ray Chandler_, Oct 25 2004
%E A098813 a(16)-a(28) from _Bert Dobbelaere_, Dec 24 2018