Married Couples Problem

Author

Eric W. Weisstein
March 11, 2011

This notebook downloaded from http://mathworld.wolfram.com/notebooks/Combinatorics/MarriedCouplesProblem.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/MarriedCouplesProblem.html.

©2011 Wolfram Research, Inc. except for portions noted otherwise

Recurrence

Explicit Solution

a[1]:=-1
a[2]:=0
a[n_]:=a[n]=(n(n-2) a[n-1] + n a[n-2] - 4(-1)^n) / (n-2)

Table[a[n],{n,10}]

Table[2n!a[n],{n,10}]

v4.2

<<DiscreteMath`RSolve`

RSolve[{a[n]==((n^2-2n) a[n-1] + n a[n-2] - 4((-1)^n)) / (n-2),a[1]==-1,a[2]==0},a[n],n]//Timing

v5.0

RSolve[{a[n]==((n^2-2n) a[n-1] + n a[n-2] - 4((-1)^n)) / (n-2),a[1]==-1,a[2]==0},a[n],n]

V7

RSolve[{a[n]==((n^2-2n) a[n-1] + n a[n-2] - 4((-1)^n)) / (n-2),a[1]==-1,a[2]==0},a[n],n]

V8.1

RSolve[{a[n]==((n^2-2n) a[n-1] + n a[n-2] - 4((-1)^n)) / (n-2),a[1]==-1,a[2]==0},a[n],n]

Sum

(∑_(k=0)^n)((2 (((-1))^k) n (n-k)! )/(2 n-k))(Binomial[2 n-k, k])

Touchard's Sum

For explicit n

Table[Sum[2n/(2n-k)Binomial[2n-k,k](n-k)!(-1)^k,{k,0,n}],{n,10}]

V4.1

Generically incorrect

Simplify[Sum[2n/(2n-k)Binomial[2n-k,k](n-k)!(-1)^k,{k,0,n}]]

V4.2

Generically incorrect

Sum[2n/(2n-k)Binomial[2n-k,k](n-k)!(-1)^k,{k,0,n}]

FullSimplify[%,n∈Integers]

Table[((n π BesselI[-n,2] Csc[n π])/(E^2))-((4 (((-1))^n) HypergeometricPFQ[{1,(3/2)},{2-n,2+n},-4])/(-1+(n^2))),{n,10}]

V5.0

(Correctly) does not return in 5.0

Sum[2n/(2n-k)Binomial[2n-k,k](n-k)!(-1)^k,{k,0,n}]

V6

Sum[2n/(2n-k)Binomial[2n-k,k](n-k)!(-1)^k,{k,0,n}]

V7.0.0

Sum[2n/(2n-k)Binomial[2n-k,k](n-k)!(-1)^k,{k,0,n}]

Table[-2 n DifferenceRoot[Function[{\[FormalY],\[FormalN]},{(-2-4 \[FormalN]+4 n) \[FormalY][\[FormalN]]+(1-(\[FormalN]^2)-2 n+\[FormalN] (2+2 n)) \[FormalY][1+\[FormalN]]+(1+(\[FormalN]^2)+\[FormalN] (2-2 n)-2 n) \[FormalY][2+\[FormalN]]==0,\[FormalY][0]==0,\[FormalY][1]==-((n!)/(2 n))}]][1+n],{n,2,10}]

V7.0.1

Sum[2n/(2n-k)Binomial[2n-k,k](n-k)!(-1)^k,{k,0,n}]

V8.1

Sum[2n/(2n-k)Binomial[2n-k,k](n-k)!(-1)^k,{k,0,n}]

V10

2*n*Sum[(-1)^k*Binomial[2*n-k,k]*(n-k)!/(2*n-k),{k,0,n}]

Table[2*n*Sum[(-1)^k*Binomial[2*n-k,k]*(n-k)!/(2*n-k),{k,0,n}],{n,10}]

2*n*Sum[(-1)^k*Binomial[2*n-k,k]*(n-k)!/(2*n-k),{k,0,n-1}]

FunctionExpand[(-1)^k Binomial[2*n-k,k]*(n-k)!/(2*n-k),Element[n,Integers]]

(((((-1))^k) (2^(2 k-2 n)) (Sqrt[π]) Gamma[-k+2 n])/(Gamma[1+k] Gamma[(1/2)-k+n]))//FullSimplify

