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.

1, 1, 4, 19, 57, 178, 543, 1591, 4598, 13117, 36999, 103514, 287653, 794847, 2186054, 5988339, 16347999, 44497490, 120804023, 327217525, 884531586, 2386747391, 6429784509, 17296261734, 46465809007, 124678595953, 334173980818, 894778164125

Offset: 1

Author

Zerinvary Lajos (with help from Miklos Kristof), Oct 07 2004

Keywords

• nonn
• nice

Comments

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, ...

Examples

			For n=1, U = 12 and only one V, 12 is a 1-match, so a(1)=1.
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.
For n=3, U = 111222 and only the four V's 112212, 121122, 121221 and 221211 are 1-matches, so a(3)=4.
		

Crossrefs

Cf. A051292.

Programs

Maple

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

Python

def find(bits_in, n0, n1, match):
    global count, U
    bitsleft = n0 + n1
    if bitsleft==0:
        if match:
            count += 1
    else:
        bitsleft -= 1
        if n0 > 0:
            bits_out = bits_in<<1
            new_match = (bits_out&3) == ((U >> bitsleft)&3)
            if not (match and new_match):
                find(bits_out, n0-1, n1, match or new_match)
        if n1 > 0:
            bits_out = (bits_in<<1)|1;
            new_match = (bits_out&3) == ((U >> bitsleft)&3)
            if not (match and new_match):
                find(bits_out, n0, n1-1, match or new_match)
def A098813(n):
    global count, U
    count = 0 ; U = (1<Bert Dobbelaere, Dec 23 2018

Extensions

a(13)-a(15) from Ray Chandler, Oct 25 2004

a(16)-a(28) from Bert Dobbelaere, Dec 24 2018