A293857 -id:A293857 - cp's OEIS frontend

A293984 a(n) = A293857(n)/A010551(n).

1, 1, 1, 2, 3, 3, 4, 10, 16, 23, 35, 85, 142, 229, 369, 895, 1522, 2614, 4348, 10467, 18038, 32160, 54488, 130148, 226594, 414130, 710880, 1685496, 2958666, 5503780, 9544629, 22476690, 39724867, 74884360, 130949625, 306457174, 544777361, 1037587152, 1827129712

Offset: 0

Vladimir Shevelev, Oct 21 2017

nonn

Or row sums of the compressed triangle in A293783.
Conjecture: all terms are positive integers.
From David A. Corneth (with participation of Vladimir Shevelev), Oct 24 2017: (Start)
Conjecture is true. Proof.
1) Let C={c_1..c_n} be a permutation of {1..n}, d(C) be alternating sum c_1 - c_2 + ... +(-1)^(n-1)*c_n. Then max_{C in S_n}d(C) = A008794(n+1). Indeed, if n = 2*m, then evidently the maximum is reached on a C={2*m,1,2*m-1,2,...,m+1,m}; if n=2*m - 1, then the maximum is reached on a C={2*m-1,1,2*m-2,2,...,m-1,m}. In both cases max_{C in S_n}d(C) = m^2 = A008794(n+1). The number of distinct reaches of the maximum is, evidently, floor(n/2)!*floor((n+1)/2)! which is also Avi Peretz's representation (2001) of A010551(n). So, A293857(n) >= A010551(n) and a(n)>=1.
2) Consider two cases: a) there are no C in S_n for which d(C) = k^2 < A008794(n+1). Then A293857(n) = A010551(n) and a(n) = 1; b) there is C for which d(C) = k^2 < A008794(n+1). Then, as in 1) to reach k^2 in case n=2*m consider all (n/2)! permutations of {c_1,c_3,...,c_n} and all (n/2)! permutations of {c_2, c_4, ... , c_(n+1)}, or in case n = 2*m-1, all ((n+1)/2)! permutations of {c_1,c_3,...,c_(2*m-1)} and ((n-1)/2)! permutations of {c_2,c_4,...,c_(2*m-2)}. So we again have A010551(n) distinct reaches. If the same k^2 could be reached by another permutation C_1 (other than above permutations of C), then we again obtain A010551 distinct reaches, etc. So, A293857(n) is always divisible by A010551(n). (End)

Peter J. C. Moses, Table of n, a(n) for n = 0..250

Cf. A008794, A010551, A293783, A293857.

b:= proc(p, m, s) option remember; (n-> `if`(n=0, `if`(issqr(s), 1, 0),
      `if`(p>0, b(p-1, m, s+n), 0)+`if`(m>0, b(p, m-1, s-n), 0)))(p+m)
    end:
a:= n-> (t-> b(n-t, t, 0))(iquo(n, 2)):
seq(a(n), n=0..40);  # Alois P. Heinz, Sep 17 2020

