This site is supported by donations to The OEIS Foundation.

User:Peter Luschny/Meander

From OeisWiki

Jump to: navigation, search

Meanders  and
 Walks on a Circle

KEYWORDS: Binary curves, meanders, walks on a circle.

Concerned with sequences:
A198060, A199932, A200062, A200583; A007318, A000012, A000079; A103371, A003056, A001700; A194595, A073254, A197657; A197653, A198063, A198256; A197654, A198064, A198257; A197655, A198065, A198258.

Contents

The definitions

Satellite photo of the Songhua River in northeast China.

Recently Susanne Wienand contributed a series of sequences to the OEIS related to meanders which we want to explore. But what are meanders? Roughly speaking meanders are closed curves drawn by arcs (and only arcs). In particular we will look at meanders whose arcs have a fixed central angle and have equal length. However, the term 'meander' is used in many different ways and therefore we will elaborate on the formal definition used here.

Definition. A binary curve C is a pair (m, S) such that
   (a) S is a list with values in {L, R} which
   (b) starts with an L, and
   (c) m > 0 is an integer which divides the length of S.

Given a binary curve C = (m, S) we call m the modulus of the curve and S the steps of C. The use of 'L' and 'R' here is for mnemonic reason: 'L' stands for a positively oriented arc (left curve) and 'R' for a negatively oriented arc (right curve).

Examples. C1 = (2, LRRLRR) and C2 = (3, LRRRLL) are binary curves of length 6. In contrast neither (3, LRRRLLR) nor (2, RLRRRL) is a binary curve.

Next we associate with each step of a binary curve a direction. To this end we define a function dir: S → [0..m-1] recursively.

Definition: The first step has direction 1, dir(S[0]) = 1. Assume now step n > 0.
dir(S[n]) = (dir(S[n−1])+[S[n]=L=S[n−1]]−[S[n]=R=S[n−1]]) mod m.

Here [ ] is the Iverson bracket. This means [S[n]=Y=S[n-1]] = 1 if  S[n] = Y and S[n-1] = Y, otherwise 0.

We say a binary curve changes direction if two consecutive steps are of the same type. Thus whenever a binary curve changes direction the direction of the curve is increased by one if the step is of type L and decreased by one if the step is of type R, modulo m.

Mapping the direction function on the steps of a binary curve gives a list DIR(C) of length(S).

For example let S = LLLLRLLRLLRLRRLLLLLRRLLLRRRRLR and C = (6,S). Then DIR(C) = 123444555000055012332234432111.

Definition. A binary curve C = (m, S) is a meander if and only if each of the values 0,..,m-1 occur with equal frequency in DIR(C).

In the last example above this is indeed the case.

The routine 'isMeander' below decides if a given binary curve is a meander. It counts the number of occurrences of the values of dir(S[n]) and as soon as a value occurs more than length(S)/m times returns with 'false'. If this does not happen all values are equal distributed and the routine returns 'true'.

def isMeander(m, S) :   # Sage/Phython
    vec = [0]*m
    max = len(S) // m
    dir = 0
    os = S[0]
    for s in S :
        if s and os :
            dir = dir + 1
        elif not s and not os :
            dir = dir - 1
        dir = dir % m
        v = vec[dir] + 1
        vec[dir] = v
        if v > max :
            return False
        os = s
    return True

Remark: A meander is a closed curve. Conversely, a closed curve is not necessarily a meander.

For example let S = LRRRRRRRRRRRLRLLRRRRRLRL. Then the binary curve (6, S) is closed but not a meander. On the other hand the binary curve (2, S) is a meander.

Plotting meanders

With Asymptote, a vector graphics language based on previous work of John D. Hobby (MetaPost) and Donald E. Knuth's MetaFont, meanders are easily visualized.

size(12cm,0);
bool L = true, R = false, StepLast;
real AngInc, Ang;
pair Z, A;

