|
%I #22 Dec 17 2016 03:54:10
%S 1,6,2683,223041730,6009583845720101,81562450515482338061230306,
%T 801231178966121521807378920617005246471,
%U 7747118609267949193978742640152633949388622796278760450,96260050927125657231057045653340232713369826309730222706933915414681058441
%N 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.
%C This problem arose because I misunderstood a question that _Mira Bernstein_ asked me!
%F Formula from _Brendan McKay_, Sep 08 2004:
%F "Define A(i) = (n-1)^i*n^(n-i) - (n-2)^i*(n-1)^(n-i) (i=0..n), B(i) = (n-1)^i*n^(n-i) - (n-2)^(i-1)*(n-1)^(n-i+1) (i=1..n).
%F "Then a(n) = (n^n - (n-1)^n)^n + sum( binomial(n, i)*(-1)^i*A(i)^(n-i)*B(i)^i, i=1..n )
%F "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.
%F "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.
%F "Now A(i)^(n-i) * 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.
%F "The given formula for a(n) is just inclusion-exclusion over the erroneous columns, always working with matrices having valid rows."
%e a(2) = 6:
%e 11 11 12 12 12 21
%e 12 22 12 21 22 12
%e Naming the squares AB/CD, ... these are:
%e A =1,D =2: 4 (2B 2C, i.e., 2 options for B times 2 options for C)
%e A =1,D!=2: 1 (1B 1C)
%e A!=1,D =2: 1 (1B 1C)
%e A!=1,D!=2: 0, for a total of 6.
%e For n = 3 and names ABC/DEF/GHI, we get
%e A =1,E =2,I =3: 729 (3B 3C 3D 3F 3G 3H)
%e A =1,E =2,I!=3: 450 (3B 3D 2I 5(CF) 5(GH))
%e A =1,E!=2,I =3: 450
%e A!=1,E =2,I =3: 450
%e A =1,E!=2,I!=3: 196 (2E 2I 7(CDF) 7(BGH))
%e A!=1,E =2,I!=3: 196
%e A!=1,E!=2,I =3: 196
%e A!=1,E!=2,I!=3: 16 (2A 2E 2I 2(BCDFGH)), for a total of 2683. - _Hugo van der Sanden_
%t a[n_] := (n^n - (n-1)^n)^n + Sum[ (-1)^i*((n-1)^i*n^(n-i) - (n-2)^i*(n-1)^(n-i))^(n-i)*((n-1)^i*n^(n-i) - (n-2)^(i-1)*(n-1)^(n-i+1))^i * Binomial[n, i], {i, 1, n}]; a[1] = 1; a[2] = 6; Table[ a[n], {n, 1, 9}] (* _Jean-François Alcover_, Dec 20 2011, from formula *)
%Y Cf. A097993.
%K nonn,nice,easy
%O 1,2
%A _N. J. A. Sloane_, Sep 03 2004
%E a(3) from _Hugo van der Sanden_, Sep 03 2004
%E a(4) from _Hugo Pfoertner_, Sep 06 2004
%E a(4) confirmed by _Hugo van der Sanden_, Sep 07 2004
%E a(5) and a(6) from Guenter Stertenbrink (Sterten(AT)aol.com), using a method suggested by _Brendan McKay_, Sep 07 2004
%E Formula and further terms from _Brendan McKay_, Sep 08 2004
|
