|
Search: id:A137398
|
|
|
| A137398 |
|
Let S be a strictly monotonic sequence of length 2n, and let p and q be subsequences of S each of length n such that the least element belongs to p and every element of S belongs to either p or q. The number of ways to select p such that for any index i the exchange of p(i) and q(i) makes at least one of p and q non-monotonic, is given by a(n). |
|
+0
1
|
|
| 0, 1, 2, 7, 22, 74, 252, 875, 3078, 10950, 39316, 142278, 518364, 1899668, 69997688, 25894579, 96211398, 1342323364
(list; graph; listen)
|
|
|
OFFSET
|
0,3
|
|
|
COMMENT
|
The sequence occurs as the diagonal of the triangle below.
0
0 1
0 1 2
0 1 3 7
0 1 4 11 22
0 1 5 16 38 74
0 1 6 22 60 134 252
0 1 7 29 89 223 475 875
The triangle is generated by:
b(n,0)=0
b(n,1)=1
b(n,k)=2b(k-2,k-2)+\sum_{i=k-1}^n b(i,k-1) for 2<=k<=n
or alternatively, for 2<=k<n either b(n,k)=b(n,k-1)+b(n-1,k) or b(n,k)= \sum_{i=1}^k b(n-1,i) and b(n,n)=b(n-1,n-1)+2b(n-2,n-2)+b(n,n-1)
|
|
REFERENCES
|
AUTHORS: G. Beavers (gordonb(AT)uark.edu), G. Starling (starling(AT)uark.edu), W. Li (wingning(AT)uark.edu)
|
|
FORMULA
|
a(1)=0, a(2)=1, a(3)=2, a(n)=2a(n-1)+2a(n-2)+\sum_{i=1}^{n-3}(c(i)a(n-i-1)) where c(i) is the ith Catalan number
G.f.: A(x)= 2x^2 / (1 -2x -4x^2 + Sqrt[1-4x])
|
|
EXAMPLE
|
a(6)=74=2a(5)+2a(4)+c(1)a(4)+c(2)a(3)+c(3)a(2)=2(22)+2(7)+1(7)+2(2)+5(1)=44+14+7+4+5
|
|
CROSSREFS
|
Sequence in context: A030186 A116387 A114495 this_sequence A007141 A090831 A119975
Adjacent sequences: A137395 A137396 A137397 this_sequence A137399 A137400 A137401
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Gordon Beavers (gordonb(AT)uark.edu), Apr 11 2008, May 15 2008
|
|
|
Search completed in 0.002 seconds
|