void Step(bool StepAct)
{
    if(StepLast != StepAct)
    {
        Z = 2*A - Z; Ang += 180;
    }
    real OldAng = Ang;
    Ang += StepAct ? AngInc : -AngInc;
    A = Z + dir(Ang);
    pen Pen = StepAct ? orange : green;
    draw(arc(Z,1,OldAng,Ang,StepAct),Pen,ArcArrow);
    StepLast = StepAct;
}

void Walk(int m, bool[] steps)
{
    AngInc = 360 / m;
    Ang = AngInc;
    StepLast = L;
    Z = (0,0); 
    A = Z + (1,0);

    for(bool s : steps) Step(s);
}

bool[] meander = 
{L,R,L,L,L,R,R,R,R,L,R,R,L,R,L,L,L,L,R,L,L,R,L,L,L};
Walk(5, meander); shipout("Meander", bbox(0.3cm));

Enumerating meanders

Susanne Wienand posed the question:

In how many ways can a meander be drawn by arcs with a central angle of 360/m degrees and of equal length, (n-k)m of which are negatively and (k+1)m positively oriented, starting with a positively oriented arc? (m>0, n≥0, k≥0)

Wienand computed some of the values by brute force and observed that these values also can be found using a recurrence (see her article on OpenCS). Using the Iverson bracket [ ] this recurrence can be written:

T(m,n,k) = {\binom{n}{k}}^m + \left[m>1\right] \binom{n}{k} T(m-1,n,n-1-k).

Or with Maple:

T := proc(m, n, k) local b; b := binomial(n, k);
     if m > 1 then b := b * (b^(m-1) + T(m-1,n,n-1-k)) fi; 
     b end:

For fixed m we get a numerical triangle. For example in the case m = 5 we find:

m = 5            
n \ k 0 1 2 3 4 Sum
0 1         1
1 5 1       6
2 31 62 1     94
3 121 1215 363 1   1700
4 341 13504 20256 1364 1  35466

The first step

Our exposition is based on a single function. This function gives for m = 0,1,2,... a sequence of integer triangles similar to Pascal's triangle, with which they share the symmetry between left and right.

P(m,n,k) = Sum{j=0..m}Sum{i=0..m}(-1)^(j+i)C(i,j) n^j k^(m-j)

The sequences start with the simplest sequence of all; the first six cases are:

m   T(n, k) Sum_{k=0..n} T(n, k) Sum(n,k)
P(0,n,k) A000012 1 n+1 A000027
P(1,n,k) A003056 n n^2+n A002378
P(2,n,k) A073254 k^2-kn+n^2 (5n^3+6n^2+n)/6 A033994
P(3,n,k) A198063 2k^2n-2kn^2+n^3 (2n^4+3n^3
+n^2)/3
A098077
P(4,n,k) A198064 k^4-2k^3n+4k^2n^2
-3kn^3+n^4
(16n^5+30n^4
+15n^3-n)/30
 
P(5,n,k) A198065 3nk^4-6k^3n^2
+7k^2n^3-4kn^4+n^5
(13n^6+30n^5
+20n^4-3n^2)/30
 

A simple way to compute this family of sequences is:

G := proc(m, n, k) if n = 2*k then m*k^(m-1)
     else (k^m-(n-k)^m)/(2*k-n) fi end:

Then G(m, n, k) = P(m-1, n, k) for m > 0.

The second step

On top of this sequence of triangles we define a second sequence of triangles. The first triangle is Pascal's triangle.

A007318(n,k) = A000012(n+1,k+1)C(n,k)^1/(k+1)^0 = H(1,n,k) 
A103371(n,k) = A003056(n+1,k+1)C(n,k)^2/(k+1)^1 = H(2,n,k) 
A194595(n,k) = A073254(n+1,k+1)C(n,k)^3/(k+1)^2 = H(3,n,k) 
A197653(n,k) = A198063(n+1,k+1)C(n,k)^4/(k+1)^3 = H(4,n,k) 
A197654(n,k) = A198064(n+1,k+1)C(n,k)^5/(k+1)^4 = H(5,n,k) 
A197655(n,k) = A198065(n+1,k+1)C(n,k)^6/(k+1)^5 = H(6,n,k) 

