login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A259697 Triangle read by rows: T(n,k) = number of rook patterns on n X n board where bottom rook is in column k. 3
1, 1, 1, 1, 2, 2, 1, 4, 5, 5, 1, 9, 12, 15, 15, 1, 24, 32, 42, 52, 52, 1, 76, 99, 129, 166, 203, 203, 1, 279, 354, 451, 575, 726, 877, 877, 1, 1156, 1434, 1786, 2232, 2792, 3466, 4140, 4140, 1, 5296, 6451, 7883, 9664, 11881, 14621, 17884, 21147, 21147 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

See Becker (1948/49) for precise definition.

This is the number of arrangements of non-attacking rooks on an n X n right triangular board where the bottom rook is in column k. The case of k=0 corresponds to the empty board where there is no bottom rook. - Andrew Howroyd, Jun 13 2017

LINKS

Andrew Howroyd, Table of n, a(n) for n = 0..1274

H. W. Becker, Rooks and rhymes, Math. Mag. 22 (1948/49), 23-26. See Table V.

H. W. Becker, Rooks and rhymes, Math. Mag., 22 (1948/49), 23-26. [Annotated scanned copy]

FORMULA

T(n,0) = 1, T(n,k) = Sum_{i=k..n} A011971(i-1,k-1) for k>0. - Andrew Howroyd, Jun 13 2017

EXAMPLE

Triangle begins:

  1,

  1,  1,

  1,  2,  2,

  1,  4,  5,   5,

  1,  9, 12,  15,  15,

  1, 24, 32,  42,  52,  52,

  1, 76, 99, 129, 166, 203, 203,

  ...

From Andrew Howroyd, Jun 13 2017: (Start)

For n=3, the four solutions with the bottom rook in column 1 are:

  .      .      .      x

  . .    . x    x .    . .

  x . .  x . .  . . .  . . .

For n=3, the five solutions with the bottom rook in column 2 are:

  .      .      x      .       x

  . .    x .    . .    . x     . x

  . x .  . x .  . x .  . . .   . . .

(End)

MATHEMATICA

a11971[n_, k_] := Sum[Binomial[k, i]*BellB[n - k + i], {i, 0, k}];

T[_, 0] = 1; T[n_, k_] := Sum[a11971[i - 1, k - 1], {i, k, n}];

Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-Fran├žois Alcover, Jul 07 2018, after Andrew Howroyd *)

PROG

(PARI)

A(N)={my(T=matrix(N, N), U=matrix(N, N)); T[1, 1]=1; U[1, 1]=1;

for(n=2, N, for(k=1, n, T[n, k]=if(k==1, T[n-1, n-1], T[n-1, k-1]+T[n, k-1]); U[n, k]=T[n, k]+U[n-1, k])); U}

{my(T=A(10)); for(n=0, length(T), for(k=0, n, print1(if(k==0, 1, T[n, k]), ", ")); print)} \\ Andrew Howroyd, Jun 13 2017

(Python)

from sympy import bell, binomial

def a011971(n, k): return sum([binomial(k, i)*bell(n - k + i) for i in xrange(k + 1)])

def T(n, k): return 1 if k==0 else sum([a011971(i - 1, k - 1) for i in xrange(k, n + 1)])

for n in xrange(10): print [T(n, k) for k in xrange(n + 1)] # Indranil Ghosh, Jun 17 2017

CROSSREFS

Right edge is A000110.

Column k=1 is A005001.

Row sums are A000110(n+1).

Cf. A011971, A259691.

Sequence in context: A247311 A113547 A218580 * A115313 A048942 A121484

Adjacent sequences:  A259694 A259695 A259696 * A259698 A259699 A259700

KEYWORD

nonn,tabl

AUTHOR

N. J. A. Sloane, Jul 05 2015

EXTENSIONS

Terms a(28) and beyond from Andrew Howroyd, Jun 13 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 23 07:05 EDT 2019. Contains 328335 sequences. (Running on oeis4.)