|
%I #36 Mar 24 2023 08:32:15
%S 1,1,2,1,3,4,1,4,10,8,1,5,22,35,16,1,6,46,134,126,32,1,7,94,485,866,
%T 462,64,1,8,190,1700,5626,5812,1716,128,1,9,382,5831,35466,69062,
%U 40048,6435,256,1,10,766,19682,219626,795312,882540,281374,24310,512
%N Array read by antidiagonals, m>=0, n>=0, A(m,n) = Sum_{k=0..n} Sum_{j=0..m} Sum_{i=0..m} (-1)^(j+i)*C(i,j)*C(n,k)^(m+1)*(n+1)^j*(k+1)^(-j).
%C We repeat the definition of a meander as given in the link below and used in the sequences in the cross-references:
%C A binary curve C is a triple (m, S, dir) such that:
%C (a) S is a list with values in {L, R} which starts with an L,
%C (b) dir is a list of m different values, each value of S being allocated a value of dir,
%C (c) consecutive Ls increment the index of dir,
%C (d) consecutive Rs decrement the index of dir,
%C (e) the integer m > 0 divides the length of S.
%C (f) C is a meander if each value of dir occurs length(S) / m times.
%C The rows of the array A(m, n) show the number of meanders of length n and central angle 360/m as specified by the columns of a table in the given link. - _Peter Luschny_, Mar 20 2023
%H Peter Luschny, <a href="http://oeis.org/wiki/User:Peter_Luschny/Meander">Meanders and walks on the circle</a>.
%F From _Peter Bala_, Apr 22 2022: (Start)
%F Conjectures:
%F 1) the m-th row entries satisfy the Gauss congruences T(m, n*p^r - 1) == T(m, n*p^(r-1) - 1) (mod p^r)) for primes p >= 3 and positive integers n and r.
%F 2) for m even, the m-th row entries satisfy the congruences T(m, p^r - 1) == 2^(p^r - 1) (mod p^2) for primes p >= 3 and positive integers r.
%F 3) for m odd, the m-th row entries satisfy the supercongruences T(m,n*p^r - 1) == T(m,n*p*(r-1) - 1) (mod p^(3*r)) for primes p >= 5 and positive integers n and r. (End)
%e Array A(m, k) starts:
%e m\n [0] [1] [2] [3] [4] [5] [6]
%e --------------------------------------------------
%e [0] 1 2 4 8 16 32 64 A000079
%e [1] 1 3 10 35 126 462 1716 A001700
%e [2] 1 4 22 134 866 5812 40048 A197657
%e [3] 1 5 46 485 5626 69062 882540 A198256
%e [4] 1 6 94 1700 35466 795312 18848992 A198257
%e [5] 1 7 190 5831 219626 8976562 394800204 A198258
%e .
%e Triangle T(m, k) starts:
%e [0] 1;
%e [1] 2, 1;
%e [2] 4, 3, 1;
%e [3] 8, 10, 4, 1;
%e [4] 16, 35, 22, 5, 1;
%e [5] 32, 126, 134, 46, 6, 1;
%e [6] 64, 462, 866, 485, 94, 7, 1;
%e [7] 128, 1716, 5812, 5626, 1700, 190, 8, 1;
%e .
%e Using the representation of meanders as multiset permutations (see A361043) and generated by the Julia program below.
%e T(3, 0) = 8 = card(1000, 1100, 1010, 1001, 1110, 1101, 1011, 1111).
%e T(3, 1) = 10 = card(110000, 100100, 100001, 111100, 111001, 110110, 110011, 101101, 100111, 111111).
%e T(3, 2) = 4 = card(111000, 110001, 100011, 111111).
%e T(3, 3) = 1 = card(1111).
%p A198060 := proc(m, n) local i, j, k; add(add(add((-1)^(j+i)*binomial(i, j)* binomial(n, k)^(m+1)*(n+1)^j*(k+1)^(-j), i=0..m), j=0..m), k=0..n) end:
%p for m from 0 to 6 do seq(A198060(m, n), n=0..6) od;
%t a[m_, n_] := Sum[ Sum[ Sum[(-1)^(j + i)*Binomial[i, j]*Binomial[n, k]^(m+1)*(n+1)^j*(k+1)^(m-j)/(k+1)^m, {i, 0, m}], {j, 0, m}], {k, 0, n}]; Table[ a[m-n, n], {m, 0, 9}, {n, 0, m}] // Flatten (* _Jean-François Alcover_, Jun 27 2013 *)
%o (SageMath) # This function assumes an offset (1, 1).
%o def A(m: int, n: int) -> int:
%o S = sum(
%o sum(
%o sum((
%o (-1) ** (j + i)
%o * binomial(i, j)
%o * binomial(n - 1, k) ** m
%o * n ** j )
%o // (k + 1) ** j
%o for i in range(m) )
%o for j in range(m) )
%o for k in range(n) )
%o return S
%o def Arow(n: int, size: int) -> list[int]:
%o return [A(n, k) for k in range(1, size + 1)]
%o for n in range(1, 7): print([n], Arow(n, 7)) # _Peter Luschny_, Mar 24 2023
%o # These functions compute the number of meanders by generating and counting.
%o # Their primary purpose is to illustrate that meanders are a special class of
%o # multiset permutations. They are not suitable for numerical calculation.
%o (Julia)
%o using Combinatorics
%o function isMeander(m::Int, c::Vector{Bool})::Bool
%o l = length(c)
%o (l == 0 || c[1] != true) && return false
%o vec = fill(Int(0), m)
%o max = div(l, m)
%o dir = Int(1)
%o ob = c[1]
%o for b in c
%o if b && ob
%o dir += 1
%o elseif !b && !ob
%o dir -= 1
%o end
%o dir = mod(dir, m)
%o v = vec[dir + 1] + 1
%o vec[dir + 1] = v
%o if v > max
%o return false
%o end
%o ob = b
%o end
%o true end
%o function CountMeanders(n, k)
%o n == 0 && return k + 1
%o count = 0
%o size = n * k
%o for a in range(0, stop=size; step=n)
%o S = [(i <= a) for i in 1:size]
%o count += sum(1 for c in multiset_permutations(S, size)
%o if isMeander(n, c); init = 0)
%o end
%o count end
%o A198060ByCount(m, n) = CountMeanders(m + 1, n + 1)
%o for n in 0:4
%o [A198060ByCount(n, k) for k in 0:4] |> println
%o end
%o # _Peter Luschny_, Mar 20 2023
%Y T(n, 2) = A033484(n+1).
%Y Cf. A033484, A000079, A001700, A197657, A198256, A198257, A198258, A198061.
%Y Cf. A361043.
%K nonn,tabl
%O 0,3
%A _Peter Luschny_, Nov 01 2011
|