These triangles can be computed with Maple as follows:

H := proc(m, n, k) if n = 1+2*k then m
     else (1+k)*(1-((n-k)/(1+k))^m)/(1+2*k-n) fi; 
     %*binomial(n, k)^m end:

Note that in this function the factor of binomial(n, k)^m can also be written as a sum.

\sum_{i=0}^{m-1}\left(\frac{n-k}{k+1}\right)^i = \begin{cases}
m & \text{if } n = 1+2k; \\
\left(1- \left({\frac{n-k}{1+k}}\right)^m\right)\frac{1+k}{1+2k-n} & \text{otherwise. }
\end{cases}

The special case H(m, 2n, n) is particularly simple:

H(m,2n,n) = C(2n,n)^(m+1)*((n+1)^(m+1)-n^(m+1))/(n+1)^m.

Next we look at the row sums of these triangles.

J := proc(m, n) local k; 
     add(H(m, n, k),k=0..n) end:
A000079(n) = Sum{k=0..n} A007318(n,k) = J(1,n)
A001700(n) = Sum{k=0..n} A103371(n,k) = J(2,n)
A197657(n) = Sum{k=0..n} A194595(n,k) = J(3,n)
A198256(n) = Sum{k=0..n} A197653(n,k) = J(4,n)
A198257(n) = Sum{k=0..n} A197654(n,k) = J(5,n)
A198258(n) = Sum{k=0..n} A197655(n,k) = J(6,n)


J(m,n) = \sum_{k=0}^{n} {\binom{n}{k}}^m \times 
\begin{cases}m & \text{if } n = 1+2k; \\ 
\left(1- \left({\frac{n-k}{1+k}}\right)^m\right)\frac{1+k}{1+2k-n} & \text{otherwise. }
\end{cases}

These sums are the answer to our problem. Thus J(m, n) is the number of ways a meander can be drawn by m(n+1) arcs with a central angle of 360/m degrees and of equal length, starting with a positively oriented arc.

Walks on a circle

We give another interpretation of the meanders as walks on a circle, starting and ending in the same point. Now a 'step' equates to an 'arc' and the 'orientation' (positively/negatively) to the 'direction' (forward/backwards). This gives a bijection between the meanders and the walks on the circle subject to the meander condition. The problem can now be restated as:

How many walks on the circle exist returning to the start with m(n+1) steps with m(k+1) forward steps and m(n-k) backward steps, provided that the first step is a forward step and each sector is visited with equal frequency.

width=326px

A script for plotting these walks with Asymptote is given below. It requires as an input a binary representation of the walk given as a list of L's and R's which denote the direction (respectively the orientation) of the step.

// Walks on the circle.

size(200,200);

int  deg = 60;
int  a = -deg;
int  b = 0;
real r = 0.3;
bool dir = CCW;  // CounterClockWise
bool L = true, R = false;
bool lastDir = L;

pen PurplePen = purple+0.5mm;
pen OrangePen = orange+0.5mm;
pen Pen = OrangePen;

void Step(bool dir)
{
   if(lastDir == dir)
   {
       int i = dir ? deg : -deg;
       a += i; b += i;
   }
   else 
   {
       int c = a; a = b; b = c; 
       r += 0.1; 
       Pen = dir ? OrangePen : PurplePen;
       lastDir = dir;
   }
   draw(arc((0,0),r,a,b,lastDir),Pen,Arrow(2mm));
}

void Walk(bool[] s)
{
    for(bool s : S) Step(s);
}

//  m = 6, 360/m = 60 deg, n = 4, k = 2, 
// (k+1)*m = 18 forward steps  ('L'),
// (n-k)*m = 12 backward steps ('R'), 30 steps in total.

