

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



FORMULA

"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


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



KEYWORD

nonn,nice,easy


AUTHOR



EXTENSIONS

a(5) and a(6) from Guenter Stertenbrink (Sterten(AT)aol.com), using a method suggested by Brendan McKay, Sep 07 2004


STATUS

approved



