Compositions with parts 1, 2 and 3

TheoremCompositions with parts \(1\), \(2\), \(3\) are counted by Tribonacci numbers#✓fully proved

Let \(T\) be a sequence of natural numbers with \(T_1 = T_2 = 1\), \(T_3 = 2\) and \(T_m = T_{m-1} + T_{m-2} + T_{m-3}\) for every \(m > 3\). Then for every positive integer \(n\), the number of compositions of \(n\) (ordered sequences of positive integers with sum \(n\)) whose parts are all \(1\), \(2\) or \(3\) is \(T_{n+1}\).

The result is due to V. E. Hoggatt, Jr., and M. Bicknell, "Palindromic compositions," Fibonacci Quarterly 13 (1975), 350–356, cited as [V] at source lines 429–430.

Proof: Split each nonempty composition by its first part, sum the resulting recurrence over its length, and use strong induction, following Stanley, Section 1.2, and OEIS A000073.

public theorem compositions_parts_one_two_three_eq_tribonacci
    (n : ℕ) (hn : 0 < n)
    (T : ℕ → ℕ)
    (hT1 : T 1 = 1)
    (hT2 : T 2 = 1)
    (hT3 : T 3 = 2)
    (hTrec : ∀ m : ℕ, 3 < m →
      T m = T (m - 1) + T (m - 2) + T (m - 3)) :
    (∑ k ∈ Finset.range (n + 1),
      Fintype.card {a : Fin k → Fin 3 //
        (∑ i : Fin k, ((a i).val + 1)) = n}) =
      T (n + 1)

Sources

• Yu-hong Guo, "Some Identities For Palindromic Compositions," Journal of Integer Sequences 21 (2018), Article 18.6.6, Theorem citing [V], lines 118–125, https://cs.uwaterloo.ca/journals/JIS/VOL21/Guo/guo19.tex

Used by 1

Used byCompositions with parts \(1\), \(2\), \(3\) and the Tribonacci sequence

TheoremCompositions with parts \(1\), \(2\), \(3\) and the Tribonacci sequence#✓fully proved

For every positive integer \(n\), the number of compositions of \(n\) (ordered sequences of positive integers with sum \(n\)) whose parts are all \(1\), \(2\) or \(3\) equals \(t_{n+2}\), where \(t\) is the Tribonacci sequence given by \(t_0 = t_1 = 0\), \(t_2 = 1\) and \(t_{k+3} = t_{k+2} + t_{k+1} + t_k\) (OEIS A000073).

Proof: Specialize compositions_parts_one_two_three_eq_tribonacci to T k = tribonacci (k + 1), whose initial values and recurrence hold by definition.

public theorem compositions_parts_one_two_three_eq_canonical_tribonacci
    (n : ℕ) (hn : 0 < n) :
    (∑ k ∈ Finset.range (n + 1),
      Fintype.card {a : Fin k → Fin 3 //
        (∑ i : Fin k, ((a i).val + 1)) = n}) =
      tribonacci (n + 2)

Uses 2

Statement usesTribonacci sequence

Proof usesCompositions with parts \(1\), \(2\), \(3\) are counted by Tribonacci numbers

2 fully proved

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.