login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A141043 Number of sequences of length n whose terms are positive integers less than or equal to n in which the i-th term is greater than both the (i-2)nd and (i-3)rd terms. 0
1, 4, 9, 31, 88, 288, 889, 2884, 9211, 29976, 97296, 318371, 1042756, 3429604, 11298969, 37320679, 123473176 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,2
COMMENTS
Apparently a(n) = sum(k=0..n, C(k, n-k)*C(2*n-k, n) ). - Paul Barry, Dec 02 2008
REFERENCES
Romanian Informatics Olympiad, 2001
LINKS
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).
PROG
(C)
#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("%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: A042599 A206960 A145543 * A111160 A192876 A201689
KEYWORD
nonn,more
AUTHOR
Shravas Rao, Jul 30 2008
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 11:46 EDT 2024. Contains 371241 sequences. (Running on oeis4.)