Table[2*n*Sum[(((((-1))^k) (2^(2 k-2 n)) (Sqrt[π]) Gamma[-k+2 n])/(Gamma[1+k] Gamma[(1/2)-k+n])),{k,0,n}],{n,10}]

2*n*Sum[(((((-1))^k) (2^(2 k-2 n)) (Sqrt[π]) Gamma[-k+2 n])/(Gamma[1+k] Gamma[(1/2)-k+n])),{k,0,n}]//FullSimplify

Table[(1/(E^2))n π Csc[n π] (BesselI[-n,2]+4 (((-1))^n) (E^2) HypergeometricPFQRegularized[{1,(3/2)},{2-n,2+n},-4]),{n,5}]

Table[{(1/(E^2))n π Csc[n π] ,BesselI[-n,2],4 (((-1))^n) (E^2) HypergeometricPFQRegularized[{1,(3/2)},{2-n,2+n},-4]},{n,5}]//N

2%[[All,2]]

Sum[(((((-1))^k) (2^(2 k)) (Sqrt[π]) Gamma[-k+2 n])/(Gamma[1+k] Gamma[(1/2)-k+n])),{k,0,n}]

Table[(((Sqrt[π]) Gamma[2 n] Hypergeometric1F1[(1/2)-n,1-2 n,-4])/(Gamma[(1/2) (1+2 n)]))+(((((-1))^(1+n)) (2^(1+2 n)) Gamma[-1+n] HypergeometricPFQ[{1,(3/2)},{2-n,2+n},-4])/(Gamma[2+n])),{n,10}]

2*n*Sum[(((((-1))^k) (2^( k-n))  (-k+2 n-1)!)/(Gamma[1+k] (2(n-k-1)+1)!!)),{k,0,m}]//FullSimplify

Limit[(1/((E^2) Gamma[-(1/2)-m+n]))(2^((1/4) (1-8 n-Cos[2 n π]))) n (π^((1/4) (3+Cos[2 n π]))) ((4^n) BesselI[-n,2] Csc[n π] Gamma[-(1/2)-m+n]+(((-1))^m) (2^(3+2 m)) (E^2) (Sqrt[π]) Csc[(m-2 n) π] HypergeometricPFQRegularized[{1,(3/2)+m-n},{2+m,2+m-2 n},-4]),m->n]

sum=2*n*Sum[(((((-1))^k) (2^( k-n))  (-k+2 n-1)!)/(Gamma[1+k] (2(n-k-1)+1)!!)),k]

Limit[sum,k->0]

Limit[sum,k->n]

Generating Function

(((1-x) (∑_(n=0)^∞)n! ((((x/(((x+1))^2))))^n))/(x+1))+x

Series[x+((1-x)/(1+x))Sum[n!((((x/(((1+x))^2))))^n),{n,0,10}],{x,0,10}]

Series[x+((1-x)/(1+x))Sum[n!((x^n)/(((1+x))^(2n))),{n,0,10}],{x,0,10}]

V8.1

x+((1-x)/(1+x))Sum[n!((((x/(((1+x))^2))))^n),{n,0,∞}]

x+((1-x)/(1+x))Sum[n!((x^n)/(((1+x))^(2n))),{n,0,∞}]

n! (∑_(k=0)^n)(∑_(j=0)^(n-k))(((2^j) k! (Binomial[-3 (k+1), -j-k+n]))/(j!))

Table[n! Sum[(2^j/j!)*k!*Binomial[-3*(k+1),n-k-j],{k,0,n},{j,0,n-k}],{n,10}]

V8.1

n! Sum[(2^j/j!)*k!*Binomial[-3*(k+1),n-k-j],{k,0,n},{j,0,n-k}]//Timing

Sum[(2^j/j!)*k!*Binomial[-3*(k+1),n-k-j],{k,0,n}]

Table

Table[Sum[2n/(2n-k)Binomial[2n-k,k](n-k)!(-1)^k,{k,0,n}],{n,15}]

a[n_]:=((n^2-2n) a[n-1] + n a[n-2] - 4((-1)^n)) / (n-2)
a[1]:=-1
a[2]:=0

Table[a[n],{n,10}]

FindSequenceFunction[{0,1,2,13,80,579,4738,43387,439792,4890741,59216642,775596313,10927434464,164806435783},n]