何度もすまぬ。些細な表記missしてました。

>>130がPCより
(1)はそれでOK
さっきの自分流の解法なら
X=0　 Y=0〜n　y2n+1個
X=1　 Y=0〜n-1 2n-1　

X=n-1 Y=0〜1　 3
X=n　 Y=0　　　1
X,Yは=0の時は1通りに注意して
2n+1+2(2n-1)+2(2n-3)+…+2*1
=2^n+2n+1

Yの個数ではなくyの個数ですよねｗ