Lozanić's triangle

Lozanić’s triangle (also referred to as Losanitsch’s triangle) is a number triangle similar to Pascal’s triangle (cf. A007318) where three terms out of four are the sum of the two numbers immediately above it, the one out of four exceptions being that (numbering the rows by

n = 0, 1, 2, ...

and the entries in each row by

k = 0, 1, 2, ...

) if

n

is even and

k

is odd we subtract the binomial coefficient

(  (n / 2)  −  1(k  −  1) / 2  )

. The difference between Pascal’s triangle and the Losanitsch’s triangle gives the triangle shown in A034852 (or A034877 if we omit the border zeros).

It is named after the Serbian chemist Sima Lozanić (Germanized as Losanitsch), who researched it in his investigation into the symmetries exhibited by rows of paraffins, but has since been found to have applications in graph theory and combinatorics.

The entries for

n

even and

k

odd (one out of four) are one half of the corresponding entries of Pascal’s triangle (cf. A091043, A091044) They are highlighted red in the triangle below.

Lozanić’s triangle

																												A005418 Row sums: ∑ n i  = 0  T  (n, i)  =  2 n  −  3 + ( − 1) n +1 2 C (2 ( ⌊  n / 2⌋ + 1), ⌊  n / 2⌋  −  1)
n = 0																1												1
1															1		1											2
2														1		1		1										3
3													1		2		2		1									6
4												1		2		4		2		1								10
5											1		3		6		6		3		1							20
6										1		3		9		10		9		3		1						36
7									1		4		12		19		19		12		4		1					72
8								1		4		16		28		38		28		16		4		1				136
9							1		5		20		44		66		66		44		20		5		1			272
10						1		5		25		60		110		126		110		60		25		5		1		528
11					1		6		30		85		170		236		236		170		85		30		6		1	1056
12				1		6		36		110		A005994: Alkane (or paraffin) numbers l (7, m) = T  (m + 4, 4) .																2080
13			1		7		42		A005993: Alkane (or paraffin) numbers l (6, m) = T  (m + 3, 3) .																			4160
14		1		7		A002620: Positive quarter-squares, positive square and oblong numbers T  (n, 2) = ⌊  n / 2⌋   ⌈ n / 2⌉ .																						8256
15	1		A008619: Each positive integer twice T  (m + 1, 1) = 1 4 [3 + ( − 1) m + 2 m] .*																									16512
16	A000012: The all 1’s sequence T  (n, 0) = 1 .																											32896

_______________

* With generating function

G{T (m +1, 1)}(x) = 1 (1  −  x) (1  −  x 2)

.

Recurrence equation

$T(0,0)=1,\,$

When

n

is even and

k

is odd, the recurrence equation is:

$T(n,k)=T(n-1,k-1)+T(n-1,k)-{\binom {{\frac {n}{2}}-1}{\frac {k-1}{2}}},\ ({(n+1)\mod 2})({k\mod 2})=1,\,$

otherwise, the default recurrence relation is the same as for Pascal’s triangle, i.e. the triangle cell is the sum of the two cells above:

$T(n,k)=T(n-1,k-1)+T(n-1,k),\ n>0,\ ({(n+1)\mod 2})({k\mod 2})=0,\,$

where

(  nk  )

is

n

choose

k

(binomial coefficient).

These two rules may be combined into the ‘single’ rule:

$T(0,0)=1,\,$

$T(n,k)=T(n-1,k-1)+T(n-1,k)-{\tfrac {1}{4}}(1+(-1)^{n})(1-(-1)^{k}){\binom {{\frac {n}{2}}-1}{\frac {k-1}{2}}},\ n>0.\,$

Explicit formula

$T(n,k)={1 \over 2}{\bigg [}{\binom {n}{k}}+{\binom {n\mod 2}{k\mod 2}}{\binom {\lfloor n/2\rfloor }{\lfloor k/2\rfloor }}{\bigg ]},\,$

where

(  00  )  = (  10  )  = (  11  )  = 1, (  01  )  = 0,

so now the extra term is added when

n

is not even and

k

is not odd, which is equivalent to the extra term being added by default and then subtracted when

