A068602 Number of functions f:{0,1,2,...,n} -> {0,1,2,...,n} that satisfy f(0)=0 and f(n)=0, with f nowhere concave upward.

1, 1, 3, 8, 23, 54, 137, 297, 659, 1355, 2765, 5332, 10315, 19040, 34917, 62302, 110129, 190065, 325844, 547683, 913936, 1502371, 2450281, 3945459, 6312470, 9986624, 15696792, 24445887, 37838409, 58085458, 88678438, 134386804, 202593273, 303451589, 452267587

Offset

0,3

Links

Table of n, a(n) for n=0..34.

Example

a(3)=8 since the following 4-tuples of function values (f(0),f(1),f(2),f(3)) and no others, have the required properties: (0,0,0,0), (0,1,1,0), (0,1,2,0), (0,2,1,0), (0,2,2,0), (0,2,3,0), (0,3,2,0) and (0,3,3,0).

Prog

(Pascal)
program concave1;
var n:integer;
function f(y0, x1, y1, n:integer): longint;
  var y, ymax:integer; ct:longint;
  begin
    if n=0 then begin f := 1; exit; end;
    if x1=n-1 then begin f := 1; exit; end;
    ct := 0;
    if x1=0 then ymax := n else ymax := 2*y1-y0;
    if ymax>n then ymax := n;
    for y := y1-(y1 div (n-x1)) to ymax do
      ct := ct+f(y1, x1+1, y, n);
      f := ct;
    end;
begin
  for n := 0 to 30 do
    write(f(0, 0, 0, n):10);
readln;
end.

Crossrefs

Sequence in context: A183922 A340493 A296286 * A255834 A027212 A027236

Adjacent sequences: A068599 A068600 A068601 * A068603 A068604 A068605

Keyword

nonn

Author

John W. Layman, Mar 28 2002

Extensions

More terms from Sean A. Irvine, Feb 27 2024

Status

approved