A108958 Number of unordered pairs of distinct length-n binary words having the same number of 1's.

0, 1, 6, 27, 110, 430, 1652, 6307, 24054, 91866, 351692, 1350030, 5196204, 20050108, 77542376, 300507427, 1166737574, 4537436578, 17672369756, 68922740122, 269127888644, 1052047384708, 4116711169496, 16123793452942, 63205286441660, 247959232919620, 973469645715192

Offset: 1

Author

Jeffrey Shallit, Jul 22 2005

Keywords

• easy
• nonn

Comments

Equals row sums of triangle A143418, starting with a(2). - Gary W. Adamson, Aug 14 2008

In coupled systems of n spin 1/2 particles (magnetic resonance) where the spin state of the i-th particle can be coded as 0 (Sz_i=-1/2) or 1 (Sz_i=+1/2), number of distinct (vw). - Stanislav Sykora, Jun 07 2012

a(n) is the number of lattice paths from (0,0) to (n,n) using E(1,0) and N(0,1) as steps that horizontally cross the diagonal y = x with odd many times. For example, a(2) = 1 because there is only one path that horizontally crosses the diagonal with odd many times, namely, NEEN. - Ran Pan, Feb 01 2016

Examples

			a(3) = 6 because the pairs are {001,010}, {001,100}, {010,100}, {011,101}, {011,110}, {101,110}.
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..1664
• Mircea Merca, A Special Case of the Generalized Girard-Waring Formula, J. Integer Sequences, Vol. 15 (2012), Article 12.5.7.
• Ran Pan and Jeffrey B. Remmel, Paired patterns in lattice paths, arXiv:1601.07988 [math.CO], 2016.
• Stanislav Sýkora, Magnetic Resonance on OEIS, Stan's NMR Blog (Dec 31, 2014), Retrieved Nov 12, 2019.

Crossrefs

Cf. A005317, A011782, A088218, A143418.

Programs

Magma

[Binomial(2*n,n)-(2^n+Binomial(2*n,n))/2: n in [1..30]]; // Vincenzo Librandi, Feb 01 2016

Maple

with(combinat) a:= proc(n) add(binomial(binomial(n,k), 2), k=0..n) end;

Mathematica

Table[Binomial[2 n, n] - (2^n + Binomial[2 n, n])/2, {n, 30}] (* Vincenzo Librandi, Feb 01 2016 *)

PARI

a(n)=binomial(2*n-1,n-1)-2^(n-1) \\ Charles R Greathouse IV, Feb 01 2016

Python

from math import comb
def A108958(n): return comb((n<<1)-1,n-1)-(1<Chai Wah Wu, Sep 23 2022

Formula

a(n) = Sum_{k=0..n} binomial(binomial(n, k), 2).

From Vladeta Jovovic, Jul 24 2005: (Start)

a(n) = binomial(2*n-1, n-1)-2^(n-1) = A088218(n) - A011782(n).

E.g.f.: exp(2*x)*(BesselI(0, 2*x)-1)/2. (End)

a(n) = (1/2)*Sum_{i+j>n,0<=i,j<=n} binomial(i+j,i). - Benoit Cloitre, May 26 2006

Conjecture: n*(n-2)*a(n) +2*(-3*n^2+7*n-3)*a(n-1) +4*(n-1)*(2*n-3) *a(n-2)=0. - R. J. Mathar, Apr 04 2012

a(n) = Sum_{0Mircea Merca, Apr 05 2012

a(n) = binomial(2*n,n) - A005317(n), - Ran Pan, Feb 01 2016

a(n) = 1/2*Sum_{k=1..n} binomial(n,k)^2 - binomial(n,k). - Gerry Martens, Oct 09 2022

a(n) ~ 2^(2*n-1)/sqrt(n*Pi). - Stefano Spezia, Apr 17 2024