n

is even and

k

is odd (thus cancelling it) corresponding to pattern in the recurrence equation.

Lozanić’s triangle rows

The triangle read by rows gives an infinite sequence of finite sequences:

{{1}, {1, 1}, {1, 1, 1}, {1, 2, 2, 1}, {1, 2, 4, 2, 1}, {1, 3, 6, 6, 3, 1}, {1, 3, 9, 10, 9, 3, 1}, {1, 4, 12, 19, 19, 12, 4, 1}, {1, 4, 16, 28, 38, 28, 16, 4, 1}, {1, 5, 20, 44, 66, 66, 44, 20, 5, 1}, ...}

whose concatenation give A034851:

{1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 4, 2, 1, 1, 3, 6, 6, 3, 1, 1, 3, 9, 10, 9, 3, 1, 1, 4, 12, 19, 19, 12, 4, 1, 1, 4, 16, 28, 38, 28, 16, 4, 1, 1, 5, 20, 44, 66, 66, 44, 20, 5, 1, ...}

Lozanić’s triangle row sums

The

n

th row sum may be computed with the following formula:

$\sum _{i=0}^{n}T(n,i)=2^{n-1}+2^{\lfloor {\frac {n+1}{2}}\rfloor -1}={1 \over 2}{\bigg [}2^{n}+2^{\lfloor {\frac {n+1}{2}}\rfloor }{\bigg ]},$

which give A005418:

{1, 2, 3, 6, 10, 20, 36, 72, 136, 272, 528, 1056, 2080, 4160, 8256, 16512, 32896, 65792, 131328, 262656, 524800, 1049600, ...}

which has recurrence equations:

$\sum _{i=0}^{n}T(n,i)=2\ {\sum _{i=0}^{n}T(n-1,i)},\,$ $\scriptstyle n\,$ odd,

$\sum _{i=0}^{n}T(n,i)={\sum _{i=0}^{n}T(n-1,i)}+2^{n-2},\,$ $\scriptstyle n\,$ even.

Lozanić’s triangle row alternating sums

The

n

th row alternating sum may be computed with the following formula:

$\sum _{i=0}^{n}(-1)^{n}\ T(n,i)=({(n+1)\mod 2}){\big \lceil }2^{\lfloor {\frac {n}{2}}-1\rfloor }{\big \rceil }={\big (}{\tfrac {1+(-1)^{n}}{2}}{\big )}{\big \lceil }2^{\lfloor {\frac {n}{2}}-1\rfloor }{\big \rceil },\,$

which give (not in OEIS, and not A077957 which does not repeat the first 1, 0 pair):

{1, 0, 1, 0, 2, 0, 4, 0, 8, 0, 16, 0, 32, 0, 64, 0, 128, 0, 256, 0, 512, 0, 1024, ...}

Lozanić’s triangle columns

The central column yields A032123:

{1, 1, 4, 10, 38, 126, 472, 1716, 6470, 24310, 92504, 352716, 1352540, 5200300, 20060016, ...}

whose

m

th entry (indexed from $\scriptstyle m\,=\,0\,$) giving $\scriptstyle T(2m,\,m)\,$ is obtained with the formulae:

$T(2m,m)={\binom {2m-1}{m-1}}+{\binom {m-1}{{\tfrac {m}{2}}-1}},\,$ $\scriptstyle m\,$ even,

$T(2m,m)={\binom {2m-1}{m-1}},\,$ $\scriptstyle m\,$ odd.

Either of the identical next-to-central columns yields A005654:

{1, 2, 6, 19, 66, 236, 868, 3235, 12190, 46252, 176484, 676270, 2600612, 10030008, ...}

whose

m

th entry (indexed from $\scriptstyle m\,=\,1\,$) giving $\scriptstyle T(2m-1,\,m-1)=T(2m-1,\,m+1)\,$ is obtained with the formula:

$T(2m-1,m-1)=T(2m-1,m+1)={\frac {1}{2}}{\bigg [}{\binom {2m-1}{m}}+{\binom {m-1}{\lfloor {\tfrac {m}{2}}\rfloor }}{\bigg ]}\,$

The central column entries interleaved with one of the next-to-central columns yields A034872:

{1, 1, 1, 2, 4, 6, 10, 19, 38, 66, 126, 236, 472, 868, 1716, 3235, 6470, 12190, 24310, ...}

Lozanić’s triangle diagonals

The diagonals of Lozanić's triangle give:

* $\scriptstyle k\,$ = 0 or $\scriptstyle n\,$ - 0:	the all 1's sequence	A000012:   {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...}
* $\scriptstyle k\,$ = 1 or $\scriptstyle n\,$ - 1:	each positive integer twice	A008619:   {1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, ...}
* $\scriptstyle k\,$ = 2 or $\scriptstyle n\,$ - 2:	the quarter-squares	A002620:   {1, 2, 4, 6, 9, 12, 16, 20, 25, 30, 36, 42, 49, 56, 64, 72, 81, 90, 100, 110, 121, ...}
* $\scriptstyle k\,$ = 3 or $\scriptstyle n\,$ - 3:	the alkane (or paraffin) numbers $l(6,n)\,$	A005993:   {1, 2, 6, 10, 19, 28, 44, 60, 85, 110, 146, 182, 231, 280, 344, 408, 489, 570, 670, ...}
* $\scriptstyle k\,$ = 4 or $\scriptstyle n\,$ - 4:	the alkane (or paraffin) numbers $l(7,n)\,$	A005994:   {1, 3, 9, 19, 38, 66, 110, 170, 255, 365, 511, 693, 924, 1204, 1548, 1956, 2445, ...}
* $\scriptstyle k\,$ = 5 or $\scriptstyle n\,$ - 5:	the alkane (or paraffin) numbers $l(8,n)\,$	A005995:   {1, 3, 12, 28, 66, 126, 236, 396, 651, 1001, 1512, 2184, 3108, 4284, 5832, 7752, ...}
* $\scriptstyle k\,$ = 6 or $\scriptstyle n\,$ - 6:	the alkane (or paraffin) numbers $l(9,n)\,$	A018210:   {1, 4, 16, 44, 110, 236, 472, 868, 1519, 2520, 4032, 6216, 9324, 13608, 19440, ...}
* $\scriptstyle k\,$ = 7 or $\scriptstyle n\,$ - 7:	the alkane (or paraffin) numbers $l(10,n)\,$	A018211:   {1, 4, 20, 60, 170, 396, 868, 1716, 3235, 5720, 9752, 15912, 25236, 38760, ...}
* $\scriptstyle k\,$ = 8 or $\scriptstyle n\,$ - 8:	the alkane (or paraffin) numbers $l(11,n)\,$	A018212:   {1, 5, 25, 85, 255, 651, 1519, 3235, 6470, 12190, 21942, 37854, 63090, 101850, ...}
* $\scriptstyle k\,$ = 9 or $\scriptstyle n\,$ - 9:	the alkane (or paraffin) numbers $l(12,n)\,$	A018213:   {1, 5, 30, 110, 365, 1001, 2520, 5720, 12190, 24310, 46252, 83980, 147070, 248710, ...}
* $\scriptstyle k\,$ = 10 or $\scriptstyle n\,$ - 10:	the alkane (or paraffin) numbers $l(13,n)\,$	A018214:   {1, 6, 36, 146, 511, 1512, 4032, 9752, 21942, 46252, 92504, 176484, 323554, 572264, ...}
* ...

Lozanić’s triangle diagonals (formulae)

The $\scriptstyle m\,$^th entry (indexed from $\scriptstyle m\,=\,0\,$) of the $\scriptstyle k\,$^th diagonal (indexed from $\scriptstyle k\,=\,0\,$) of Lozanić's triangle is given by:

* $\scriptstyle k\,$ = 0 or $\scriptstyle n\,$ - 0:	$T(m+0,0)=1\,$
* $\scriptstyle k\,$ = 1 or $\scriptstyle n\,$ - 1:	$T(m+1,1)={\tfrac {1}{4}}[3+(-1)^{m}+2m]\,$
* $\scriptstyle k\,$ = 2 or $\scriptstyle n\,$ - 2:	$T(m+2,2)={\tfrac {1}{8}}[7+(-1)^{m}+8m+2m^{2}]\,$
* $\scriptstyle k\,$ = 3 or $\scriptstyle n\,$ - 3:	$T(m+3,3)={\tfrac {1}{24}}[(2+m)(9+3(-1)^{m}+8m+2m^{2})]\,$
* $\scriptstyle k\,$ = 4 or $\scriptstyle n\,$ - 4:	$T(m+4,4)={\tfrac {1}{96}}[81+15(-1)^{m}+2(65+3(-1)^{m})m+76m^{2}+20m^{3}+2m^{4}]\,$
* $\scriptstyle k\,$ = 5 or $\scriptstyle n\,$ - 5:	$T(m+5,5)={\tfrac {1}{480}}[(8+6m+m^{2})(15(3+(-1)^{m})+46m+18m^{2}+2m^{3})]\,$
* $\scriptstyle k\,$ = 6 or $\scriptstyle n\,$ - 6:	$T(m\ +\ 6,6)={\tfrac {1}{2880}}[45(53+11(-1)^{m})+(4533+315(-1)^{m})m+(3563+45(-1)^{m})m^{2}+1500m^{3}+350m^{4}+42m^{5}+2m^{6})]\,$
* $\scriptstyle k\,$ = 7 or $\scriptstyle n\,$ - 7:	$T(m\ +\ 7,7)={\tfrac {1}{20160}}[(48+44m+12m^{2}+m^{3})(105(3+(-1)^{m})+352m+172m^{2}+32m^{3}+2m^{4})]\,$
* $\scriptstyle k\,$ = 8 or $\scriptstyle n\,$ - 8:	$T(m+8,8)=...\,$ (series representation of generating function gets ever more unwieldy)
* $\scriptstyle k\,$ = 9 or $\scriptstyle n\,$ - 9:	$T(m+9,9)=...\,$
* $\scriptstyle k\,$ = 10 or $\scriptstyle n\,$ - 10:	$T(m+10,10)=...\,$
* ...

Lozanić’s triangle diagonals (recurrence equations)

The entries of the 1^st ($\scriptstyle k\,=\,1\,$) diagonal are the partial sums of one out of two entries of the 0^th ($\scriptstyle k\,=\,0\,$) diagonal:

$T(n,1)=\sum _{i=0}^{n-1}{\tfrac {(1-(-1)^{i})}{2}}\ T(i,0)=\sum _{i=0}^{n-1}{\tfrac {(1-(-1)^{i})}{2}}\,$

The entries of the 2^nd ($\scriptstyle k\,=\,2\,$) diagonal are the product of successive entries of the 1^st ($\scriptstyle k\,=\,1\,$) diagonal:

$T(n,2)=T(n,1)\ T(n-1,1)\,$

The entries of the even-numbered ($\scriptstyle k\,=\,2j\,$) diagonals are the partial sums of the previous diagonals:

$T(n,2j)=\sum _{m=2j-1}^{n-1}T(m,2j-1),\ j\geq 1.\,$

Lozanić’s triangle diagonals (generating functions)

A generating function for the ($\scriptstyle 2j+1\,$)^th diagonal is:

$G_{T(n+(2j+1),2j+1)}(x)={{\sum _{i=0}^{\infty }{\binom {j+1}{2i}}x^{2i}} \over {(1-x)^{j+1}(1-x^{2})^{j+1}}}\,$

and for the ($\scriptstyle 2j+2\,$)^th diagonal is obtained by dividing that by $\scriptstyle 1-x\,$:

$G_{T(n+(2j+2),2j+2)}(x)={{G_{T(n,2j+1)}(x)} \over {1-x}}\,$

Examples:

The 1^st diagonal { 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, ... } and the 2^nd diagonal { 1, 2, 4, 6, 9, 12, 16, 20, 25, 30, ... } have generating functions:

$G_{T(n+1,1)}(x)={{1} \over {(1-x)(1-x^{2})}},\,$ $\ \ G_{T(n+2,2)}(x)={{1} \over {(1-x)^{2}(1-x^{2})}}.\,$

The 3^rd diagonal { 1, 2, 6, 10, 19, 28, 44, 60, ... } and the 4^th diagonal { 1, 3, 9, 19, 38, 66, 110, 170, ... } have generating functions:

$G_{T(n+3,3)}(x)={{(1+x^{2})} \over {(1-x)^{2}(1-x^{2})^{2}}},\,$ $\ \ G_{T(n+4,4)}(x)={{(1+x^{2})} \over {(1-x)^{3}(1-x^{2})^{2}}}.\,$

The 5^th diagonal { 1, 3, 12, 28, 66, 126, 236, ... } and the 6^th diagonal { 1, 4, 16, 44, 110, 236, 472, ... } have generating functions:

$G_{T(n+5,5)}(x)={{(1+3x^{2})} \over {(1-x)^{3}(1-x^{2})^{3}}},\,$ $\ \ G_{T(n+6,6)}(x)={{(1+3x^{2})} \over {(1-x)^{4}(1-x^{2})^{3}}}.\,$

The 7^th diagonal { 1, 4, 20, 60, 170, 396, 868, ... } and the 8^th diagonal { 1, 5, 25, 85, 255, 651, 1519, 3235, ... } have generating functions:

$G_{T(n+7,7)}(x)={{(1+6x^{2}+x^{4})} \over {(1-x)^{4}(1-x^{2})^{4}}},\,$ $\ \ G_{T(n+8,8)}(x)={{(1+6x^{2}+x^{4})} \over {(1-x)^{5}(1-x^{2})^{4}}}.\,$

Lozanić’s triangle half sloped diagonals and Fibonacci numbers

Entries $\scriptstyle T(n,k)\,$ of half sloped diagonals rising from the left have constant sum $\scriptstyle s\,=\,n+k\,$.

Adding the entries on half sloped diagonals, starting with the 1 on an even $\scriptstyle n\,$ row, gives:

A005207

{1, 2, 4, 9, 21, 51, 127, 322, 826, 2135, 5545, 14445, 37701, 98514, 257608, 673933, ...}

which is obtained by the formula:

$\sum _{n+k=s}^{}T(n,k)={1 \over 2}\sum _{n+k=s}^{}{\bigg [}{\binom {n}{k}}+{\binom {n\mod 2}{k\mod 2}}{\binom {\lfloor n/2\rfloor }{\lfloor k/2\rfloor }}{\bigg ]}={1 \over 2}\sum _{n+k=s}^{}{\bigg [}{\binom {n}{k}}+{\binom {\lfloor n/2\rfloor }{\lfloor k/2\rfloor }}{\bigg ]}={\frac {(F_{2n-1}+F_{n+1})}{2}},s\geq 0,\ s\ even.\,$

Adding the entries on half sloped diagonals, starting with the 1 on an odd $\scriptstyle n\,$ row, gives:

A051450

{1, 2, 5, 12, 30, 76, 195, 504, 1309, 3410, 8900, 23256, 60813, 159094, 416325, 1089648, ...}

which is obtained by the formula:

$\sum _{n+k=s}^{}T(n,k)={1 \over 2}\sum _{n+k=s}^{}{\bigg [}{\binom {n}{k}}+{\binom {n\mod 2}{k\mod 2}}{\binom {\lfloor n/2\rfloor }{\lfloor k/2\rfloor }}{\bigg ]}={1 \over 2}\sum _{n+k=s}^{}{\bigg [}{\binom {n}{k}}+({n\mod 2}){\binom {\lfloor n/2\rfloor }{\lfloor k/2\rfloor }}{\bigg ]}={\frac {(F_{2n}+F_{n})}{2}},s\geq 0,\ s\ odd,\,$

where $F_{i}\,$ is the $\scriptstyle i\,$^th Fibonacci number.

See also

• Classic Sequences (Losanitsch's Triangle)
• A153046 Multiplicative encoding of Losanitsch's triangle (A034851.)

References

• S. M. Losanitsch, Die Isomerie-Arten bei den Homologen der Paraffin-Reihe, Chem. Ber. 30 (1897), 1917-1926.