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

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.

Links

T. D. Noe, Rows n = 0..100, flattened

Dennis Walsh, Notes on isolating men in a line-up

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)

Example

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

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 *)

Crossrefs

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

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

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

Cf. A169803

Sequence in context: A271708 A284983 A140333 * A265326 A245333 A323777

Adjacent sequences: A182059 A182060 A182061 * A182063 A182064 A182065

Keyword

nonn,easy,tabl

Author

Dennis P. Walsh, Apr 09 2012

Status

approved