bool[] steps = 
{L,L,L,L,R,L,L,R,L,L,R,L,R,R,L,L,L,L,L,R,R,L,L,L,R,R,R,R,L,R};
Walk(steps); shipout("WalkingTheCircle", bbox(0.3cm));

Safe cracking

Visualize a safe and the movements of the lock necessary to open the safe. These movements can be interpreted as a walk on a circle. Fix a carve on the moveable part of the lock, say at the number 0, and watch this carve when opening the safe. The trace of the carve will look like a walk on a circle as in the plot above.

Image: Combinatoria by rpongsaj, Boston Public Library.

Wienand's question can now be rephrased as: How many secret codes exist if the structural design of the lock was a meander?

What we need next is a way to generate all possible secret codes fast. Then it is not difficult to build a device which can crack a meander lock by trying the codes. We will for obvious reasons not enlarge upon this topic. But you can watch a similar device in action on YouTube, a robotic safe cracker.

Generating meanders

Still we have to find a way to generate meanders. Susanne Wienand gives a brute force search on her user page. A 'brute force search' here means that all 2^n combinations are tested whether they satisfy the meander condition.

We will give a version which makes use of the modular structure of the problem, i.e. that (k+1)m forward steps and (n-k)m are backward steps are looked for. This reduces the number of test cases considerably. The implementation is in Sage.

Basically it consists of three simple functions:

  • parts
    Lists the partitions which are the candidates to be scanned.
  • isMeander
    Tests if a binary curve is a meander. (This function was given above.)
  • generateMeanders
    Filters the candidates according to the criterion.
def parts(m, len) :
    a = m
    p = []
    while True :
       b = len - a
       if a > len : break
       p.append([a, b])
       a = a + m
    return p 
    
def generateMeanders(m, len) :
    count = 0
    P = parts(m, len)
    for p in P :
        S = [True for i in range(p[0])]+[False for j in range(p[1])]
        for c in Permutations(S) :
            if not c[0] : continue
            if isMeander(m, c) : 
                count = count + 1
                PrintAsBinaryString(c) 
    return count

A faster version written in C# can be found on the author's homepage.

Representing the meanders as binary strings ('L' maps to '1' and 'R' maps to '0') we give some examples of simple cases. The meanders are listed in the coolex order as given by the C# program.

m len card meander m len card meander
1 3 4

100
101
110
111

3 9 22

100000011
100010001
110000001
100100100
100011000
110001000
111000000
100011111
110001111
111000111
100111011
101110011
111100011
110011101
101101101
110111001
111110001
111001110
110110110
111011100
111111000
111111111

2 6 10

100001
100100
110000
100111
110011
101101
111001
110110
111100
111111

3 6 4

100011
110001
111000
111111

4 8 5

10000111
11000011
11100001
11110000
11111111

Meanders of length n

Let us look now at meanders of length n. They come in two flavors: First we count all meanders and then only those with central angle < 360°.

len 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A199932 1 3 5 12 17 47 65 169 279 645 1025 2698 4097 9917 17345
A200062 0 1 1 4 1 15 1 41 23 133 1 650 1 1725 961

Three observations are immediate:

The first observation comes from the fact that meanders with central angle equal to 360° are counted by the (n-1)-th row of Pascal's triangle. The second observation is obviously true. The third is a consequence of the first two facts.

Here you can download the plots as a pdf for the cases n = 6, n = 8 and n = 9.

More generally we might look at the table of meanders of length n and central angle 360/m. In this funny shaped table the nonzero entries in the rows are indexed by the divisors of n. For example the values in row 12 refer to meanders with central angle 360/m where m = 1, 2, 3, 4, 6 and 12 respectively.

