|
Search: id:A141043
|
|
|
| A141043 |
|
Number of sequences of length n whose terms are positive integers less than or equal to n in which the ith term is greater than both the i-2th and i-3th terms. |
|
+0
1
|
|
| 1, 4, 9, 31, 88, 288, 889, 2884, 9211, 29976, 97296, 318371, 1042756, 3429604, 11298969, 37320679, 123473176
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
May coincide with a(n)=sum{k-0..n, C(k,n-k)C(2n-k,n)}. [From Paul Barry (pbarry(AT)wit.ie), Dec 02 2008]
|
|
REFERENCES
|
Romanian Informatics Olympiad, 2001
|
|
EXAMPLE
|
The valid sequences for n=3 are (1,1,2), (1,1,3), (1,2,2), (1,2,3), 1,3,2), (1,3,3), (2,1,3), (2,2,3), (2,3,3).
|
|
PROGRAM
|
#include <stdio.h> #define MAX_N 1001 int N; int DP[MAX_N][MAX_N], X[MAX_N][MAX_N]; int main() { int i, j; scanf(input, "%d ", &N); for(i=1; i<=N; i++) { DP[1][i] = i; DP[2][i] = i*i; } for(i=3; i<=N; i++) { for(j=1; j<=N; j++) { if(j-2 >= 0) X[i][j] = X[i][j-1]+DP[i-2][j-2]; DP[i][j] = DP[i][j-1]+DP[i-1][j-1]+DP[i-2][j-1]+X[i][j]; } } printf("%d ", DP[N][N]); return 0; }
|
|
CROSSREFS
|
Sequence in context: A041137 A042599 A145543 this_sequence A111160 A071378 A053192
Adjacent sequences: A141040 A141041 A141042 this_sequence A141044 A141045 A141046
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Shravas Rao (shravas(AT)gmail.com), Jul 30 2008
|
|
|
Search completed in 0.002 seconds
|
