A293783 Triangle of numbers of squares {i^2}, i = 0,1..ceiling(n/2), in permutations of {1..n} in A293857.

0, 1, 0, 1, 2, 0, 2, 8, 0, 4, 0, 24, 0, 12, 0, 108, 0, 36, 576, 0, 720, 0, 144, 4608, 0, 4032, 0, 576, 0, 31680, 0, 31680, 0, 2880, 0, 288000, 0, 201600, 0, 14400, 2505600, 0, 2764800, 0, 1987200, 0, 86400, 30067200, 0, 28512000, 0, 14515200, 0, 518400

Offset: 1

Author

Peter J. C. Moses and Vladimir Shevelev, Oct 18 2017

Keywords

• nonn
• tabf

Comments

From Shevelev's comment in A008794 it follows that the last entries of rows, corresponding to the maximal possible i^2, form sequence A010551, n >= 1. Also note that the last entry of each row is the gcd of all its entries (for a proof see comment in A293857). - Vladimir Shevelev, Oct 26 2017

Examples

			Triangle begins
         0,      1;
         0,      1;
         2,      0,        2;
         8,      0,        4;
         0,     24,        0,     12;
         0,    108,        0,     36;
       576,      0,      720,      0,      144;
      4608,      0,     4032,      0,      576;
         0,  31680,        0,  31680,        0,  2880;
         0, 288000,        0, 201600,        0, 14400;
   2505600,      0,  2764800,      0,  1987200,     0,  86400;
  30067200,      0, 28512000,      0, 14515200,     0, 518400;
The compressed triangle resulting from the division of each entry by the last entry of its row begins as follows. If i is the index of the row, starting with i = 1 then this last entry is floor(i/2)! * (i - floor(i/2))!.
    0,   1;
    0,   1;
    1,   0,   1;
    2,   0,   1;
    0,   2,   0,   1;
    0,   3,   0,   1;
    4,   0,   5,   0,   1;
    8,   0,   7,   0,   1;
    0,  11,   0,  11,   0,   1;
    0,  20,   0,  14,   0,   1;
   29,   0,  32,   0,  23,   0,   1;
   58,   0,  55,   0,  28,   0,   1;
    0,  88,   0,  94,   0,  46,   0,   1;
    0, 169,   0, 146,   0,  53,   0,   1;
  263,   0, 282,   0, 283,   0,  86,   0,   1;
  526,   0, 515,   0, 383,   0,  97,   0,   1;
For the sense of the entries of this triangle see the [Shevelev] link (with a continuation there). Let B(n,i) be the set of permutations C of 1..n for which c_1 - c_2 + ... + (-1)^(n-1)*c_n = i^2, i >= 0. Then |B(n,i)| is the entry in the n-th row and i-th column of the first triangle. Let us call two permutations C_1 and C_2 equivalent if one of them is obtained from another by a permutation of its elements with odd indices and/or separately with even indices. Let b(n,i) be the entry in the n-th row and i-th column of the second triangle. Then b(n,i) is the maximal possible number of pairwise non-equivalent permutations which could be chosen in B(n,i). On the other hand, it is the smallest number of non-equivalent permutations in B(n,i) such that every other permutation in B(n,i) is equivalent to one of them. So in some sense b(n,i) is the dimension of B(n,i). In particular, b(n,i) = 0 corresponds to empty B(n,i). - _Vladimir Shevelev_, Nov 13 2017
		

Links

• Peter J. C. Moses, Table of the first 100 rows
• Vladimir Shevelev, Basis in subsets of permutations described in A293783, SeqFan post Oct 27 2017.

Crossrefs

Cf. A008794, A010551, A293857, A293984.

Programs

Mathematica

a293783=Flatten[Table[PadLeft[Riffle[#,Table[0,{Floor[(n-1)/4]}]/.{}->0],1+Floor[(1+n)/2]](Floor[n/2]!*(n-Floor[n/2])!)&[Reverse[Map[SeriesCoefficient[QBinomial[n,Floor[(n+1)/2],q],{q,0,#}]&,Map[2#(Floor[(n+1)/2] - #)&,Range[0,Floor[(n+1)/4]]]]]],{n,20}]] (* Peter J. C. Moses, Nov 01 2017 *)

Formula

Row sums of triangle give A293857.

If C = {c_1..c_n} is a permutation of {1..n}, then c_1 - c_2 + ... has the same parity as 1 + 2 + ... + n = n*(n+1)/2. So adjacent rows in the triangle for odd and even n have the same positions of 0's. These positions follow through one, beginning from the first position for n == 1,2 (mod 4) and from the second position for n == 3,0 (mod 4). - David A. Corneth and Vladimir Shevelev, Oct 19 2017