OFFSET
0,3
COMMENTS
We repeat the definition of a meander as given in the link below and used in the sequences in the cross-references:
A binary curve C is a triple (m, S, dir) such that:
(a) S is a list with values in {L, R} which starts with an L,
(b) dir is a list of m different values, each value of S being allocated a value of dir,
(c) consecutive Ls increment the index of dir,
(d) consecutive Rs decrement the index of dir,
(e) the integer m > 0 divides the length of S.
(f) C is a meander if each value of dir occurs length(S) / m times.
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
LINKS
Peter Luschny, Meanders and walks on the circle.
FORMULA
From Peter Bala, Apr 22 2022: (Start)
Conjectures:
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.
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.
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)
EXAMPLE
m\n [0] [1] [2] [3] [4] [5] [6]
--------------------------------------------------
[0] 1 2 4 8 16 32 64 A000079
[1] 1 3 10 35 126 462 1716 A001700
[2] 1 4 22 134 866 5812 40048 A197657
[3] 1 5 46 485 5626 69062 882540 A198256
[4] 1 6 94 1700 35466 795312 18848992 A198257
[5] 1 7 190 5831 219626 8976562 394800204 A198258
.
Using a representation of meanders as multisets as given in the program section:
A(1, 2) = 10 = card(110000, 100100, 100001, 111100, 111001, 110110, 110011, 101101, 100111, 111111). Note that this is a subset of the 32 multiset permutations A361043(2, 4).
MAPLE
MATHEMATICA
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 *)
PROG
(SageMath) # This function assumes an offset (1, 1).
def A(m: int, n: int) -> int:
S = sum(
sum(
sum((
(-1) ** (j + i)
* binomial(i, j)
* binomial(n - 1, k) ** m
* n ** j )
// (k + 1) ** j
for i in range(m) )
for j in range(m) )
for k in range(n) )
return S
def Arow(n: int, size: int) -> list[int]:
return [A(n, k) for k in range(1, size + 1)]
for n in range(1, 7): print([n], Arow(n, 7)) # Peter Luschny, Mar 24 2023
# These functions compute the number of meanders by generating and counting.
# Their primary purpose is to illustrate that meanders are a special class of
# multiset permutations. They are not suitable for numerical calculation.
(Julia)
using Combinatorics
function isMeander(m::Int, c::Vector{Bool})::Bool
l = length(c)
(l == 0 || c[1] != true) && return false
vec = fill(Int(0), m)
max = div(l, m)
dir = Int(1)
ob = c[1]
for b in c
if b && ob
dir += 1
elseif !b && !ob
dir -= 1
end
dir = mod(dir, m)
v = vec[dir + 1] + 1
vec[dir + 1] = v
if v > max
return false
end
ob = b
end
true end
function CountMeanders(n, k)
n == 0 && return k + 1
count = 0
size = n * k
for a in range(0, stop=size; step=n)
S = [(i <= a) for i in 1:size]
count += sum(1 for c in multiset_permutations(S, size)
if isMeander(n, c); init = 0)
end
count end
A198060ByCount(m, n) = CountMeanders(m + 1, n + 1)
for n in 0:4
[A198060ByCount(n, k) for k in 0:4] |> println
end
# Peter Luschny, Mar 20 2023
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Peter Luschny, Nov 01 2011
STATUS
editing