A191681 a(n) = (9^n - 1)/2.

0, 4, 40, 364, 3280, 29524, 265720, 2391484, 21523360, 193710244, 1743392200, 15690529804, 141214768240, 1270932914164, 11438396227480, 102945566047324, 926510094425920, 8338590849833284, 75047317648499560, 675425858836496044

Offset: 0

Author

Adi Dani, Jun 11 2011

Keywords

• nonn
• easy

Comments

Number of compositions of odd numbers into n parts < 9.

These are also the junctions of the Collatz trajectories of 2^(2k-1)-1 and 2^2k-1. - David Rabahy, Nov 01 2017

a(n) gives the number of turns in the n-th iteration of the Peano curve given by plotting (A163528, A163529) or by (Siromoney 1982). - Jason V. Morgan, Oct 08 2021

Examples

			a(2)=40: there are 40 compositions of odd numbers into 2 parts < 9:
1:  (0,1),(1,0);
3:  (0,3),(3,0),(1,2),(2,1);
5:  (0,5),(5,0),(1,4),(4,1),(2,3),(3,2);
7:  (0,7),(7,0),(1,6),(6,1),(2,5),(5,2),(3,4),(4,3);
9:  (1,8),(8,1),(2,7),(7,2),(3,6),(6,3),(4,5),(5,4);
11: (3,8),(8,3),(4,7),(7,4),(5,6),(6,5);
13: (5,8),(8,5),(6,7),(7,6);
15: (7,8),(8,7).
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..200
• Adi Dani, Restricted compositions of natural numbers
• Rani Siromoney and K. G. Subramanian, Space-filling curves and infinite graphs, International Workshop on Graph Grammars and Their Application to Computer Science, 1982.
• Index entries for linear recurrences with constant coefficients, signature (10,-9).

Crossrefs

Cf. A002452, A096053, A125857, A138894, A198964.

Programs

Magma

[(9^n-1)/2: n in [0..30]]; // Vincenzo Librandi, Jun 16 2011

Mathematica

Table[(9^n - 1)/2, {n, 0, 19}]
LinearRecurrence[{10,-9},{0,4},30] (* Harvey P. Dale, Jun 19 2011 *)

PARI

a(n)=9^n\2 \\ Charles R Greathouse IV, Oct 16 2015

Formula

a(0)=0, a(1)=4, a(n) = 10*a(n-1) - 9*a(n-2). - Harvey P. Dale, Jun 19 2011

G.f.: 4*x / ((x-1)*(9*x-1)). - Colin Barker, May 16 2013

a(n) = 2 * A125857(n+1) = 4 * A002452(n). - Bernard Schott, Oct 29 2021

Extensions

Example corrected by L. Edson Jeffery, Feb 13 2015