n \ m  1  2  3  4  5  6 Sum
1 1           1
2 2 1         3
3 4   1       5
4 8 3   1     12
5 16       1   17
6 32 10 4     1 47
7 64           65
8 128 35   5     169
9 256   22       279
10 512 126     6   645
11 1024           1025
12 2048 462 134 46   7 2698
13 4096           4097
14 8192 1716         9917
15 16384   866   94   17345
16 32768 6435   485     39698
17 65536           65537
18 131072 24310 5812     190 161395
19 262144           262145
20 524288 92378   5626 1700   624004
21 1048576   40048       1089007
OEIS A000079 A001700 A197657 A198256 A198257   A199932

This table read by rows is A200583. Another systematic overview with a formula which covers all cases is given by A198060. One might also observe the curved diagonals, for example the third one 4, 10, 22, 46, 94, 190,...  which is A099018 (A033484).

Looking at the row sums we are indeed back at an extended version of the formula given above as the first step. It can be written as:

A199932(n) = Sum_{d|n} A198060(d−1,n/d−1).

In other symbols, the meanders of length n are given by:

M_n = \sum_{d \mid n}\sum_{k=0}^{\frac{n}{d}-1}\sum_{j=0}^{d-1}\sum_{i=0}^{d-1}(-1)^{j+i} \binom{i}{j}{\binom{n/d-1}{k}}^{d} \left(\frac{n}{d(k+1)} \right)^{j}

For those who whish to test such a formidable formula we offer a Maple snippet.

M := proc(n) local d, k, j, i; add(add(add(add(
(-1)^(j+i)*binomial(i,j)*binomial(n/d-1,k)^d*((n/d)/(k+1))^j,
i=0..d-1),j=0..d-1),k=0..(n/d-1)),d=numtheory[divisors](n))end:


Invertible meanders

A meander a = (a_1, .., a_n) is invertible if and only if
a* := (~a_n, .., ~a_(n-k+1), .., ~a_1) is a meander.
In this case we call a* the dual of a (or the reversed complement of a).

Here '~' denotes the negation operator and in the definition of the meander 'L' and 'R' is to be read as the Boolean values 'true' and 'false' respectively.

Examples:

  • (10001010)* = 10101110. 
  • The binary sequence (6, 110011101) is a meander but is not an invertible meander.
  • The figure below shows an invertible meander and its dual.

A more functional way to express these relations is:

