A258371 Triangle read by rows: T(n,k) is number of ways of arranging n indistinguishable points on an n X n square grid such that k rows contain at least one point.

1, 2, 4, 3, 54, 27, 4, 408, 1152, 256, 5, 2500, 22500, 25000, 3125, 6, 13830, 315900, 988200, 583200, 46656, 7, 72030, 3709545, 25882780, 40588905, 14823774, 823543, 8, 360304, 39024384, 535754240, 1766195200, 1657012224, 411041792, 16777216

Offset

1,2

Comments

Row sums give A014062, n >= 1.

Leading diagonal is A000312, n >= 1.

The triangle t(n,k) = T(n,k)/binomial(n,k) gives the number of ways to place n stones into the k X n grid of squares such that each of the k rows contains at least one stone. See A259051. One can use a partition array for this (and the T(n,k)) problem. See A258152. - Wolfdieter Lang, Jun 17 2015

Links

Giovanni Resta, Table of n, a(n) for n = 1..1830 (first 60 rows)

Formula

T(n,2) = binomial(n,2)*(binomial(2*n,n)-2). - Giovanni Resta, May 28 2015

Example

The number of ways of arranging eight pawns on a standard chessboard such that two rows contain at least one pawn is T(8,2)=360304.
Triangle T(n,k) begins:
n\k 1      2        3       4        5       6 ...
1:  1
2:  2      4
3:  3     54      27
4:  4    408    1152      256
5:  5   2500   22500    25000     3125
6:  6  13830  315900   988200   583200   46656
...
n = 7:  7  72030 3709545 25882780  40588905 14823774 823543,
n = 8:  8 360304 39024384 535754240 1766195200 1657012224 411041792 16777216.

Mathematica

T[n_, k_]:= Binomial[n, k] * Sum[Multinomial@@ (Last/@ Tally[e]) * Times@@ Binomial[n, e], {e, IntegerPartitions[n, {k}]}]; Flatten@ Table[ T[n, k], {n, 9}, {k, n}] (* Giovanni Resta, May 28 2015 *)

Crossrefs

Cf. A000312, A014062, A258152, A259051.

Sequence in context: A182103 A303053 A163089 * A111172 A173556 A247554

Adjacent sequences: A258368 A258369 A258370 * A258372 A258373 A258374

Keyword

nonn,tabl

Author

Adam J.T. Partridge, May 28 2015

Status

approved