login
T(n,k) = C(n+1-k,k)*k!*(n-k)!, the number of ways for k men and n-k women to form a queue in which no man is next to another man.
1

%I #10 Jul 15 2012 17:55:28

%S 1,1,1,2,2,0,6,6,2,0,24,24,12,0,0,120,120,72,12,0,0,720,720,480,144,0,

%T 0,0,5040,5040,3600,1440,144,0,0,0,40320,40320,30240,14400,2880,0,0,0,

%U 0,362880,362880,282240,151200,43200,2880,0,0,0,0,3628800,3628800

%N T(n,k) = C(n+1-k,k)*k!*(n-k)!, the number of ways for k men and n-k women to form a queue in which no man is next to another man.

%C Triangle T(n,k), 0<=k<=n, is readily derived since there are C(n+1-k,k) ways to form a sequence of k zeros and n-k ones in which no zeros are consecutive and there are k!(n-k)! ways to permute k labeled zeros and n-k labeled ones. This triangle contains several known sequences, notably A000142 (factorial numbers), A062119 (number of multiplications performed in a determinant), and A010796.

%H T. D. Noe, <a href="/A182062/b182062.txt">Rows n = 0..100, flattened</a>

%H Dennis Walsh, <a href="http://frank.mtsu.edu/~dwalsh/ISOLATEM.pdf">Notes on isolating men in a line-up

%F binomial(n+1-k,k)*k!*(n-k)!

%F G.f. (fixed k): (1-k)*hypergeom([1, 1-k, 2-k],[2-2*k],t)*GAMMA(1-k)^2/GAMMA(2-2*k)

%F T(n,k)=(n+2-2k)*T(n-1,k-1)

%e T(4,2)=12 since there are 12 ways to line up two men {M,m} and two women {W,w} so that no man is next to another man, namely, MWmw, MWwm, MwmW, MwWm, mWMw, mWwM, mwMW, mwWM, WMwm, WmwM, wMWm, and wmWM.

%e Triangle T(n,k) begins

%e 1,

%e 1, 1,

%e 2, 2, 0,

%e 6, 6, 2, 0,

%e 24, 24, 12, 0, 0,

%e 120, 120, 72, 12, 0, 0,

%e 720, 720, 480, 144, 0, 0, 0,

%e 5040, 5040, 3600, 1440, 144, 0, 0, 0,

%e 40320, 40320, 30240, 14400, 2880, 0, 0, 0, 0,

%e 362880,362880,282240,151200,43200,2880,0,0,0,0,

%e 3628800,3628800,2903040,1693440,604800,86400,0,0,0,0,0

%p seq(seq(binomial(n+1-k,k)*k!*(n-k)!,k=0..n),n=0..10);

%t Flatten[Table[Binomial[n+1-k,k]k!(n-k)!,{n,0,10},{k,0,n}]] (* _Harvey P. Dale_, Jul 15 2012 *)

%Y T(n,1) = A000142(n);

%Y T(n,2) = A062119(n-1);

%Y T(2n-1,n-1) = A010796;

%Y Cf. A169803

%K nonn,easy,tabl

%O 0,4

%A _Dennis P. Walsh_, Apr 09 2012