A269129 -id:A269129 - cp's OEIS frontend

A331562 Number A(n,k) of sequences with k copies each of 1,2,...,n avoiding absolute differences between adjacent elements larger than one; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 6, 2, 1, 1, 1, 20, 12, 2, 1, 1, 1, 70, 92, 26, 2, 1, 1, 1, 252, 780, 506, 48, 2, 1, 1, 1, 924, 7002, 11482, 2288, 86, 2, 1, 1, 1, 3432, 65226, 284002, 135040, 10010, 148, 2, 1, 1, 1, 12870, 623576, 7426610, 8956752, 1543862, 41618, 250, 2, 1

Offset: 0

Alois P. Heinz, Jan 20 2020

All columns are linear recurrences with constant coefficients and for k > 0 the order of the recurrence is bounded by 3*k-1. For k up to at least 17 this upper bound is exact. - Andrew Howroyd, May 16 2020

Row 2, the sequence of central binomial numbers A000984, satisfies the supercongruences u(n*p^r) == u(n*p^(r-1)) (mod p^(3*r)) for all primes p >= 5 and all positive integers n and r (see Meštrović, equation 39). This is also known to be true for row 3 (A103882) and row 4 (A177316). We conjecture that each row sequence of the table satisfies the same congruences. - Peter Bala, Oct 26 2024.

			A(2,2) = 6: 1122, 1212, 1221, 2112, 2121, 2211.
A(3,2) = 12: 112233, 112323, 112332, 121233, 123321, 211233, 233211, 321123, 323211, 332112, 332121, 332211.
A(2,3) = 20: 111222, 112122, 112212, 112221, 121122, 121212, 121221, 122112, 122121, 122211, 211122, 211212, 211221, 212112, 212121, 212211, 221112, 221121, 221211, 222111.
A(3,3) = 92: 111222333, 111223233, 111223323, 111223332, ..., 333221112, 333221121, 333221211, 333222111.
Square array A(n,k) begins:
  1, 1,  1,     1,       1,         1,           1, ...
  1, 1,  1,     1,       1,         1,           1, ...
  1, 2,  6,    20,      70,       252,         924, ...
  1, 2, 12,    92,     780,      7002,       65226, ...
  1, 2, 26,   506,   11482,    284002,     7426610, ...
  1, 2, 48,  2288,  135040,   8956752,   640160976, ...
  1, 2, 86, 10010, 1543862, 276285002, 54331653686, ...

Andrew Howroyd, Antidiagonals n = 0..50, flattened (antidiagonals 0..15 from Alois P. Heinz)
Romeo Meštrović, Wolstenholme's theorem: Its Generalizations and Extensions in the last hundred and fifty years (1862-2012), arXiv:1111.3057 [math.NT], (2011).

Columns k=0-9 give: A000012, A130130 (for n>0), A177282, A177291, A177298, A177301, A177304, A177307, A177310, A177313.
Rows n=0+1, 2-9 give: A000012, A000984, A103882, A177316, A177317, A177318, A177319, A177320, A177321.
Main diagonal gives A331623.
Cf. A269129, A275784.

b:= proc(l, q) option remember; (n-> `if`(n<2, 1, add(
     `if`(l[j]=1, `if`(j in [1, n], b(subsop(j=[][], l),
     `if`(j=1, 0, n)), 0), b(subsop(j=l[j]-1, l), j)), j=
     `if`(q<0, 1..n, max(1, q-1)..min(n, q+1)))))(nops(l))
    end:
A:= (n, k)-> `if`(k=0, 1, b([k$n], -1)):
seq(seq(A(n, d-n), n=0..d), d=0..10);

b[l_, q_] := b[l, q] = With[{n = Length[l]}, If[n < 2, 1, Sum[
      If[l[[j]] == 1, If[j == 1 || j == n, b[ReplacePart[l, j -> Nothing],
      If[j == 1, 0, n]], 0], b[ReplacePart[l, j -> l[[j]] - 1], j]], {j,
      If[q < 0, Range[n], Range[Max[1, q - 1], Min[n, q + 1]]]}]]];
