mathlibdocumentation

data.list.nat_antidiagonal

Antidiagonals in ℕ × ℕ as lists #

This file defines the antidiagonals of ℕ × ℕ as lists: the n-th antidiagonal is the list of pairs (i, j) such that i + j = n. This is useful for polynomial multiplication and more generally for sums going from 0 to n.

Notes #

Files data.multiset.nat_antidiagonal and data.finset.nat_antidiagonal successively turn the list definition we have here into multiset and finset.

The antidiagonal of a natural number n is the list of pairs (i, j) such that i + j = n.

Equations
@[simp]
theorem list.nat.mem_antidiagonal {n : } {x : × } :
x.fst + x.snd = n

A pair (i, j) is contained in the antidiagonal of n if and only if i + j = n.

@[simp]
theorem list.nat.length_antidiagonal (n : ) :
= n + 1

The length of the antidiagonal of n is n + 1.

@[simp]
theorem list.nat.antidiagonal_zero  :
= [(0, 0)]

The antidiagonal of 0 is the list [(0, 0)]

theorem list.nat.nodup_antidiagonal (n : ) :

The antidiagonal of n does not contain duplicate entries.

@[simp]
theorem list.nat.antidiagonal_succ {n : } :
list.nat.antidiagonal (n + 1) = (0, n + 1) ::