|
|
A194595
|
|
Triangle by rows T(n,k), showing the number of meanders with length (n+1)*3 and containing (k+1)*3 L's and (n-k)*3 R's, where L's and R's denote arcs of equal length and a central angle of 120 degrees which are positively or negatively oriented.
|
|
8
|
|
|
1, 3, 1, 7, 14, 1, 13, 81, 39, 1, 21, 304, 456, 84, 1, 31, 875, 3000, 1750, 155, 1, 43, 2106, 13875, 18500, 5265, 258, 1, 57, 4459, 50421, 128625, 84035, 13377, 399, 1, 73, 8576, 153664, 669536, 836920, 307328, 30016, 584, 1, 91, 15309, 409536, 2815344, 6001128, 4223016, 955584, 61236, 819, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
Definition of a meander:
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 L's increment the index of dir,
(d) consecutive R's decrement the index of dir,
(e) the integer m > 0 divides the length of S and
(f) C is a meander if each value of dir occurs length(S)/m times.
For this sequence, m = 3.
The values in the triangle are proved by brute force for 0 <= n <= 11. The formulas are not yet proved in general. - Susanne Wienand
Let S(N,n,k) = C(n,k)^(N+1)*Sum_{j=0..N} Sum_{i=0..N} (-1)^(N-j+i)*C(N-i,j)*((n+1)/(k+1))^j. Then S(0,n,k) = A007318(n,k), S(1,n,k) = A103371(n,k), S(2,n,k) = T(n,k), S(3,n,k) = A197653(n,k), S(4,n,k) = A197654(n,k), S(5,n,k) = A197655(n,k). - Peter Luschny, Oct 21 2011
The number triangle can be calculated recursively by the number triangles A103371 and A007318. The first column of the triangle contains the central polygonal numbers A002061. The diagonal right hand is A000012. The diagonal with k = n-1 seems to be A027444. Row sums are in A197657. - Susanne Wienand, Nov 24 2011
The conjectured formulas are confirmed by dynamic programming for 0 <= n <= 62. - Susanne Wienand, Jun 24 2015
|
|
LINKS
|
|
|
FORMULA
|
Recursive formula (conjectured):
T(n,k) = T(3,n,k) = T(1,n,k)^3 + T(1,n,k)*T(2,n,n-1-k), 0 <= k < n
T(3,n,n) = 1, k = n
T(2,n,k) = T(1,n,k)^2 + T(1,n,k) * T(1,n,n-1-k), 0 <= k < n
T(2,n,n) = 1, k = n
T(1,n,k) = A007318 (Pascal's Triangle).
Closed formula (conjectured): T(n,k) = (C(n,k))^3 + C(n,k) * C(n,k+1) * C(n+1,k+1). - Susanne Wienand
Let S(n,k) = binomial(2*n,n)^(k+1)*((n+1)^(k+1)-n^(k+1))/(n+1)^k. Then T(2*n,n) = S(n,2). - Peter Luschny, Oct 20 2011
T(n,k) = h(n,k)*binomial(n,k)^3, where h(n,k) = (1+k)*(1-((n-k)/(1+k))^3)/(1+2*k-n) if 1+2*k-n <> 0 else h(n,k) = 3. - Peter Luschny, Nov 24 2011
|
|
EXAMPLE
|
For n = 4 and k = 2, T(3,4,2) = 456.
Recursive example:
T(1,4,0) = 1
T(1,4,1) = 4
T(1,4,2) = 6
T(1,4,3) = 4
T(1,4,4) = 1
T(2,4,0) = 5
T(2,4,1) = 40
T(2,4,2) = 60
T(2,4,3) = 20
T(2,4,4) = 1
T(3,4,0) = T(1,4,0)^3 + T(1,4,0)*T(2,4,4-1-0) = 1^3 + 1*20 = 21
T(3,4,1) = T(1,4,1)^3 + T(1,4,1)*T(2,4,4-1-1) = 4^3 + 4*60 = 304
T(3,4,2) = T(1,4,2)^3 + T(1,4,2)*T(2,4,4-1-2) = 6^3 + 6*40 = 456
T(3,4,3) = T(1,4,3)^3 + T(1,4,3)*T(2,4,4-1-3) = 4^3 + 4*5 = 84
T(3,4,4) = 1.
Example for closed formula:
T(4,2) = (C(4,2))^3 + C(4,2) * C(4,3) * C(5,3) = 6^3 + 6 * 4 * 10 = 456.
Some examples of list S and allocated values of dir if n = 4 and k = 2:
Length(S) = (4+1)*3 = 15 and S contains (2+1)*3 = 9 L's.
S: L,L,L,L,L,L,L,L,L,R,R,R,R,R,R
dir: 1,2,0,1,2,0,1,2,0,0,2,1,0,2,1
S: L,L,R,L,L,L,L,R,R,L,R,R,L,R,L
dir: 1,2,2,2,0,1,2,2,1,1,1,0,0,0,0
S: L,R,R,R,L,L,L,L,R,R,L,L,L,R,L
dir: 1,1,0,2,2,0,1,2,2,1,1,2,0,0,0
Each value of dir occurs 15/3 = 5 times.
|
|
MAPLE
|
A194595 := (n, k)->binomial(n, k)^3*(k^2+k+1+n^2+n-k*n)/((k+1)^2);
|
|
MATHEMATICA
|
T[n_, k_] := Binomial[n, k]^3*(k^2 + k + 1 + n^2 + n - k*n)/((k + 1)^2);
|
|
PROG
|
static int[] GenBinomial(int n, int k)
{
int[, , ] T = new int[k, n, n ];
for (int m = 0; m < n; m++)
{
T[0, m, 0] = 1; T[0, m, m] = 1;
for (int j = 1; j < m; j++)
{
T[0, m, j] = T[0, m - 1, j] + T[0, m - 1, j - 1];
}
for (int r = 1; r < k; r++)
{
T[r, m, m] = 1;
for (int j = 0; j < m; j++)
{
int p = (int)Math.Pow(T[0, m, j], r + 1);
T[r, m, j] = p + T[0, m, j] * T[r - 1, m, m - j - 1];
}
}
}
int[] R = new int[n];
for (int j = 0; j < n; j++)
{
R[j] = T[k - 1, n - 1, j];
}
return R;
}
{
return GenBinomial(r, 3);
}
// This C#-program causes numerical overflow for results
(PARI)
A194595(n, k) = {if(n == 1+2*k, 3, (1+k)*(1-((n-k)/(1+k))^3)/(1+2*k-n))*binomial(n, k)^3} \\ Peter Luschny, Nov 24 2011
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|