A[n_, k_] := If[k == 0, 1, b[Table[k, {n}], -1]];
Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Jan 03 2021, after Alois P. Heinz *)

step(m,R)={my(M=matrix(3, m+1, q, p, q--; p--; sum(j=0, m-p-q, sum(i=max(p+j-#R+1, 2*p+q+j-m), p, R[1+q, 1+p+j-i] * binomial(p,i) * binomial(p+q+j-i-1, j) * binomial(m-1, 2*p+q+j-i-1))))); M[3,]+=2*M[2,]+M[1,]; M[2,]+=M[1,]; M}
AdjPathsBySig(sig)={if(#sig<1, 1, my(R=[1;1;1]); for(i=1, #sig-1, R=step(sig[i], R)); my(m=sig[#sig]); sum(i=1, min(m, #R), binomial(m-1, i-1)*R[3,i]))}
T(n,k) = {if(k==0, 1, AdjPathsBySig(vector(n,i,k)))} \\ Andrew Howroyd, May 16 2020

A275784 Number A(n,k) of up-down sequences with k copies each of 1,2,...,n; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 2, 1, 1, 0, 1, 4, 5, 1, 1, 0, 1, 12, 53, 16, 1, 1, 0, 1, 36, 761, 936, 61, 1, 1, 0, 1, 120, 12661, 87336, 25325, 272, 1, 1, 0, 1, 400, 229705, 9929000, 18528505, 933980, 1385, 1, 1, 0, 1, 1400, 4410665, 1267945800, 17504311533, 6376563600, 45504649, 7936, 1

Offset: 0

Alois P. Heinz, Aug 12 2016

			A(4,1) = 5: 1324, 1423, 2314, 2413, 3412.
A(3,2) = 4: 121323, 132312, 231213, 231312.
A(3,3) = 12: 121313232, 121323132, 121323231, 131213232, 132312132, 132323121, 231213132, 231213231, 231312132, 231323121, 232312131, 232313121.
A(2,4) = 1: 12121212.
Square array A(n,k) begins:
  1,   1,      1,          1,              1,              1, ...
  1,   1,      0,          0,              0,              0, ...
  1,   1,      1,          1,              1,              1, ...
  1,   2,      4,         12,             36,            120, ...
  1,   5,     53,        761,          12661,         229705, ...
  1,  16,    936,      87336,        9929000,     1267945800, ...
  1,  61,  25325,   18528505,    17504311533, 19126165462061, ...
  1, 272, 933980, 6376563600, 59163289699260, ...

Alois P. Heinz, Antidiagonals n = 0..15, flattened

Columns k=0-3 give: A000012, A000111, A275801, A276636.
Rows n=2-5 give: A000012, A241530, A036916, A276637.
Cf. A269129, A331562.

b:= proc(n, l) option remember; `if`(l=[], 1, `if`(irem(add(i,
      i=l), 2)=0, add(b(i, subsop(i=`if`(l[i]=1, [][], l[i]-1),
      l)), i=n+1..nops(l)), add(b(i-`if`(l[i]=1, 1, 0), subsop(
      i=`if`(l[i]=1, [][], l[i]-1), l)), i=1..n-1)))
    end:
A:= (n, k)->`if`(k=0, 1, b(`if`(irem(k*n, 2)=0, 0, n+1), [k$n])):
seq(seq(A(n, d-n), n=0..d), d=0..10);

b[n_, l_List] := b[n, l] = If[l == {}, 1, If[EvenQ[Total[l]], Sum[b[i, ReplacePart[l, i -> If[l[[i]] == 1, Nothing, l[[i]]-1]]], {i, n+1, Length[l]}], Sum[b[i - If[l[[i]] == 1, 1, 0], ReplacePart[l, i -> If[l[[i]] == 1, Nothing, l[[i]]-1]]], {i, 1, n-1}]]]; A[n_, k_] := If[k == 0, 1, b[If[EvenQ[k*n], 0, n+1], Array[k&, n]]]; Table[A[n, d-n], {d, 0, 10}, {n, 0, d}] // Flatten (* Jean-François Alcover, Jan 23 2017, adapted from Maple *)

A267532 Number of words on {1,1,2,2,...,n,n} with longest increasing subsequence of length < n.

Original entry on oeis.org

0, 0, 1, 43, 1879, 102011, 7235651, 674641325, 81537026047, 12498099730471, 2375632826877259, 548818073236649129, 151476182218777630655, 49229890784448694885163, 18608906461974462064310179, 8094874797394331233877338741, 4015057931973886657462193434111

Offset: 0

Alois P. Heinz, Jan 16 2016

nonn

Or number of words on {1,1,2,2,...,n,n} avoiding the pattern 12...n.

			a(2) = 1: 2211.
a(3) = 43: 113322, 131322, 133122, 133212, 133221, 211332, 213132, 213312, 213321, 221133, 221313, 221331, 223113, 223131, 223311, 231132, 231312, 231321, 232113, 232131, 232311, 233112, 233121, 233211, 311322, 313122, 313212, 313221, 321132, 321312, 321321, 322113, 322131, 322311, 323112, 323121, 323211, 331122, 331212, 331221, 332112, 332121, 332211.

Alois P. Heinz, Table of n, a(n) for n = 0..200

Cf. A000079, A000142, A000680, A006902, A010050, A267479, A267480, A269042.

Column k=2 of A269129.

b:= proc(n) option remember; `if`(n<3, [1$2, 5][n+1], (
      (n^3+n^2-7*n+4)*b(n-1)-2*(2*n-3)*(n-1)^3*b(n-2))/(n-2))
    end:
a:= n-> (2*n)!/(2^n)-b(n):
seq(a(n), n=0..20);

a(n) = (2*n)! * ( 1/(2^n) - Sum_{k=0..n} (-1)^k * C(n,k) / (n+k)! ).
a(n) = A000680(n) - A006902(n).
a(n) = A267479(n,n-1) for n>0.
a(n) = Sum_{k=0..n-1} A267480(n,k).

A268751 Number of sequences with n copies each of 1,2,...,n avoiding the pattern 12...n.

Original entry on oeis.org

0, 0, 1, 374, 16140983, 173996758190594, 791857392420720220446647, 2285085934263252199073238394141449534, 5841526335200139692050292842849347521755651331941759, 17585875137049122003330684747231440185032966840579881629527695901745706

Offset: 0

Alois P. Heinz, Feb 12 2016

nonn

			a(2) = 1: 2211.
a(3) = 374: 111333222, 113133222, 113313222, ..., 333221121, 333221211, 333222111.

Alois P. Heinz, Table of n, a(n) for n = 0..27

Main diagonal of A269129.

Cf. A034841, A268485.

a(n) = A034841(n) - A268485(n).

A269113 Number of sequences with 3 copies each of 1,2,...,n avoiding the pattern 12...n.

Original entry on oeis.org

0, 0, 1, 374, 173891, 117392909, 117108036719, 171248808285596, 360953073372968159, 1072323973643442736211, 4376906243609822466600689, 23919710914189027455648239834, 170865299381465355439286870245691, 1561721420156259852074018974532765369

Offset: 0

Alois P. Heinz, Feb 19 2016

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..165

Column k=3 of A269129.

Cf. A014606, A047910.

a(n) = A014606(n) - A047910(n).

A269114 Number of sequences with 4 copies each of 1,2,...,n avoiding the pattern 12...n.

Original entry on oeis.org

0, 0, 1, 3199, 16140983, 142951955371, 2169397142273171, 54391509124298646609, 2179159866745975811590271, 135383475007869462606521105767, 12672963300072129619006691134123819, 1737368296284036324230735297513232295869

Offset: 0

Alois P. Heinz, Feb 19 2016

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..100

Column k=4 of A269129.

Cf. A014608, A268847.

a(n) = A014608(n) - A268847(n).

A269115 Number of sequences with 5 copies each of 1,2,...,n avoiding the pattern 12...n.

Original entry on oeis.org

0, 0, 1, 26945, 1474050783, 173996758190594, 41489887418194798439, 18675035107760751336633904, 15006398706095549205738572240519, 20584293980310480336378076914369061769, 46436573450646384263588550418764923934014699

Offset: 0

Alois P. Heinz, Feb 19 2016

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..100

Column k=5 of A269129.

Cf. A014609, A268848.

a(n) = A014609(n) - A268848(n).

A269116 Number of sequences with 6 copies each of 1,2,...,n avoiding the pattern 12...n.

Original entry on oeis.org

0, 0, 1, 224296, 132279480115, 208728647384065181, 791857392420720220446647, 6541943110420293280017597411002, 108710813295434106456771753677041770655, 3413618982844502796240740610191874586048936771, 192715148077645864521949395033355447100683080114830089

Offset: 0

Alois P. Heinz, Feb 19 2016

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..91

Column k=6 of A269129.

Cf. A248814, A268849.

a(n) = A248814(n) - A268849(n).

A269117 Number of sequences with 7 copies each of 1,2,...,n avoiding the pattern 12...n.

Original entry on oeis.org

0, 0, 1, 1850672, 11690616534627, 246211478304046636024, 14919265746950486383601562197, 2285085934263252199073238394141449534, 798203800902002138190338074022806761037450631, 586566986371155102435901052470650279895779757665905993

Offset: 0

Alois P. Heinz, Feb 19 2016

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..80

Column k=7 of A269129.

Cf. A172603, A268850.

a(n) = A172603(n) - A268850(n).

A269118 Number of sequences with 8 copies each of 1,2,...,n avoiding the pattern 12...n.

Original entry on oeis.org

0, 0, 1, 15168751, 1020149742404727, 285867869484243410805931, 276745258345325814650980975177139, 789007694236868030155290867470985247486401, 5841526335200139692050292842849347521755651331941759, 101741646114927245552012617872560516024563394870390766150081895

Offset: 0

Alois P. Heinz, Feb 19 2016

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..70

Column k=8 of A269129.

Cf. A172609, A268851.

a(n) = A172609(n) - A268851(n).

cp's OEIS Frontend

A331562 Number A(n,k) of sequences with k copies each of 1,2,...,n avoiding absolute differences between adjacent elements larger than one; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A275784 Number A(n,k) of up-down sequences with k copies each of 1,2,...,n; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A267532 Number of words on {1,1,2,2,...,n,n} with longest increasing subsequence of length < n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A268751 Number of sequences with n copies each of 1,2,...,n avoiding the pattern 12...n.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A269113 Number of sequences with 3 copies each of 1,2,...,n avoiding the pattern 12...n.

Views

Author

Keywords

Links

Crossrefs

Formula

A269114 Number of sequences with 4 copies each of 1,2,...,n avoiding the pattern 12...n.

Views

Author

Keywords

Links

Crossrefs

Formula

A269115 Number of sequences with 5 copies each of 1,2,...,n avoiding the pattern 12...n.

Views

Author

Keywords

Links

Crossrefs

Formula

A269116 Number of sequences with 6 copies each of 1,2,...,n avoiding the pattern 12...n.

Views

Author

Keywords

Links

Crossrefs

Formula

A269117 Number of sequences with 7 copies each of 1,2,...,n avoiding the pattern 12...n.

Views

Author

Keywords

Links

Crossrefs

Formula

A269118 Number of sequences with 8 copies each of 1,2,...,n avoiding the pattern 12...n.

Views

Author