A141043 - OEIS

%I #21 Apr 16 2014 05:39:02

%S 1,4,9,31,88,288,889,2884,9211,29976,97296,318371,1042756,3429604,

%T 11298969,37320679,123473176

%N 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.

%C Apparently a(n) = sum(k=0..n, C(k, n-k)*C(2*n-k, n) ). - _Paul Barry_, Dec 02 2008

%D Romanian Informatics Olympiad, 2001

%e 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).

%o (C)

%o #include <stdio.h>

%o #define MAX_N 1001

%o int N;

%o int DP[MAX_N][MAX_N], X[MAX_N][MAX_N];

%o int main() {

%o     int i, j;

%o     scanf("%d ", &N);

%o     for(i = 1; i <= N; i++) { DP[1][i] = i; DP[2][i] = i * i; }

%o     for(i = 3; i <= N; i++) {

%o         for(j = 1; j <= N; j++) {

%o             if(j - 2 >= 0) X[i][j] = X[i][j - 1] + DP[i - 2][j - 2];

%o             DP[i][j] = DP[i][j - 1] + DP[i - 1][j - 1]

%o                           + DP[i - 2][j - 1] + X[i][j];

%o         }

%o     }

%o     printf("%d ", DP[N][N]);

%o     return 0;

%o }

%K nonn,more

%O 1,2

%A _Shravas Rao_, Jul 30 2008