

A097871


Number of Bernstein squares of order n: n X n squares filled with the numbers 1...n such that in row or column k, for all k = 1...n, the number k appears at least once.


1



1, 6, 2683, 223041730, 6009583845720101, 81562450515482338061230306, 801231178966121521807378920617005246471, 7747118609267949193978742640152633949388622796278760450, 96260050927125657231057045653340232713369826309730222706933915414681058441
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

This problem arose because I misunderstood a question that Mira Bernstein asked me!


LINKS

Table of n, a(n) for n=1..9.


FORMULA

Formula from Brendan McKay, Sep 08 2004:
"Define A(i) = (n1)^i*n^(ni)  (n2)^i*(n1)^(ni) (i=0..n), B(i) = (n1)^i*n^(ni)  (n2)^(i1)*(n1)^(ni+1) (i=1..n).
"Then a(n) = (n^n  (n1)^n)^n + sum( binomial(n, i)*(1)^i*A(i)^(ni)*B(i)^i, i=1..n )
"Interpretation: A(i) is the number of ways of choosing row j, say R, such that it has at least one j and i specified positions R[k[1]], ..., R[k[i]] that do not include position R[j] do not have R[k[m]]=k[m] for any m.
"B(i) is the number of ways of choosing row j, say R, such that it has at least one j and i specified positions R[k[1]], ..., R[k[i]] that DO include position R[j] do not have R[k[m]]=k[m] for any m.
"Now A(i)^(ni) * B(i)^i is the number of ways of choosing all the rows such that row j has at least one j for each j and such that a specified set of i columns each do not have an entry equal to the column number.
"The given formula for a(n) is just inclusionexclusion over the erroneous columns, always working with matrices having valid rows."


EXAMPLE

a(2) = 6:
11 11 12 12 12 21
12 22 12 21 22 12
Naming the squares AB/CD, ... these are:
A =1,D =2: 4 (2B 2C, i.e., 2 options for B times 2 options for C)
A =1,D!=2: 1 (1B 1C)
A!=1,D =2: 1 (1B 1C)
A!=1,D!=2: 0, for a total of 6.
For n = 3 and names ABC/DEF/GHI, we get
A =1,E =2,I =3: 729 (3B 3C 3D 3F 3G 3H)
A =1,E =2,I!=3: 450 (3B 3D 2I 5(CF) 5(GH))
A =1,E!=2,I =3: 450
A!=1,E =2,I =3: 450
A =1,E!=2,I!=3: 196 (2E 2I 7(CDF) 7(BGH))
A!=1,E =2,I!=3: 196
A!=1,E!=2,I =3: 196
A!=1,E!=2,I!=3: 16 (2A 2E 2I 2(BCDFGH)), for a total of 2683.  Hugo van der Sanden


MATHEMATICA

a[n_] := (n^n  (n1)^n)^n + Sum[ (1)^i*((n1)^i*n^(ni)  (n2)^i*(n1)^(ni))^(ni)*((n1)^i*n^(ni)  (n2)^(i1)*(n1)^(ni+1))^i * Binomial[n, i], {i, 1, n}]; a[1] = 1; a[2] = 6; Table[ a[n], {n, 1, 9}] (* JeanFrançois Alcover, Dec 20 2011, from formula *)


CROSSREFS

Cf. A097993.
Sequence in context: A067630 A181700 A199147 * A210004 A198667 A225066
Adjacent sequences: A097868 A097869 A097870 * A097872 A097873 A097874


KEYWORD

nonn,nice,easy


AUTHOR

N. J. A. Sloane, Sep 03 2004


EXTENSIONS

a(3) from Hugo van der Sanden, Sep 03 2004
a(4) from Hugo Pfoertner, Sep 06 2004
a(4) confirmed by Hugo van der Sanden, Sep 07 2004
a(5) and a(6) from Guenter Stertenbrink (Sterten(AT)aol.com), using a method suggested by Brendan McKay, Sep 07 2004
Formula and further terms from Brendan McKay, Sep 08 2004


STATUS

approved