a293984=Table[
possibleSums=Range[1/2-(-1)^n/2-Floor[n/2]^2,Floor[(n+1)/2]^2];
filteredSums=Select[possibleSums,IntegerQ[Sqrt[#]]&];
positions=Map[Flatten[{#,Position[possibleSums,#,1]-1}]&,filteredSums];
Total[Map[SeriesCoefficient[QBinomial[n,Floor[(n+1)/2],q],{q,0,#[[2]]/2}]&,positions]],{n,20}] (* Peter J. C. Moses, Nov 05 2017 *)

a(13)-a(30) from David A. Corneth, Oct 21 2017; a(31)-a(38) from Peter J. C. Moses, Nov 02 2017

a(0)=1 prepended by Alois P. Heinz, Sep 17 2020

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

Original entry on oeis.org

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

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

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

			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

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.

Cf. A008794, A010551, A293857, A293984.

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 *)

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

A294811 Let b(n) be the number of permutations {c_1..c_n} of {1..n} for which c_1 - c_2 + ... + (-1)^(n-1)*c_n are triangular numbers (A000217). Then a(n) = b(n)/A010551(n).

Original entry on oeis.org

1, 1, 1, 1, 2, 4, 6, 11, 16, 30, 48, 97, 157, 322, 524, 1077, 1777, 3684, 6157, 12876, 21684, 45520, 77212, 162533, 277608, 585993, 1006784, 2129433, 3677453, 7788711, 13514487, 28654668, 49933938, 105964856, 185377690, 393631445, 691101516, 1468137470

Offset: 0

Vladimir Shevelev and Peter J. C. Moses, Nov 09 2017

nonn

All terms are positive integers (for a proof, cf. comment in A293984). Note that a(1), a(2), a(3), a(4) remain the same if in the definition the triangular numbers are replaced by k-gonal numbers for k >= 5.

			Let n=3. For a permutation C={c_1,c_2,c_3}, set s = s(C) = c_1 - c_2 + c_3. We have the permutations:
1,2,3; s=2
1,3,2; s=0
2,1,3; s=4
2,3,1; s=0
3,1,2; s=4
3,2,1; s=2
Here there are 2 permutations for which {s} are triangular numbers (when s = 0). Further, since A010551(3) = 2, then a(3) = 1.
Let n=4. For a permutation C={c_1,c_2,c_3,c_4}, set s = s(C) = c_1 - c_2 + c_3 - c_4. We have the permutations:
1,2,3,4; s=-2
1,3,2,4; s=-4
2,1,3,4; s=0
2,3,1,4; s=-4
3,1,2,4; s=0
3,2,1,4; s=-2
1,2,4,3; s=0
1,3,4,2; s=0
2,1,4,3; s=2
2,3,4,1; s=2
3,1,4,2; s=4
3,2,4,1; s=4
1,4,2,3; s=-4
1,4,3,2; s=-2
2,4,1,3; s=-4
2,4,3,1; s=0
3,4,1,2; s=-2
3,4,2,1; s=0
4,1,2,3; s=2
4,1,3,2; s=4
4,2,1,3; s=0
4,2,3,1; s=4
4,3,1,2; s=0
4,3,2,1; s=2
Here there are 8 permutations for which {s} are triangular numbers (when s = 0). Further, since A010551(4) = 4, then a(4) = 8/4 = 2.

Alois P. Heinz, Table of n, a(n) for n = 0..250 (terms n=1..200 from Peter J. C. Moses)

Cf. A010551, A293857, A293984.

b:= proc(p, m, s) option remember; (n-> `if`(n=0, `if`(issqr(8*s+1), 1, 0),
      `if`(p>0, b(p-1, m, s+n), 0)+`if`(m>0, b(p, m-1, s-n), 0)))(p+m)
    end:
a:= n-> (t-> b(n-t, t, 0))(iquo(n, 2)):
seq(a(n), n=0..40);  # Alois P. Heinz, Sep 17 2020

polyQ[order_,n_]:=If[n==0,True,IntegerQ[(#-4+Sqrt[(#-4)^2+8 n (#-2)])/(2 (#-2))]&[order]];(*is a number polygonal?*)
Map[Total,Table[
possibleSums=Range[1/2-(-1)^n/2-Floor[n/2]^2,Floor[(n+1)/2]^2];
filteredSums=Select[possibleSums,polyQ[3,#]&&#>-1&];
positions=Map[Flatten[{#,Position[possibleSums,#,1]-1}]&,filteredSums];
Map[SeriesCoefficient[QBinomial[n,Floor[(n+1)/2],q],{q,0,#[[2]]/2}]&,positions],{n,25}]] (* Peter J. C. Moses, Jan 02 2018 *)

a(0)=1 prepended by Alois P. Heinz, Sep 17 2020

A294812 Let b(n) be the number of permutations {c_1..c_n} of {1..n} for which c_1 - c_2 + ... + (-1)^(n-1)*c_n are pentagonal numbers (A000326). Then a(n) = b(n)/A010551(n).

Original entry on oeis.org

1, 1, 1, 2, 4, 5, 6, 10, 23, 38, 70, 110, 196, 346, 759, 1250, 2313, 3982, 8433, 14520, 29437, 50466, 102830, 179587, 376439, 654374, 1343540, 2352149, 4916286, 8654120, 18065200, 31783592, 66233160, 117371504, 246610521, 436972949, 913862320, 1626523783

Offset: 1

Vladimir Shevelev and Peter J. C. Moses, Nov 09 2017

nonn

All terms are positive integers (for a proof, cf. comment in A293984).

Note that a(1), a(2), a(3), a(4) remain the same, if in the definition the pentagonal numbers are replaced by k-gonal numbers for k >= 3 other than k=4.

Peter J. C. Moses, Table of n, a(n) for n = 1..200

Cf. A010551, A293857, A293984, A294811.

polyQ[order_,n_]:=If[n==0,True,IntegerQ[(#-4+Sqrt[(#-4)^2+8 n (#-2)])/(2 (#-2))]&[order]];(*is a number polygonal?*)
Map[Total,Table[
possibleSums=Range[1/2-(-1)^n/2-Floor[n/2]^2,Floor[(n+1)/2]^2];
filteredSums=Select[possibleSums,polyQ[5,#]&&#>-1&];
positions=Map[Flatten[{#,Position[possibleSums,#,1]-1}]&,filteredSums];
Map[SeriesCoefficient[QBinomial[n,Floor[(n+1)/2],q],{q,0,#[[2]]/2}]&,positions],{n,25}]] (* Peter J. C. Moses, Jan 02 2018 *)

cp's OEIS Frontend

A293984 a(n) = A293857(n)/A010551(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A294811 Let b(n) be the number of permutations {c_1..c_n} of {1..n} for which c_1 - c_2 + ... + (-1)^(n-1)*c_n are triangular numbers (A000217). Then a(n) = b(n)/A010551(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A294812 Let b(n) be the number of permutations {c_1..c_n} of {1..n} for which c_1 - c_2 + ... + (-1)^(n-1)*c_n are pentagonal numbers (A000326). Then a(n) = b(n)/A010551(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica