A182062 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, 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, 0, 0, 5040, 5040, 3600, 1440, 144, 0, 0, 0, 40320, 40320, 30240, 14400, 2880, 0, 0, 0, 0, 362880, 362880, 282240, 151200, 43200, 2880, 0, 0, 0, 0, 3628800, 3628800

Offset: 0

Author

Dennis P. Walsh, Apr 09 2012

Keywords

• nonn
• easy
• tabl

Comments

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.

Examples

			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.
Triangle T(n,k) begins
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, 0, 0,
5040, 5040, 3600, 1440, 144, 0, 0, 0,
40320, 40320, 30240, 14400, 2880, 0, 0, 0, 0,
362880,362880,282240,151200,43200,2880,0,0,0,0,
3628800,3628800,2903040,1693440,604800,86400,0,0,0,0,0
		

Links

• T. D. Noe, Rows n = 0..100, flattened
• Dennis Walsh, Notes on isolating men in a line-up [dead link]

Crossrefs

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

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

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

Cf. A169803

Programs

Maple

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

Mathematica

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

Formula

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

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

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