Let {0,1}^n denote the set of all strings of length n with values 0 or 1. Then define an operator R : {0,1}^n → {0,1}^n which reverses a string and an operator ' : {0,1}^n → {0,1}^n which complements bit-wise the values of the string, setting 0' = 1 and 1' = 0. Then M* = R(M'). Clearly M** = M since R(R(M')') = R(s_n, ..., s_1) = R(s_n, ..., s_1) = (s_1, ..., s_n) = M.

Proposition: Let M be (the binary representation of) a meander. Then M* is a meander if and only if the last bit of M is 0.

'→' If M* is a meander then it starts with bit 1. Thus M = M** = R(M*') = R(1',...,s_n') = (s_n',...,0).
'←' Since the last bit of M is 0 the first bit of M* is 1. We have to check that the directions of M* appear equally often. Since M is a meander every direction in M will lead to a direction in M* of the opposite kind. In fact DIR(M*) is the reverse of DIR(M) and therefore a direction is assumed with equal frequency in M and in M*. Thus M* is indeed a meander. q.e.d.

The table below counts the invertible meanders of length n and of type m.

n \ m  1  2  3  4  5  6  7 Sum
1 0             0
2 1 0           1
3 2   0         2
4 4 1   0       5
5 8       0     8
6 16 4 1     0   21
7 32           0 32
8 64 15   1       80
9 128   8         136
10 256 56     1     313
11 512             512
12 1024 210 54 16   1   1305
13 2048             2048
14 4096 792         1 4889
15 8192   368   32     8592
16 16384 3003   189       19577
17 32768             32768
18 65536 11440 2550     64   79591
19 131072             131072
20 262144 43758   2336 648     308886
21 524288   17952       128 542368
OEIS A000079 A001791 A201640         A201642

New sequences are A201640 = 0, 1, 8, 54, 368, 2550, 17952, 128086, ...
and in the case m = 4 the sequence 0, 1, 16, 189, 2336, 29750, 389712, ...

Again the columns of the tables can be seen as the row sums of symmetric triangles similar to Pascal's triangle. These triangles classify the invertible meanders on a finer scale by looking at their binary sum. (The binary sum of a meander is the sum of the binary digits of the binary representation of the meander, for instance the binary sum of 110011101 is 6.)

Case m = 2: A001791 are the row sums of the triangle A132812.

A132812 := (n,k) -> (n-k)*binomial(n,k)^2/(1+k);

                 0
                1, 0 
              2, 2, 0 
             3, 9, 3, 0 
          4, 24, 24, 4, 0 
        5, 50, 100, 50, 5, 0 
      6, 90, 300, 300, 90, 6, 0
   7, 147, 735, 1225, 735, 147, 7, 0

Case m = 3: A201640 are the row sums the triangle A202409:

A202409 := (n,k) -> `if`(n=0,0,
           (n-k)*binomial(n,k)^3*(n^2-k*n+k+k^2)/((1+k)^2*n));

                     0, 
                    1, 0,
                  4, 4, 0,
                9, 36, 9, 0,
            16, 168, 168, 16, 0,
           25, 55, 140, 55, 25, 0,
      36, 1440, 7500, 7500, 1440, 36, 0,
  49, 3234, 30135, 61250, 30135, 3234, 49, 0,

In general the m-th column lists the row sums of the triangle A_m where A_m(n, k) is the number of meanders of length (n+1)m which have binary sum mk.

For example the entry in the table for n = 12 and m = 3 says that there are 54 invertible meanders of length 12 and modulus 3. The 3rd row of the triangle A202409, which is [9, 36, 9], tells us that 9 of those have binary sum 3, 36 have binary sum 6 and 9 binary sum 9.

Non-invertible meanders

The table below counts the non-invertible meanders of length n and of type m.

n \ m  1  2  3  4  5  6  7 Sum
1 1             1
2 1 1           2
3 2   1         3
4 4 2   1       7
5 8       1     9
6 16 6 3     1   26
7 32           1 33
8 64 20   4       89
9 128   14         143
10 256 70     5     332
11 512             513
12 1024 252 80 30   6   1393
13 2048             2049
14 4096 924         7 5028
15 8192   498   62     8753
16 16384 3432   296       20121
17 32768             32769
18 65536 12870 3262     126   81804
19 131072             131073
20 262144 48620   3290 1052     315118
21 524288   22096       254 546639
OEIS A000079 A000984 A202410         A202411

New sequences are A202410 = 1, 3, 14, 80, 498, 3262, 22096, ...
and in the case m = 4 the sequence 1, 4, 30, 296, 3290, 39312, ...

Again the columns of the tables can be seen as the row sums of triangles. These triangles classify the non-invertible meanders by their binary sum.

Case m = 2: A000984 are the row sums of the triangle A008459.

Thus the number of non-invertible meanders classified by their binary sum are in the case m = 2 the square of the entries of Pascal's triangle.

A008459 := (n,k) -> binomial(n,k)^2;

                1 
              1, 1 
            1, 4, 1 
          1, 9, 9, 1 
        1, 16, 36, 16, 1 
      1, 25, 100, 100, 25, 1
   1, 36, 225, 400, 225, 36, 1

Case m = 3: A202410 are the row sums of the triangle A:

A := (n,k) -> `if`(n=0,1,
               binomial(n,k)^3*(k^2-k*n+n+n^2)/(n*(1+k)));

                   1,
                 2, 1,
               3, 10, 1,
             4, 45, 30, 1,
           5, 136, 288, 68, 1,
        6, 325, 1600, 1200, 130, 1,
   7, 666, 6375, 11000, 3825, 222, 1,

Self-dual meanders

A meander M is self-dual if and only if M is an invertible meander and M = M*.

For example 10110010 is a self-dual meander. Note that a meander of odd length cannot be a self-dual meander. The table below enumerates the self-dual meanders.

n \ m  1  2  3  4  5  6  7 Sum
1 0             0
2 1 0           1
3 0   0         0
4 2 1   0       3
5 0       0     0
6 4 0 1     0   5
7 0           0 0
8 8 3   1       12
9 0   0         0
10 16 0     1     17
11 0             0
12 32 10 4 0   1   47
13 0             0
14 64 0         1 65
15 0   0   0     0
16 128 35   5       169
17 0             0
18 256 0 22     1   279
19 0             0
20 512 126   0 6     645
21 0   0       0 0
OEIS A000079 A138364

A001700

A088218
A197657 A198256 A198257     A199932

The columns in this table are an aerated version of the columns of the table A200583 above. The figure below shows an example of a self-dual meander.

Next month we will look at Fibonacci meanders.

Acknowledgments

I would like to thank Susanne Wienand for helpful discussions. I also would like to acknowledge the work of the Project Euler team. It was a PE-problem that inspired this investigation.

Appendix

J(m, n) as hypergeometric sums

A000079 := n -> Sum{k=0..n} A007318(n,k);
h01 := n -> hypergeom([-n],[],-1);
A000079 := n -> h01(n);
A001700 := n -> Sum{k=0..n} A103371(n,k);
h11 := n -> hypergeom([-n,-n],[2],1);
A001700 := n -> (n+1)*h11(n);
A197657 := n -> Sum{k=0..n} A194595(n,k);
h21 := n-> hypergeom([-n,-n,-n],[2,2],-1); 
h22 := n-> hypergeom([1-n,1-n,1-n],[3,3],-1); 
h23 := n-> hypergeom([2,1-n,1-n,1-n],[1,3,3],-1);
A197657 := n -> (h22(n)*(n^3-n^4)+h21(n)*4*(1+n+n^2)+n^3*h23(n))/4; 
A198256 := n -> Sum{k=0..n} A197653(n,k);
h31:= n-> hypergeom([-n,-n,-n,-n],[2,2,2],1);
h32:= n-> hypergeom([1-n,1-n,1-n,1-n],[3,3,3],1);
h33:= n-> hypergeom([2,1-n,1-n,1-n,1-n],[1,3,3,3],1);
A198256 := n -> h32(n)*(n^4-n^6)/4+h31(n)*(1+n+n^2+n^3)+h33(n)*(n^4+n^5)/4;

P(m, n, k) as binomial-like triangles

A000012(n, k) = P(0,n,k)

                    1
                   1, 1
                 1, 1, 1
                1, 1, 1, 1
              1, 1, 1, 1, 1
             1, 1, 1, 1, 1, 1

A003056(n, k) = P(1,n,k)

                    0
                   1, 1
                 2, 2, 2
                3, 3, 3, 3
              4, 4, 4, 4, 4
             5, 5, 5, 5, 5, 5

A073254(n, k) = P(2,n,k)

                    0
                   1, 1
                 4, 3, 4
                9, 7, 7, 9
            16, 13, 12, 13, 16
          25, 21, 19, 19, 21, 25

A198063(n, k) = P(3,n,k)

                    0
                   1, 1
                 8, 4, 8
              27, 15, 15, 27
            64, 40, 32, 40, 64
         125, 85, 65, 65, 85, 125

A198064(n, k) = P(4,n,k)

                    0
                   1, 1
                16, 5, 16
              81, 31, 31, 81
          256, 121, 80, 121, 256
       625, 341, 211, 211, 341, 625

A198065(n, k) = P(5,n,k).

                     0
                    1, 1
                 32, 6, 32
              243, 63, 63, 243
         1024, 364, 192, 364, 1024
      3125, 1365, 665, 665, 1365, 3125
Personal tools