|
| |
|
|
A197654
|
|
Triangle by rows T(n,k), showing the number of meanders with length 5(n+1) and containing 5(k+1) L's and 5(n-k) R's, where L's and R's denote arcs of equal length and a central angle of 72 degrees which are positively or negatively oriented.
|
|
8
|
|
|
|
1, 5, 1, 31, 62, 1, 121, 1215, 363, 1, 341, 13504, 20256, 1364, 1, 781, 96875, 500000, 193750, 3905, 1, 1555, 501066, 7321875, 9762500, 1252665, 9330, 1, 2801, 2033647, 72656661, 262609375, 121094435, 6100941, 19607, 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.
Then C is a meander if each value of dir occurs length(S)/m times.
Let T(m,n,k) = number of meanders (m, S, dir) in which S contains m(k+1) L's and m(n-k) R's, so that length(S) = m(n+1).
For this sequence, m = 5, T(n,k) = T(5,n,k).
The values in the triangle were proved by brute force for 0 <= n <= 6. The formulas have not yet been proved in general.
The conjectured formulas are confirmed by dynamic programming for 0 <= n <= 29. - Susanne Wienand, Jul 01 2015
|
|
|
LINKS
|
|
|
|
FORMULA
|
Recursive formula (conjectured):
T(n,k) = T(5,n,k) = T(1,n,k)^5 + T(1,n,k)*T(4,n,n-1-k), 0 <= k < n
T(5,n,n) = 1 k = n
T(4,n,k) = T(1,n,k)^4 + T(1,n,k) * T(3,n,n-1-k), 0 <= k < n
T(4,n,n) = 1 k = n
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,n) = 1, k = n
T(n,k) = A + B + C + D + E, k < n
A = (C(n,k))^5
B = (C(n,k))^4 * C(n,n-1-k)
C = (C(n,k))^3 *(C(n,n-1-k))^2
D = (C(n,k))^2 *(C(n,n-1-k))^3
E = C(n,k) *(C(n,n-1-k))^4 [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,4). [Peter Luschny, Oct 20 2011]
T(n,k) = h(n,k)*binomial(n,k)^5, where h(n,k) = (1+k)*(1-((n-k)/(1+k))^5)/(1+2*k-n) if 1+2*k-n <> 0 else h(n,k) = 5. [Peter Luschny, Nov 24 2011]
|
|
|
EXAMPLE
|
For n = 5 and k = 2, T(n,k) = 500000
Example for recursive formula:
T(1,5,2) = 10
T(4,5,5-1-2) = T(4,5,2) = 40000
T(5,5,2) = 10^5 + 10*40000 = 500000
Example for closed formula:
T(5,2) = A + B + C + D + E
A = 10^5
B = 10^4 * 10
C = 10^3 * 10^2
D = 10^2 * 10^3
E = 10 * 10^4
T(5,2) = 5 * 10^5 = 500000
Some examples of list S and allocated values of dir if n = 5 and k = 2:
Length(S) = (5+1)*5 = 30 and S contains (2+1)*5 = 15 Ls.
S: L,L,L,L,L,L,L,L,L,L,L,L,L,L,L,R,R,R,R,R,R,R,R,R,R,R,R,R,R,R
dir: 1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,0,4,3,2,1,0,4,3,2,1,0,4,3,2,1
S: L,L,L,L,L,L,L,R,R,L,L,R,R,R,L,R,R,R,L,R,L,L,L,R,R,L,R,R,R,R
dir: 1,2,3,4,0,1,2,2,1,1,2,2,1,0,0,0,4,3,3,3,3,4,0,0,4,4,4,3,2,1
S: L,L,L,L,L,R,L,L,L,L,L,R,L,R,R,R,R,R,R,R,R,R,R,L,L,L,L,R,R,R
dir: 1,2,3,4,0,0,0,1,2,3,4,4,4,4,3,2,1,0,4,3,2,1,0,0,1,2,3,3,2,1
Each value of dir occurs 30/5 = 6 times.
The triangle begins:
1,
5, 1,
31, 62, 1,
121, 1215, 363, 1,
341, 13504, 20256, 1364, 1,
781, 96875, 500000, 193750, 3905, 1,
...
|
|
|
MAPLE
|
A197654 := (n, k)->(k^4+2*k^3*(1-n)+2*k^2*(2+n+2*n^2)+k*(3+n-n^2-3*n^3)+ n^4+n^3+n^2+n+1)*binomial(n, k)^5/(1+k)^4;
|
|
|
MATHEMATICA
|
T[n_, k_] := (k^4 + 2*k^3*(1-n) + 2*k^2*(2+n+2*n^2) + k*(3+n-n^2-3*n^3) + n^4+n^3+n^2+n+1)*Binomial[n, k]^5/(1+k)^4; Table[T[n, k], {n, 0, 7}, {k, 0, n}] // Flatten (* Jean-François Alcover, Feb 20 2017, after Peter Luschny *)
|
|
|
PROG
|
(C#) static int[] A197654_row(int r) { return GenBinomial(r, 5); } // The function GenBinomial(r, s) is defined in A194595.
// This C#-program causes numerical overflow for results larger than 2147483647. - Susanne Wienand, Jul 01 2015
(Sage)
def S(N, n, k) : return binomial(n, k)^(N+1)*sum(sum((-1)^(N-j+i)*binomial(N-i, j)*((n+1)/(k+1))^j for i in (0..N) for j in (0..N)))
def A197654(n, k) : return S(4, n, k)
for n in (0..5) : print([A197654(n, k) for k in (0..n)]) # Peter Luschny, Oct 24 2011
(PARI) A197654(n, k) = {if(n ==1+2*k, 5, (1+k)*(1-((n-k)/(1+k))^5)/(1+2*k-n))*binomial(n, k)^5} \\ Peter Luschny, Nov 24 2011
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
