combinatorics.catalan | Mathlib porting status

Changes since the initial port

The following section lists changes to this file in mathlib3 and mathlib4 that occured after the initial port. Most recent changes are shown first. Hovering over a commit will show all commits associated with the same mathlib3 commit.

Changes in mathlib3

26b40791

(last sync)

Changes in mathlib3port

mathlib3

mathlib3port

10bf4f82

bump to nightly-2023-11-01-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

13aa39b0

Diff

@@ -199,8 +199,8 @@ def treesOfNumNodesEq : ℕ → Finset (Tree Unit)
   | 0 => {nil}
   | n + 1 =>
     (Finset.Nat.antidiagonal n).attach.biUnion fun ijh =>
-      have := Nat.lt_succ_of_le (fst_le ijh.2)
-      have := Nat.lt_succ_of_le (snd_le ijh.2)
+      have := Nat.lt_succ_of_le (Finset.antidiagonal.fst_le ijh.2)
+      have := Nat.lt_succ_of_le (Finset.antidiagonal.snd_le ijh.2)
       pairwiseNode (trees_of_num_nodes_eq ijh.1.1) (trees_of_num_nodes_eq ijh.1.2)
 #align tree.trees_of_num_nodes_eq Tree.treesOfNumNodesEq
 -/

10bf4f82

bump to nightly-2023-09-24-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451

5655435f

Diff

@@ -3,14 +3,14 @@ Copyright (c) 2022 Julian Kuelshammer. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Julian Kuelshammer
 -/
-import Mathbin.Algebra.BigOperators.Fin
-import Mathbin.Algebra.BigOperators.NatAntidiagonal
-import Mathbin.Algebra.CharZero.Lemmas
-import Mathbin.Data.Finset.NatAntidiagonal
-import Mathbin.Data.Nat.Choose.Central
-import Mathbin.Data.Tree
-import Mathbin.Tactic.FieldSimp
-import Mathbin.Tactic.LinearCombination
+import Algebra.BigOperators.Fin
+import Algebra.BigOperators.NatAntidiagonal
+import Algebra.CharZero.Lemmas
+import Data.Finset.NatAntidiagonal
+import Data.Nat.Choose.Central
+import Data.Tree
+import Tactic.FieldSimp
+import Tactic.LinearCombination
 
 #align_import combinatorics.catalan from "leanprover-community/mathlib"@"10bf4f825ad729c5653adc039dafa3622e7f93c9"

10bf4f82

bump to nightly-2023-07-20-09

mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345

9c56d0dd

Diff

@@ -2,11 +2,6 @@
 Copyright (c) 2022 Julian Kuelshammer. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Julian Kuelshammer
-
-! This file was ported from Lean 3 source module combinatorics.catalan
-! leanprover-community/mathlib commit 10bf4f825ad729c5653adc039dafa3622e7f93c9
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Algebra.BigOperators.Fin
 import Mathbin.Algebra.BigOperators.NatAntidiagonal
@@ -17,6 +12,8 @@ import Mathbin.Data.Tree
 import Mathbin.Tactic.FieldSimp
 import Mathbin.Tactic.LinearCombination
 
+#align_import combinatorics.catalan from "leanprover-community/mathlib"@"10bf4f825ad729c5653adc039dafa3622e7f93c9"
+
 /-!
 # Catalan numbers

10bf4f82

bump to nightly-2023-06-13-21

mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423

829520ac

Diff

@@ -214,12 +214,14 @@ theorem treesOfNumNodesEq_zero : treesOfNumNodesEq 0 = {nil} := by rw [trees_of_
 #align tree.trees_of_nodes_eq_zero Tree.treesOfNumNodesEq_zero
 -/
 
+#print Tree.treesOfNumNodesEq_succ /-
 theorem treesOfNumNodesEq_succ (n : ℕ) :
     treesOfNumNodesEq (n + 1) =
       (Nat.antidiagonal n).biUnion fun ij =>
         pairwiseNode (treesOfNumNodesEq ij.1) (treesOfNumNodesEq ij.2) :=
   by rw [trees_of_num_nodes_eq]; ext; simp
 #align tree.trees_of_nodes_eq_succ Tree.treesOfNumNodesEq_succ
+-/
 
 #print Tree.mem_treesOfNumNodesEq /-
 @[simp]

10bf4f82

bump to nightly-2023-06-10-07

mathlib commit https://github.com/leanprover-community/mathlib/commit/a3e83f0fa4391c8740f7d773a7a9b74e311ae2a3

3fdc57bc

Diff

@@ -155,7 +155,7 @@ theorem catalan_eq_centralBinom_div (n : ℕ) : catalan n = n.centralBinom / (n
         push_cast
         rw [Nat.cast_sub i.is_le]
         exact tsub_le_self
-    · trans ∑ i : Fin d.succ, gosper_catalan (d + 1) (i + 1) - gosper_catalan (d + 1) i
+    · trans ∑ i : Fin d.succ, (gosper_catalan (d + 1) (i + 1) - gosper_catalan (d + 1) i)
       · refine' sum_congr rfl fun i _ => _
         rw_mod_cast [gosper_trick i.is_le, mul_div]
       · rw [← sum_range fun i => gosper_catalan (d + 1) (i + 1) - gosper_catalan (d + 1) i,

10bf4f82

bump to nightly-2023-06-04-18

mathlib commit https://github.com/leanprover-community/mathlib/commit/5f25c089cb34db4db112556f23c50d12da81b297

3fb4268b

Diff

@@ -239,8 +239,7 @@ theorem mem_treesOfNumNodesEq_numNodes (x : Tree Unit) : x ∈ treesOfNumNodesEq
 
 #print Tree.coe_treesOfNumNodesEq /-
 @[simp, norm_cast]
-theorem coe_treesOfNumNodesEq (n : ℕ) :
-    ↑(treesOfNumNodesEq n) = { x : Tree Unit | x.numNodes = n } :=
+theorem coe_treesOfNumNodesEq (n : ℕ) : ↑(treesOfNumNodesEq n) = {x : Tree Unit | x.numNodes = n} :=
   Set.ext (by simp)
 #align tree.coe_trees_of_nodes_eq Tree.coe_treesOfNumNodesEq
 -/

10bf4f82

bump to nightly-2023-05-28-18

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

8d353152

Diff

@@ -54,7 +54,7 @@ https://math.stackexchange.com/questions/3304415/catalan-numbers-algebraic-proof
 -/
 
 
-open BigOperators
+open scoped BigOperators
 
 open Finset
 
@@ -184,7 +184,7 @@ theorem catalan_three : catalan 3 = 5 := by
 
 namespace Tree
 
-open Tree
+open scoped Tree
 
 /- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
 #print Tree.pairwiseNode /-

10bf4f82

bump to nightly-2023-05-28-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

ba5d8b97

Diff

@@ -214,12 +214,6 @@ theorem treesOfNumNodesEq_zero : treesOfNumNodesEq 0 = {nil} := by rw [trees_of_
 #align tree.trees_of_nodes_eq_zero Tree.treesOfNumNodesEq_zero
 -/
 
-/- warning: tree.trees_of_nodes_eq_succ -> Tree.treesOfNumNodesEq_succ is a dubious translation:
-lean 3 declaration is
-  forall (n : Nat), Eq.{1} (Finset.{0} (Tree.{0} Unit)) (Tree.treesOfNumNodesEq (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) n (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))))) (Finset.biUnion.{0, 0} (Prod.{0, 0} Nat Nat) (Tree.{0} Unit) (fun (a : Tree.{0} Unit) (b : Tree.{0} Unit) => Tree.decidableEq.{0} Unit (fun (a : Unit) (b : Unit) => PUnit.decidableEq.{1} a b) a b) (Finset.Nat.antidiagonal n) (fun (ij : Prod.{0, 0} Nat Nat) => Tree.pairwiseNode (Tree.treesOfNumNodesEq (Prod.fst.{0, 0} Nat Nat ij)) (Tree.treesOfNumNodesEq (Prod.snd.{0, 0} Nat Nat ij))))
-but is expected to have type
-  forall (n : Nat), Eq.{1} (Finset.{0} (Tree.{0} Unit)) (Tree.treesOfNumNodesEq (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) n (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)))) (Finset.biUnion.{0, 0} (Prod.{0, 0} Nat Nat) (Tree.{0} Unit) (fun (a : Tree.{0} Unit) (b : Tree.{0} Unit) => instDecidableEqTree.{0} Unit (fun (a : Unit) (b : Unit) => instDecidableEqPUnit.{1} a b) a b) (Finset.Nat.antidiagonal n) (fun (ij : Prod.{0, 0} Nat Nat) => Tree.pairwiseNode (Tree.treesOfNumNodesEq (Prod.fst.{0, 0} Nat Nat ij)) (Tree.treesOfNumNodesEq (Prod.snd.{0, 0} Nat Nat ij))))
-Case conversion may be inaccurate. Consider using '#align tree.trees_of_nodes_eq_succ Tree.treesOfNumNodesEq_succₓ'. -/
 theorem treesOfNumNodesEq_succ (n : ℕ) :
     treesOfNumNodesEq (n + 1) =
       (Nat.antidiagonal n).biUnion fun ij =>

10bf4f82

bump to nightly-2023-05-28-04

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

6797a637

Diff

@@ -224,10 +224,7 @@ theorem treesOfNumNodesEq_succ (n : ℕ) :
     treesOfNumNodesEq (n + 1) =
       (Nat.antidiagonal n).biUnion fun ij =>
         pairwiseNode (treesOfNumNodesEq ij.1) (treesOfNumNodesEq ij.2) :=
-  by
-  rw [trees_of_num_nodes_eq]
-  ext
-  simp
+  by rw [trees_of_num_nodes_eq]; ext; simp
 #align tree.trees_of_nodes_eq_succ Tree.treesOfNumNodesEq_succ
 
 #print Tree.mem_treesOfNumNodesEq /-

10bf4f82

bump to nightly-2023-05-28-03

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

6c6011cf

Diff

@@ -103,7 +103,6 @@ theorem catalan_one : catalan 1 = 1 := by simp [catalan_succ]
 definition using a telescoping sum argument. -/
 private def gosper_catalan (n j : ℕ) : ℚ :=
   Nat.centralBinom j * Nat.centralBinom (n - j) * (2 * j - n) / (2 * n * (n + 1))
-#align gosper_catalan gosper_catalan
 
 private theorem gosper_trick {n i : ℕ} (h : i ≤ n) :
     gosperCatalan (n + 1) (i + 1) - gosperCatalan (n + 1) i =
@@ -125,7 +124,6 @@ private theorem gosper_trick {n i : ℕ} (h : i ≤ n) :
   linear_combination
     (2 : ℚ) * (n - i).centralBinom * (i + 1 - (n - i)) * (n + 1) * (n + 2) * (n - i + 1) * h₁ -
       2 * i.central_binom * (n + 1) * (n + 2) * (i - (n - i) - 1) * (i + 1) * h₂
-#align gosper_trick gosper_trick
 
 private theorem gosper_catalan_sub_eq_central_binom_div (n : ℕ) :
     gosperCatalan (n + 1) (n + 1) - gosperCatalan (n + 1) 0 = Nat.centralBinom (n + 1) / (n + 2) :=
@@ -136,7 +134,6 @@ private theorem gosper_catalan_sub_eq_central_binom_div (n : ℕ) :
   simp only [gosper_catalan, Nat.sub_zero, Nat.centralBinom_zero, Nat.sub_self]
   field_simp
   ring
-#align gosper_catalan_sub_eq_central_binom_div gosper_catalan_sub_eq_central_binom_div
 
 #print catalan_eq_centralBinom_div /-
 theorem catalan_eq_centralBinom_div (n : ℕ) : catalan n = n.centralBinom / (n + 1) :=

10bf4f82

bump to nightly-2023-05-14-08

mathlib commit https://github.com/leanprover-community/mathlib/commit/e3fb84046afd187b710170887195d50bada934ee

d31da313

Diff

@@ -204,7 +204,7 @@ def pairwiseNode (a b : Finset (Tree Unit)) : Finset (Tree Unit) :=
 def treesOfNumNodesEq : ℕ → Finset (Tree Unit)
   | 0 => {nil}
   | n + 1 =>
-    (Finset.Nat.antidiagonal n).attach.bunionᵢ fun ijh =>
+    (Finset.Nat.antidiagonal n).attach.biUnion fun ijh =>
       have := Nat.lt_succ_of_le (fst_le ijh.2)
       have := Nat.lt_succ_of_le (snd_le ijh.2)
       pairwiseNode (trees_of_num_nodes_eq ijh.1.1) (trees_of_num_nodes_eq ijh.1.2)
@@ -219,13 +219,13 @@ theorem treesOfNumNodesEq_zero : treesOfNumNodesEq 0 = {nil} := by rw [trees_of_
 
 /- warning: tree.trees_of_nodes_eq_succ -> Tree.treesOfNumNodesEq_succ is a dubious translation:
 lean 3 declaration is
-  forall (n : Nat), Eq.{1} (Finset.{0} (Tree.{0} Unit)) (Tree.treesOfNumNodesEq (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) n (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))))) (Finset.bunionᵢ.{0, 0} (Prod.{0, 0} Nat Nat) (Tree.{0} Unit) (fun (a : Tree.{0} Unit) (b : Tree.{0} Unit) => Tree.decidableEq.{0} Unit (fun (a : Unit) (b : Unit) => PUnit.decidableEq.{1} a b) a b) (Finset.Nat.antidiagonal n) (fun (ij : Prod.{0, 0} Nat Nat) => Tree.pairwiseNode (Tree.treesOfNumNodesEq (Prod.fst.{0, 0} Nat Nat ij)) (Tree.treesOfNumNodesEq (Prod.snd.{0, 0} Nat Nat ij))))
+  forall (n : Nat), Eq.{1} (Finset.{0} (Tree.{0} Unit)) (Tree.treesOfNumNodesEq (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) n (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))))) (Finset.biUnion.{0, 0} (Prod.{0, 0} Nat Nat) (Tree.{0} Unit) (fun (a : Tree.{0} Unit) (b : Tree.{0} Unit) => Tree.decidableEq.{0} Unit (fun (a : Unit) (b : Unit) => PUnit.decidableEq.{1} a b) a b) (Finset.Nat.antidiagonal n) (fun (ij : Prod.{0, 0} Nat Nat) => Tree.pairwiseNode (Tree.treesOfNumNodesEq (Prod.fst.{0, 0} Nat Nat ij)) (Tree.treesOfNumNodesEq (Prod.snd.{0, 0} Nat Nat ij))))
 but is expected to have type
-  forall (n : Nat), Eq.{1} (Finset.{0} (Tree.{0} Unit)) (Tree.treesOfNumNodesEq (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) n (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)))) (Finset.bunionᵢ.{0, 0} (Prod.{0, 0} Nat Nat) (Tree.{0} Unit) (fun (a : Tree.{0} Unit) (b : Tree.{0} Unit) => instDecidableEqTree.{0} Unit (fun (a : Unit) (b : Unit) => instDecidableEqPUnit.{1} a b) a b) (Finset.Nat.antidiagonal n) (fun (ij : Prod.{0, 0} Nat Nat) => Tree.pairwiseNode (Tree.treesOfNumNodesEq (Prod.fst.{0, 0} Nat Nat ij)) (Tree.treesOfNumNodesEq (Prod.snd.{0, 0} Nat Nat ij))))
+  forall (n : Nat), Eq.{1} (Finset.{0} (Tree.{0} Unit)) (Tree.treesOfNumNodesEq (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) n (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)))) (Finset.biUnion.{0, 0} (Prod.{0, 0} Nat Nat) (Tree.{0} Unit) (fun (a : Tree.{0} Unit) (b : Tree.{0} Unit) => instDecidableEqTree.{0} Unit (fun (a : Unit) (b : Unit) => instDecidableEqPUnit.{1} a b) a b) (Finset.Nat.antidiagonal n) (fun (ij : Prod.{0, 0} Nat Nat) => Tree.pairwiseNode (Tree.treesOfNumNodesEq (Prod.fst.{0, 0} Nat Nat ij)) (Tree.treesOfNumNodesEq (Prod.snd.{0, 0} Nat Nat ij))))
 Case conversion may be inaccurate. Consider using '#align tree.trees_of_nodes_eq_succ Tree.treesOfNumNodesEq_succₓ'. -/
 theorem treesOfNumNodesEq_succ (n : ℕ) :
     treesOfNumNodesEq (n + 1) =
-      (Nat.antidiagonal n).bunionᵢ fun ij =>
+      (Nat.antidiagonal n).biUnion fun ij =>
         pairwiseNode (treesOfNumNodesEq ij.1) (treesOfNumNodesEq ij.2) :=
   by
   rw [trees_of_num_nodes_eq]

10bf4f82

bump to nightly-2023-03-17-14

mathlib commit https://github.com/leanprover-community/mathlib/commit/da3fc4a33ff6bc75f077f691dc94c217b8d41559

2bedb1b6

Diff

@@ -211,19 +211,19 @@ def treesOfNumNodesEq : ℕ → Finset (Tree Unit)
 #align tree.trees_of_num_nodes_eq Tree.treesOfNumNodesEq
 -/
 
-#print Tree.treesOfNodesEq_zero /-
+#print Tree.treesOfNumNodesEq_zero /-
 @[simp]
-theorem treesOfNodesEq_zero : treesOfNumNodesEq 0 = {nil} := by rw [trees_of_num_nodes_eq]
-#align tree.trees_of_nodes_eq_zero Tree.treesOfNodesEq_zero
+theorem treesOfNumNodesEq_zero : treesOfNumNodesEq 0 = {nil} := by rw [trees_of_num_nodes_eq]
+#align tree.trees_of_nodes_eq_zero Tree.treesOfNumNodesEq_zero
 -/
 
-/- warning: tree.trees_of_nodes_eq_succ -> Tree.treesOfNodesEq_succ is a dubious translation:
+/- warning: tree.trees_of_nodes_eq_succ -> Tree.treesOfNumNodesEq_succ is a dubious translation:
 lean 3 declaration is
   forall (n : Nat), Eq.{1} (Finset.{0} (Tree.{0} Unit)) (Tree.treesOfNumNodesEq (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) n (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))))) (Finset.bunionᵢ.{0, 0} (Prod.{0, 0} Nat Nat) (Tree.{0} Unit) (fun (a : Tree.{0} Unit) (b : Tree.{0} Unit) => Tree.decidableEq.{0} Unit (fun (a : Unit) (b : Unit) => PUnit.decidableEq.{1} a b) a b) (Finset.Nat.antidiagonal n) (fun (ij : Prod.{0, 0} Nat Nat) => Tree.pairwiseNode (Tree.treesOfNumNodesEq (Prod.fst.{0, 0} Nat Nat ij)) (Tree.treesOfNumNodesEq (Prod.snd.{0, 0} Nat Nat ij))))
 but is expected to have type
   forall (n : Nat), Eq.{1} (Finset.{0} (Tree.{0} Unit)) (Tree.treesOfNumNodesEq (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) n (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)))) (Finset.bunionᵢ.{0, 0} (Prod.{0, 0} Nat Nat) (Tree.{0} Unit) (fun (a : Tree.{0} Unit) (b : Tree.{0} Unit) => instDecidableEqTree.{0} Unit (fun (a : Unit) (b : Unit) => instDecidableEqPUnit.{1} a b) a b) (Finset.Nat.antidiagonal n) (fun (ij : Prod.{0, 0} Nat Nat) => Tree.pairwiseNode (Tree.treesOfNumNodesEq (Prod.fst.{0, 0} Nat Nat ij)) (Tree.treesOfNumNodesEq (Prod.snd.{0, 0} Nat Nat ij))))
-Case conversion may be inaccurate. Consider using '#align tree.trees_of_nodes_eq_succ Tree.treesOfNodesEq_succₓ'. -/
-theorem treesOfNodesEq_succ (n : ℕ) :
+Case conversion may be inaccurate. Consider using '#align tree.trees_of_nodes_eq_succ Tree.treesOfNumNodesEq_succₓ'. -/
+theorem treesOfNumNodesEq_succ (n : ℕ) :
     treesOfNumNodesEq (n + 1) =
       (Nat.antidiagonal n).bunionᵢ fun ij =>
         pairwiseNode (treesOfNumNodesEq ij.1) (treesOfNumNodesEq ij.2) :=
@@ -231,33 +231,34 @@ theorem treesOfNodesEq_succ (n : ℕ) :
   rw [trees_of_num_nodes_eq]
   ext
   simp
-#align tree.trees_of_nodes_eq_succ Tree.treesOfNodesEq_succ
+#align tree.trees_of_nodes_eq_succ Tree.treesOfNumNodesEq_succ
 
-#print Tree.mem_treesOfNodesEq /-
+#print Tree.mem_treesOfNumNodesEq /-
 @[simp]
-theorem mem_treesOfNodesEq {x : Tree Unit} {n : ℕ} : x ∈ treesOfNumNodesEq n ↔ x.numNodes = n :=
+theorem mem_treesOfNumNodesEq {x : Tree Unit} {n : ℕ} : x ∈ treesOfNumNodesEq n ↔ x.numNodes = n :=
   by
   induction x using Tree.unitRecOn generalizing n <;> cases n <;>
     simp [trees_of_nodes_eq_succ, Nat.succ_eq_add_one, *]
   trivial
-#align tree.mem_trees_of_nodes_eq Tree.mem_treesOfNodesEq
+#align tree.mem_trees_of_nodes_eq Tree.mem_treesOfNumNodesEq
 -/
 
-#print Tree.mem_trees_of_nodes_eq_numNodes /-
-theorem mem_trees_of_nodes_eq_numNodes (x : Tree Unit) : x ∈ treesOfNumNodesEq x.numNodes :=
-  mem_treesOfNodesEq.mpr rfl
-#align tree.mem_trees_of_nodes_eq_num_nodes Tree.mem_trees_of_nodes_eq_numNodes
+#print Tree.mem_treesOfNumNodesEq_numNodes /-
+theorem mem_treesOfNumNodesEq_numNodes (x : Tree Unit) : x ∈ treesOfNumNodesEq x.numNodes :=
+  mem_treesOfNumNodesEq.mpr rfl
+#align tree.mem_trees_of_nodes_eq_num_nodes Tree.mem_treesOfNumNodesEq_numNodes
 -/
 
-#print Tree.coe_treesOfNodesEq /-
+#print Tree.coe_treesOfNumNodesEq /-
 @[simp, norm_cast]
-theorem coe_treesOfNodesEq (n : ℕ) : ↑(treesOfNumNodesEq n) = { x : Tree Unit | x.numNodes = n } :=
+theorem coe_treesOfNumNodesEq (n : ℕ) :
+    ↑(treesOfNumNodesEq n) = { x : Tree Unit | x.numNodes = n } :=
   Set.ext (by simp)
-#align tree.coe_trees_of_nodes_eq Tree.coe_treesOfNodesEq
+#align tree.coe_trees_of_nodes_eq Tree.coe_treesOfNumNodesEq
 -/
 
-#print Tree.treesOfNodesEq_card_eq_catalan /-
-theorem treesOfNodesEq_card_eq_catalan (n : ℕ) : (treesOfNumNodesEq n).card = catalan n :=
+#print Tree.treesOfNumNodesEq_card_eq_catalan /-
+theorem treesOfNumNodesEq_card_eq_catalan (n : ℕ) : (treesOfNumNodesEq n).card = catalan n :=
   by
   induction' n using Nat.case_strong_induction_on with n ih
   · simp
@@ -269,7 +270,7 @@ theorem treesOfNodesEq_card_eq_catalan (n : ℕ) : (treesOfNumNodesEq n).card =
     rintro ⟨i, j⟩ _ ⟨i', j'⟩ _
     clear * -
     tidy
-#align tree.trees_of_nodes_eq_card_eq_catalan Tree.treesOfNodesEq_card_eq_catalan
+#align tree.trees_of_nodes_eq_card_eq_catalan Tree.treesOfNumNodesEq_card_eq_catalan
 -/
 
 end Tree

10bf4f82

bump to nightly-2023-03-16-03

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce7e9d53d4bbc38065db3b595cd5bd73c323bc1d

8ae28b0b

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Julian Kuelshammer
 
 ! This file was ported from Lean 3 source module combinatorics.catalan
-! leanprover-community/mathlib commit 26b40791e4a5772a4e53d0e28e4df092119dc7da
+! leanprover-community/mathlib commit 10bf4f825ad729c5653adc039dafa3622e7f93c9
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -20,6 +20,9 @@ import Mathbin.Tactic.LinearCombination
 /-!
 # Catalan numbers
 
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
 The Catalan numbers (http://oeis.org/A000108) are probably the most ubiquitous sequence of integers
 in mathematics. They enumerate several important objects like binary trees, Dyck paths, and
 triangulations of convex polygons.

26b40791

bump to nightly-2023-03-13-18

mathlib commit https://github.com/leanprover-community/mathlib/commit/2af0836443b4cfb5feda0df0051acdb398304931

66e1e587

Diff

@@ -57,6 +57,7 @@ open Finset
 
 open Finset.Nat.antidiagonal (fst_le snd_le)
 
+#print catalan /-
 /-- The recursive definition of the sequence of Catalan numbers:
 `catalan (n + 1) = ∑ i : fin n.succ, catalan i * catalan (n - i)` -/
 def catalan : ℕ → ℕ
@@ -67,24 +68,33 @@ def catalan : ℕ → ℕ
       have := Nat.lt_succ_iff.mpr (n.sub_le i)
       catalan i * catalan (n - i)
 #align catalan catalan
+-/
 
+#print catalan_zero /-
 @[simp]
 theorem catalan_zero : catalan 0 = 1 := by rw [catalan]
 #align catalan_zero catalan_zero
+-/
 
+#print catalan_succ /-
 theorem catalan_succ (n : ℕ) : catalan (n + 1) = ∑ i : Fin n.succ, catalan i * catalan (n - i) := by
   rw [catalan]
 #align catalan_succ catalan_succ
+-/
 
+#print catalan_succ' /-
 theorem catalan_succ' (n : ℕ) :
     catalan (n + 1) = ∑ ij in Nat.antidiagonal n, catalan ij.1 * catalan ij.2 := by
   rw [catalan_succ, nat.sum_antidiagonal_eq_sum_range_succ (fun x y => catalan x * catalan y) n,
     sum_range]
 #align catalan_succ' catalan_succ'
+-/
 
+#print catalan_one /-
 @[simp]
 theorem catalan_one : catalan 1 = 1 := by simp [catalan_succ]
 #align catalan_one catalan_one
+-/
 
 /-- A helper sequence that can be used to prove the equality of the recursive and the explicit
 definition using a telescoping sum argument. -/
@@ -125,6 +135,7 @@ private theorem gosper_catalan_sub_eq_central_binom_div (n : ℕ) :
   ring
 #align gosper_catalan_sub_eq_central_binom_div gosper_catalan_sub_eq_central_binom_div
 
+#print catalan_eq_centralBinom_div /-
 theorem catalan_eq_centralBinom_div (n : ℕ) : catalan n = n.centralBinom / (n + 1) :=
   by
   suffices (catalan n : ℚ) = Nat.centralBinom n / (n + 1)
@@ -151,31 +162,41 @@ theorem catalan_eq_centralBinom_div (n : ℕ) : catalan n = n.centralBinom / (n
           sum_range_sub, Nat.succ_eq_add_one]
         exact_mod_cast gosper_catalan_sub_eq_central_binom_div d
 #align catalan_eq_central_binom_div catalan_eq_centralBinom_div
+-/
 
+#print succ_mul_catalan_eq_centralBinom /-
 theorem succ_mul_catalan_eq_centralBinom (n : ℕ) : (n + 1) * catalan n = n.centralBinom :=
   (Nat.eq_mul_of_div_eq_right n.succ_dvd_centralBinom (catalan_eq_centralBinom_div n).symm).symm
 #align succ_mul_catalan_eq_central_binom succ_mul_catalan_eq_centralBinom
+-/
 
+#print catalan_two /-
 theorem catalan_two : catalan 2 = 2 := by
   norm_num [catalan_eq_centralBinom_div, Nat.centralBinom, Nat.choose]
 #align catalan_two catalan_two
+-/
 
+#print catalan_three /-
 theorem catalan_three : catalan 3 = 5 := by
   norm_num [catalan_eq_centralBinom_div, Nat.centralBinom, Nat.choose]
 #align catalan_three catalan_three
+-/
 
 namespace Tree
 
 open Tree
 
 /- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
+#print Tree.pairwiseNode /-
 /-- Given two finsets, find all trees that can be formed with
   left child in `a` and right child in `b` -/
 @[reducible]
 def pairwiseNode (a b : Finset (Tree Unit)) : Finset (Tree Unit) :=
   (a ×ˢ b).map ⟨fun x => x.1 △ x.2, fun ⟨x₁, x₂⟩ ⟨y₁, y₂⟩ => fun h => by simpa using h⟩
 #align tree.pairwise_node Tree.pairwiseNode
+-/
 
+#print Tree.treesOfNumNodesEq /-
 /-- A finset of all trees with `n` nodes. See `mem_trees_of_nodes_eq` -/
 def treesOfNumNodesEq : ℕ → Finset (Tree Unit)
   | 0 => {nil}
@@ -185,12 +206,21 @@ def treesOfNumNodesEq : ℕ → Finset (Tree Unit)
       have := Nat.lt_succ_of_le (snd_le ijh.2)
       pairwiseNode (trees_of_num_nodes_eq ijh.1.1) (trees_of_num_nodes_eq ijh.1.2)
 #align tree.trees_of_num_nodes_eq Tree.treesOfNumNodesEq
+-/
 
+#print Tree.treesOfNodesEq_zero /-
 @[simp]
-theorem trees_of_nodes_eq_zero : treesOfNumNodesEq 0 = {nil} := by rw [trees_of_num_nodes_eq]
-#align tree.trees_of_nodes_eq_zero Tree.trees_of_nodes_eq_zero
+theorem treesOfNodesEq_zero : treesOfNumNodesEq 0 = {nil} := by rw [trees_of_num_nodes_eq]
+#align tree.trees_of_nodes_eq_zero Tree.treesOfNodesEq_zero
+-/
 
-theorem trees_of_nodes_eq_succ (n : ℕ) :
+/- warning: tree.trees_of_nodes_eq_succ -> Tree.treesOfNodesEq_succ is a dubious translation:
+lean 3 declaration is
+  forall (n : Nat), Eq.{1} (Finset.{0} (Tree.{0} Unit)) (Tree.treesOfNumNodesEq (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) n (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))))) (Finset.bunionᵢ.{0, 0} (Prod.{0, 0} Nat Nat) (Tree.{0} Unit) (fun (a : Tree.{0} Unit) (b : Tree.{0} Unit) => Tree.decidableEq.{0} Unit (fun (a : Unit) (b : Unit) => PUnit.decidableEq.{1} a b) a b) (Finset.Nat.antidiagonal n) (fun (ij : Prod.{0, 0} Nat Nat) => Tree.pairwiseNode (Tree.treesOfNumNodesEq (Prod.fst.{0, 0} Nat Nat ij)) (Tree.treesOfNumNodesEq (Prod.snd.{0, 0} Nat Nat ij))))
+but is expected to have type
+  forall (n : Nat), Eq.{1} (Finset.{0} (Tree.{0} Unit)) (Tree.treesOfNumNodesEq (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) n (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)))) (Finset.bunionᵢ.{0, 0} (Prod.{0, 0} Nat Nat) (Tree.{0} Unit) (fun (a : Tree.{0} Unit) (b : Tree.{0} Unit) => instDecidableEqTree.{0} Unit (fun (a : Unit) (b : Unit) => instDecidableEqPUnit.{1} a b) a b) (Finset.Nat.antidiagonal n) (fun (ij : Prod.{0, 0} Nat Nat) => Tree.pairwiseNode (Tree.treesOfNumNodesEq (Prod.fst.{0, 0} Nat Nat ij)) (Tree.treesOfNumNodesEq (Prod.snd.{0, 0} Nat Nat ij))))
+Case conversion may be inaccurate. Consider using '#align tree.trees_of_nodes_eq_succ Tree.treesOfNodesEq_succₓ'. -/
+theorem treesOfNodesEq_succ (n : ℕ) :
     treesOfNumNodesEq (n + 1) =
       (Nat.antidiagonal n).bunionᵢ fun ij =>
         pairwiseNode (treesOfNumNodesEq ij.1) (treesOfNumNodesEq ij.2) :=
@@ -198,27 +228,33 @@ theorem trees_of_nodes_eq_succ (n : ℕ) :
   rw [trees_of_num_nodes_eq]
   ext
   simp
-#align tree.trees_of_nodes_eq_succ Tree.trees_of_nodes_eq_succ
+#align tree.trees_of_nodes_eq_succ Tree.treesOfNodesEq_succ
 
+#print Tree.mem_treesOfNodesEq /-
 @[simp]
-theorem mem_trees_of_nodes_eq {x : Tree Unit} {n : ℕ} : x ∈ treesOfNumNodesEq n ↔ x.numNodes = n :=
+theorem mem_treesOfNodesEq {x : Tree Unit} {n : ℕ} : x ∈ treesOfNumNodesEq n ↔ x.numNodes = n :=
   by
   induction x using Tree.unitRecOn generalizing n <;> cases n <;>
     simp [trees_of_nodes_eq_succ, Nat.succ_eq_add_one, *]
   trivial
-#align tree.mem_trees_of_nodes_eq Tree.mem_trees_of_nodes_eq
+#align tree.mem_trees_of_nodes_eq Tree.mem_treesOfNodesEq
+-/
 
+#print Tree.mem_trees_of_nodes_eq_numNodes /-
 theorem mem_trees_of_nodes_eq_numNodes (x : Tree Unit) : x ∈ treesOfNumNodesEq x.numNodes :=
-  mem_trees_of_nodes_eq.mpr rfl
+  mem_treesOfNodesEq.mpr rfl
 #align tree.mem_trees_of_nodes_eq_num_nodes Tree.mem_trees_of_nodes_eq_numNodes
+-/
 
+#print Tree.coe_treesOfNodesEq /-
 @[simp, norm_cast]
-theorem coe_trees_of_nodes_eq (n : ℕ) :
-    ↑(treesOfNumNodesEq n) = { x : Tree Unit | x.numNodes = n } :=
+theorem coe_treesOfNodesEq (n : ℕ) : ↑(treesOfNumNodesEq n) = { x : Tree Unit | x.numNodes = n } :=
   Set.ext (by simp)
-#align tree.coe_trees_of_nodes_eq Tree.coe_trees_of_nodes_eq
+#align tree.coe_trees_of_nodes_eq Tree.coe_treesOfNodesEq
+-/
 
-theorem trees_of_nodes_eq_card_eq_catalan (n : ℕ) : (treesOfNumNodesEq n).card = catalan n :=
+#print Tree.treesOfNodesEq_card_eq_catalan /-
+theorem treesOfNodesEq_card_eq_catalan (n : ℕ) : (treesOfNumNodesEq n).card = catalan n :=
   by
   induction' n using Nat.case_strong_induction_on with n ih
   · simp
@@ -230,7 +266,8 @@ theorem trees_of_nodes_eq_card_eq_catalan (n : ℕ) : (treesOfNumNodesEq n).card
     rintro ⟨i, j⟩ _ ⟨i', j'⟩ _
     clear * -
     tidy
-#align tree.trees_of_nodes_eq_card_eq_catalan Tree.trees_of_nodes_eq_card_eq_catalan
+#align tree.trees_of_nodes_eq_card_eq_catalan Tree.treesOfNodesEq_card_eq_catalan
+-/
 
 end Tree

26b40791

bump to nightly-2023-02-21-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc

1107b979

Changes in mathlib4

mathlib3

mathlib4

26b40791

chore: Rename mul-div cancellation lemmas (#11530)

Lemma names around cancellation of multiplication and division are a mess.

This PR renames a handful of them according to the following table (each big row contains the multiplicative statement, then the three rows contain the GroupWithZero lemma name, the Group lemma, the AddGroup lemma name).

4ea4a86a

Diff

@@ -91,8 +91,8 @@ private theorem gosper_trick {n i : ℕ} (h : i ≤ n) :
       Nat.centralBinom i / (i + 1) * Nat.centralBinom (n - i) / (n - i + 1) := by
   have l₁ : (i : ℚ) + 1 ≠ 0 := by norm_cast; exact i.succ_ne_zero
   have l₂ : (n : ℚ) - i + 1 ≠ 0 := by norm_cast; exact (n - i).succ_ne_zero
-  have h₁ := (mul_div_cancel_left (↑(Nat.centralBinom (i + 1))) l₁).symm
-  have h₂ := (mul_div_cancel_left (↑(Nat.centralBinom (n - i + 1))) l₂).symm
+  have h₁ := (mul_div_cancel_left₀ (↑(Nat.centralBinom (i + 1))) l₁).symm
+  have h₂ := (mul_div_cancel_left₀ (↑(Nat.centralBinom (n - i + 1))) l₂).symm
   have h₃ : ((i : ℚ) + 1) * (i + 1).centralBinom = 2 * (2 * i + 1) * i.centralBinom :=
     mod_cast Nat.succ_mul_centralBinom_succ i
   have h₄ :

26b40791

chore(Tactic/GCongr): move @[gcongr] tags around (#9393)

Add import Mathlib.Tactic.GCongr.Core to Algebra/Order/Ring/Lemmas.
Move most @[gcongr] tags next to the lemmas.

See Zulip thread

Co-authored-by: Jeremy Tan Jie Rui <reddeloostw@gmail.com>

cd4edcb7

Diff

@@ -11,6 +11,7 @@ import Mathlib.Data.Nat.Choose.Central
 import Mathlib.Data.Tree
 import Mathlib.Tactic.FieldSimp
 import Mathlib.Tactic.GCongr
+import Mathlib.Tactic.Positivity
 
 #align_import combinatorics.catalan from "leanprover-community/mathlib"@"26b40791e4a5772a4e53d0e28e4df092119dc7da"

26b40791

chore: move to v4.6.0-rc1, merging adaptations from bump/v4.6.0 (#10176)

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Joachim Breitner <mail@joachim-breitner.de>

490d2d48

Diff

@@ -172,10 +172,8 @@ def treesOfNumNodesEq : ℕ → Finset (Tree Unit)
       pairwiseNode (treesOfNumNodesEq ijh.1.1) (treesOfNumNodesEq ijh.1.2)
   -- Porting note: Add this to satisfy the linter.
   decreasing_by
-      simp_wf
-      have := fst_le ijh.2
-      have := snd_le ijh.2
-      omega
+    · simp_wf; have := fst_le ijh.2; omega
+    · simp_wf; have := snd_le ijh.2; omega
 #align tree.trees_of_num_nodes_eq Tree.treesOfNumNodesEq
 
 @[simp]

26b40791

chore: remove spurious imports of positivity (#9924)

Some of these are already transitively imported, others aren't used at all (but not handled by noshake in #9772).

Mostly I wanted to avoid needing all of algebra imported (but unused!) in FilteredColimitCommutesFiniteLimit; there are now some assert_not_exists to preserve this.

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

26c5ad69

Diff

@@ -10,6 +10,7 @@ import Mathlib.Data.Finset.NatAntidiagonal
 import Mathlib.Data.Nat.Choose.Central
 import Mathlib.Data.Tree
 import Mathlib.Tactic.FieldSimp
+import Mathlib.Tactic.GCongr
 
 #align_import combinatorics.catalan from "leanprover-community/mathlib"@"26b40791e4a5772a4e53d0e28e4df092119dc7da"

26b40791

chore: use omega in decreasing_by proofs (#9688)

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

30030d81

Diff

@@ -172,8 +172,9 @@ def treesOfNumNodesEq : ℕ → Finset (Tree Unit)
   -- Porting note: Add this to satisfy the linter.
   decreasing_by
       simp_wf
-      try exact Nat.lt_succ_of_le (fst_le ijh.2)
-      try exact Nat.lt_succ_of_le (snd_le ijh.2)
+      have := fst_le ijh.2
+      have := snd_le ijh.2
+      omega
 #align tree.trees_of_num_nodes_eq Tree.treesOfNumNodesEq
 
 @[simp]

26b40791

chore: space after ← (#8178)

Co-authored-by: Moritz Firsching <firsching@google.com>

5fb9beab

Diff

@@ -98,7 +98,8 @@ private theorem gosper_trick {n i : ℕ} (h : i ≤ n) :
       mod_cast Nat.succ_mul_centralBinom_succ (n - i)
   simp only [gosperCatalan]
   push_cast
-  rw [show n + 1 - i = n - i + 1 by rw [Nat.add_comm (n - i) 1, ←(Nat.add_sub_assoc h 1), add_comm]]
+  rw [show n + 1 - i = n - i + 1 by rw [Nat.add_comm (n - i) 1, ← (Nat.add_sub_assoc h 1),
+    add_comm]]
   rw [h₁, h₂, h₃, h₄]
   field_simp
   ring

26b40791

chore: replace exact_mod_cast tactic with mod_cast elaborator where possible (#8404)

We still have the exact_mod_cast tactic, used in a few places, which somehow (?) works a little bit harder to prevent the expected type influencing the elaboration of the term. I would like to get to the bottom of this, and it will be easier once the only usages of exact_mod_cast are the ones that don't work using the term elaborator by itself.

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

693fd795

Diff

@@ -91,11 +91,11 @@ private theorem gosper_trick {n i : ℕ} (h : i ≤ n) :
   have l₂ : (n : ℚ) - i + 1 ≠ 0 := by norm_cast; exact (n - i).succ_ne_zero
   have h₁ := (mul_div_cancel_left (↑(Nat.centralBinom (i + 1))) l₁).symm
   have h₂ := (mul_div_cancel_left (↑(Nat.centralBinom (n - i + 1))) l₂).symm
-  have h₃ : ((i : ℚ) + 1) * (i + 1).centralBinom = 2 * (2 * i + 1) * i.centralBinom := by
-    exact_mod_cast Nat.succ_mul_centralBinom_succ i
+  have h₃ : ((i : ℚ) + 1) * (i + 1).centralBinom = 2 * (2 * i + 1) * i.centralBinom :=
+    mod_cast Nat.succ_mul_centralBinom_succ i
   have h₄ :
     ((n : ℚ) - i + 1) * (n - i + 1).centralBinom = 2 * (2 * (n - i) + 1) * (n - i).centralBinom :=
-    by exact_mod_cast Nat.succ_mul_centralBinom_succ (n - i)
+      mod_cast Nat.succ_mul_centralBinom_succ (n - i)
   simp only [gosperCatalan]
   push_cast
   rw [show n + 1 - i = n - i + 1 by rw [Nat.add_comm (n - i) 1, ←(Nat.add_sub_assoc h 1), add_comm]]
@@ -115,7 +115,7 @@ private theorem gosper_catalan_sub_eq_central_binom_div (n : ℕ) : gosperCatala
 theorem catalan_eq_centralBinom_div (n : ℕ) : catalan n = n.centralBinom / (n + 1) := by
   suffices (catalan n : ℚ) = Nat.centralBinom n / (n + 1) by
     have h := Nat.succ_dvd_centralBinom n
-    exact_mod_cast this
+    exact mod_cast this
   induction' n using Nat.case_strong_induction_on with d hd
   · simp
   · simp_rw [catalan_succ, Nat.cast_sum, Nat.cast_mul]

26b40791

feat(Data.Finset.Antidiagonal): generalize Finset.Nat.antidiagonal (#7486)

We define a type class Finset.HasAntidiagonal A which contains a function antidiagonal : A → Finset (A × A) such that antidiagonal n is the Finset of all pairs adding to n, as witnessed by mem_antidiagonal.

When A is a canonically ordered add monoid with locally finite order this typeclass can be instantiated with Finset.antidiagonalOfLocallyFinite. This applies in particular when A is ℕ, more generally or σ →₀ ℕ, or even ι →₀ A under the additional assumption OrderedSub A that make it a canonically ordered add monoid. (In fact, we would just need an AddMonoid with a compatible order, finite Iic, such that if a + b = n, then a, b ≤ n, and any finiteness condition would be OK.)

For computational reasons it is better to manually provide instances for ℕ and σ →₀ ℕ, to avoid quadratic runtime performance. These instances are provided as Finset.Nat.instHasAntidiagonal and Finsupp.instHasAntidiagonal. This is why Finset.antidiagonalOfLocallyFinite is an abbrev and not an instance.

This definition does not exactly match with that of Multiset.antidiagonal defined in Mathlib.Data.Multiset.Antidiagonal, because of the multiplicities. Indeed, by counting multiplicities, Multiset α is equivalent to α →₀ ℕ, but Finset.antidiagonal and Multiset.antidiagonal will return different objects. For example, for s : Multiset ℕ := {0,0,0}, Multiset.antidiagonal s has 8 elements but Finset.antidiagonal s has only 4.

def s : Multiset ℕ := {0, 0, 0}
#eval (Finset.antidiagonal s).card -- 4
#eval Multiset.card (Multiset.antidiagonal s) -- 8

TODO

Define HasMulAntidiagonal (for monoids). For PNat, we will recover the set of divisors of a strictly positive integer.

This closes #7917

Co-authored by: María Inés de Frutos-Fernández <mariaines.dff@gmail.com> and Eric Wieser <efw27@cam.ac.uk>

Co-authored-by: Antoine Chambert-Loir <antoine.chambert-loir@math.univ-paris-diderot.fr> Co-authored-by: Mario Carneiro <di.gama@gmail.com> Co-authored-by: Eric Wieser <wieser.eric@gmail.com>

85a1f28f

Diff

@@ -50,7 +50,7 @@ open BigOperators
 
 open Finset
 
-open Finset.Nat.antidiagonal (fst_le snd_le)
+open Finset.antidiagonal (fst_le snd_le)
 
 /-- The recursive definition of the sequence of Catalan numbers:
 `catalan (n + 1) = ∑ i : Fin n.succ, catalan i * catalan (n - i)` -/
@@ -70,7 +70,7 @@ theorem catalan_succ (n : ℕ) : catalan (n + 1) = ∑ i : Fin n.succ, catalan i
 #align catalan_succ catalan_succ
 
 theorem catalan_succ' (n : ℕ) :
-    catalan (n + 1) = ∑ ij in Nat.antidiagonal n, catalan ij.1 * catalan ij.2 := by
+    catalan (n + 1) = ∑ ij in antidiagonal n, catalan ij.1 * catalan ij.2 := by
   rw [catalan_succ, Nat.sum_antidiagonal_eq_sum_range_succ (fun x y => catalan x * catalan y) n,
     sum_range]
 #align catalan_succ' catalan_succ'
@@ -163,7 +163,7 @@ def pairwiseNode (a b : Finset (Tree Unit)) : Finset (Tree Unit) :=
 def treesOfNumNodesEq : ℕ → Finset (Tree Unit)
   | 0 => {nil}
   | n + 1 =>
-    (Finset.Nat.antidiagonal n).attach.biUnion fun ijh =>
+    (antidiagonal n).attach.biUnion fun ijh =>
       -- Porting note: `unusedHavesSuffices` linter is not happy with this. Commented out.
       -- have := Nat.lt_succ_of_le (fst_le ijh.2)
       -- have := Nat.lt_succ_of_le (snd_le ijh.2)
@@ -181,7 +181,7 @@ theorem treesOfNumNodesEq_zero : treesOfNumNodesEq 0 = {nil} := by rw [treesOfNu
 
 theorem treesOfNumNodesEq_succ (n : ℕ) :
     treesOfNumNodesEq (n + 1) =
-      (Nat.antidiagonal n).biUnion fun ij =>
+      (antidiagonal n).biUnion fun ij =>
         pairwiseNode (treesOfNumNodesEq ij.1) (treesOfNumNodesEq ij.2) := by
   rw [treesOfNumNodesEq]
   ext

26b40791

chore: remove trailing space in backticks (#7617)

This will improve spaces in the mathlib4 docs.

9106dcf8

Diff

@@ -27,7 +27,7 @@ triangulations of convex polygons.
 
 ## Main results
 
-* `catalan_eq_centralBinom_div `: The explicit formula for the Catalan number using the central
+* `catalan_eq_centralBinom_div`: The explicit formula for the Catalan number using the central
   binomial coefficient, `catalan n = Nat.centralBinom n / (n + 1)`.
 
 * `treesOfNodesEq_card_eq_catalan`: The number of binary trees with `n` internal nodes

26b40791

feat: fix norm num with arguments (#6600)

norm_num was passing the wrong syntax node to elabSimpArgs when elaborating, which essentially had the effect of ignoring all arguments it was passed, i.e. norm_num [add_comm] would not try to commute addition in the simp step. The fix itself is very simple (though not obvious to debug!), probably using TSyntax more would help avoid such issues in future.

Due to this bug many norm_num [blah] became rw [blah]; norm_num or similar, sometimes with porting notes, sometimes not, we fix these porting notes and other regressions during the port also.

Interestingly cancel_denoms uses norm_num [<- mul_assoc] internally, so cancel_denoms also got stronger with this change.

49a849ef

Diff

@@ -140,10 +140,12 @@ theorem succ_mul_catalan_eq_centralBinom (n : ℕ) : (n + 1) * catalan n = n.cen
   (Nat.eq_mul_of_div_eq_right n.succ_dvd_centralBinom (catalan_eq_centralBinom_div n).symm).symm
 #align succ_mul_catalan_eq_central_binom succ_mul_catalan_eq_centralBinom
 
-theorem catalan_two : catalan 2 = 2 := by unfold catalan; rfl
+theorem catalan_two : catalan 2 = 2 := by
+  norm_num [catalan_eq_centralBinom_div, Nat.centralBinom, Nat.choose]
 #align catalan_two catalan_two
 
-theorem catalan_three : catalan 3 = 5 := by unfold catalan; rfl
+theorem catalan_three : catalan 3 = 5 := by
+  norm_num [catalan_eq_centralBinom_div, Nat.centralBinom, Nat.choose]
 #align catalan_three catalan_three
 
 namespace Tree

26b40791

field_simp: Use positivity as a discharger (#6312)

The main reasons is that having h : 0 < denom in the context should suffice for field_simp to do its job, without the need to manually pass h.ne or similar.

Quite a few have := … ≠ 0 could be dropped, and some field_simp calls no longer need explicit arguments; this is promising.

This does break some proofs where field_simp was not used as a closing tactic, and it now shuffles terms around a bit different. These were fixed. Using field_simp in the middle of a proof seems rather fragile anyways.

As a drive-by contribution, positivity now knows about π > 0.

fixes: #4835

Co-authored-by: Matthew Ballard <matt@mrb.email>

6b391efa

Diff

@@ -87,12 +87,10 @@ private def gosperCatalan (n j : ℕ) : ℚ :=
 private theorem gosper_trick {n i : ℕ} (h : i ≤ n) :
     gosperCatalan (n + 1) (i + 1) - gosperCatalan (n + 1) i =
       Nat.centralBinom i / (i + 1) * Nat.centralBinom (n - i) / (n - i + 1) := by
-  have l₁ : (n : ℚ) + 1 ≠ 0 := by norm_cast; exact n.succ_ne_zero
-  have l₂ : (n : ℚ) + 1 + 1 ≠ 0 := by norm_cast; exact (n + 1).succ_ne_zero
-  have l₃ : (i : ℚ) + 1 ≠ 0 := by norm_cast; exact i.succ_ne_zero
-  have l₄ : (n : ℚ) - i + 1 ≠ 0 := by norm_cast; exact (n - i).succ_ne_zero
-  have h₁ := (mul_div_cancel_left (↑(Nat.centralBinom (i + 1))) l₃).symm
-  have h₂ := (mul_div_cancel_left (↑(Nat.centralBinom (n - i + 1))) l₄).symm
+  have l₁ : (i : ℚ) + 1 ≠ 0 := by norm_cast; exact i.succ_ne_zero
+  have l₂ : (n : ℚ) - i + 1 ≠ 0 := by norm_cast; exact (n - i).succ_ne_zero
+  have h₁ := (mul_div_cancel_left (↑(Nat.centralBinom (i + 1))) l₁).symm
+  have h₂ := (mul_div_cancel_left (↑(Nat.centralBinom (n - i + 1))) l₂).symm
   have h₃ : ((i : ℚ) + 1) * (i + 1).centralBinom = 2 * (2 * i + 1) * i.centralBinom := by
     exact_mod_cast Nat.succ_mul_centralBinom_succ i
   have h₄ :

26b40791

chore: script to replace headers with #align_import statements (#5979)

depends on: #5966

Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

89aa3a3b

Diff

@@ -2,11 +2,6 @@
 Copyright (c) 2022 Julian Kuelshammer. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Julian Kuelshammer
-
-! This file was ported from Lean 3 source module combinatorics.catalan
-! leanprover-community/mathlib commit 26b40791e4a5772a4e53d0e28e4df092119dc7da
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Algebra.BigOperators.Fin
 import Mathlib.Algebra.BigOperators.NatAntidiagonal
@@ -16,6 +11,8 @@ import Mathlib.Data.Nat.Choose.Central
 import Mathlib.Data.Tree
 import Mathlib.Tactic.FieldSimp
 
+#align_import combinatorics.catalan from "leanprover-community/mathlib"@"26b40791e4a5772a4e53d0e28e4df092119dc7da"
+
 /-!
 # Catalan numbers

26b40791

refactor: use the typeclass SProd to implement overloaded notation · ×ˢ · (#4200)

Currently, the following notations are changed from · ×ˢ · because Lean 4 can't deal with ambiguous notations. | Definition | Notation | | :

Co-authored-by: Jeremy Tan Jie Rui <reddeloostw@gmail.com> Co-authored-by: Kyle Miller <kmill31415@gmail.com> Co-authored-by: Chris Hughes <chrishughes24@gmail.com>

6c01dc6e

Diff

@@ -159,7 +159,7 @@ open Tree
   left child in `a` and right child in `b` -/
 @[reducible]
 def pairwiseNode (a b : Finset (Tree Unit)) : Finset (Tree Unit) :=
-  (a ×ᶠ b).map ⟨fun x => x.1 △ x.2, fun ⟨x₁, x₂⟩ ⟨y₁, y₂⟩ => fun h => by simpa using h⟩
+  (a ×ˢ b).map ⟨fun x => x.1 △ x.2, fun ⟨x₁, x₂⟩ ⟨y₁, y₂⟩ => fun h => by simpa using h⟩
 #align tree.pairwise_node Tree.pairwiseNode
 
 /-- A Finset of all trees with `n` nodes. See `mem_treesOfNodesEq` -/

26b40791

chore: Rename to sSup/iSup (#3938)

As discussed on Zulip

Renames

supₛ → sSup
infₛ → sInf
supᵢ → iSup
infᵢ → iInf
bsupₛ → bsSup
binfₛ → bsInf
bsupᵢ → biSup
binfᵢ → biInf
csupₛ → csSup
cinfₛ → csInf
csupᵢ → ciSup
cinfᵢ → ciInf
unionₛ → sUnion
interₛ → sInter
unionᵢ → iUnion
interᵢ → iInter
bunionₛ → bsUnion
binterₛ → bsInter
bunionᵢ → biUnion
binterᵢ → biInter

Co-authored-by: Parcly Taxel <reddeloostw@gmail.com>

d1eb6264

Diff

@@ -166,7 +166,7 @@ def pairwiseNode (a b : Finset (Tree Unit)) : Finset (Tree Unit) :=
 def treesOfNumNodesEq : ℕ → Finset (Tree Unit)
   | 0 => {nil}
   | n + 1 =>
-    (Finset.Nat.antidiagonal n).attach.bunionᵢ fun ijh =>
+    (Finset.Nat.antidiagonal n).attach.biUnion fun ijh =>
       -- Porting note: `unusedHavesSuffices` linter is not happy with this. Commented out.
       -- have := Nat.lt_succ_of_le (fst_le ijh.2)
       -- have := Nat.lt_succ_of_le (snd_le ijh.2)
@@ -184,7 +184,7 @@ theorem treesOfNumNodesEq_zero : treesOfNumNodesEq 0 = {nil} := by rw [treesOfNu
 
 theorem treesOfNumNodesEq_succ (n : ℕ) :
     treesOfNumNodesEq (n + 1) =
-      (Nat.antidiagonal n).bunionᵢ fun ij =>
+      (Nat.antidiagonal n).biUnion fun ij =>
         pairwiseNode (treesOfNumNodesEq ij.1) (treesOfNumNodesEq ij.2) := by
   rw [treesOfNumNodesEq]
   ext
@@ -212,7 +212,7 @@ theorem coe_treesOfNumNodesEq (n : ℕ) :
 theorem treesOfNumNodesEq_card_eq_catalan (n : ℕ) : (treesOfNumNodesEq n).card = catalan n := by
   induction' n using Nat.case_strong_induction_on with n ih
   · simp
-  rw [treesOfNumNodesEq_succ, card_bunionᵢ, catalan_succ']
+  rw [treesOfNumNodesEq_succ, card_biUnion, catalan_succ']
   · apply sum_congr rfl
     rintro ⟨i, j⟩ H
     rw [card_map, card_product, ih _ (fst_le H), ih _ (snd_le H)]

26b40791

chore: bye-bye, solo bys! (#3825)

This PR puts, with one exception, every single remaining by that lies all by itself on its own line to the previous line, thus matching the current behaviour of start-port.sh. The exception is when the by begins the second or later argument to a tuple or anonymous constructor; see https://github.com/leanprover-community/mathlib4/pull/3825#discussion_r1186702599.

Essentially this is s/\n *by$/ by/g, but with manual editing to satisfy the linter's max-100-char-line requirement. The Python style linter is also modified to catch these "isolated bys".

14167e48

Diff

@@ -108,9 +108,8 @@ private theorem gosper_trick {n i : ℕ} (h : i ≤ n) :
   field_simp
   ring
 
-private theorem gosper_catalan_sub_eq_central_binom_div (n : ℕ) :
-    gosperCatalan (n + 1) (n + 1) - gosperCatalan (n + 1) 0 = Nat.centralBinom (n + 1) / (n + 2) :=
-  by
+private theorem gosper_catalan_sub_eq_central_binom_div (n : ℕ) : gosperCatalan (n + 1) (n + 1) -
+    gosperCatalan (n + 1) 0 = Nat.centralBinom (n + 1) / (n + 2) := by
   have : (n : ℚ) + 1 ≠ 0 := by norm_cast; exact n.succ_ne_zero
   have : (n : ℚ) + 1 + 1 ≠ 0 := by norm_cast; exact (n + 1).succ_ne_zero
   have h : (n : ℚ) + 2 ≠ 0 := by norm_cast; exact (n + 1).succ_ne_zero
@@ -193,8 +192,8 @@ theorem treesOfNumNodesEq_succ (n : ℕ) :
 #align tree.trees_of_nodes_eq_succ Tree.treesOfNumNodesEq_succ
 
 @[simp]
-theorem mem_treesOfNumNodesEq {x : Tree Unit} {n : ℕ} : x ∈ treesOfNumNodesEq n ↔ x.numNodes = n :=
-  by
+theorem mem_treesOfNumNodesEq {x : Tree Unit} {n : ℕ} :
+    x ∈ treesOfNumNodesEq n ↔ x.numNodes = n := by
   induction x using Tree.unitRecOn generalizing n <;> cases n <;>
     simp [treesOfNumNodesEq_succ, Nat.succ_eq_add_one, *]
   exact (Nat.succ_ne_zero _).symm

26b40791

chore: bump to nightly-2023-04-11 (#3139)

1cd8b316

Diff

@@ -106,7 +106,7 @@ private theorem gosper_trick {n i : ℕ} (h : i ≤ n) :
   rw [show n + 1 - i = n - i + 1 by rw [Nat.add_comm (n - i) 1, ←(Nat.add_sub_assoc h 1), add_comm]]
   rw [h₁, h₂, h₃, h₄]
   field_simp
-  ring_nf
+  ring
 
 private theorem gosper_catalan_sub_eq_central_binom_div (n : ℕ) :
     gosperCatalan (n + 1) (n + 1) - gosperCatalan (n + 1) 0 = Nat.centralBinom (n + 1) / (n + 2) :=
@@ -116,7 +116,7 @@ private theorem gosper_catalan_sub_eq_central_binom_div (n : ℕ) :
   have h : (n : ℚ) + 2 ≠ 0 := by norm_cast; exact (n + 1).succ_ne_zero
   simp only [gosperCatalan, Nat.sub_zero, Nat.centralBinom_zero, Nat.sub_self]
   field_simp
-  ring_nf
+  ring
 
 theorem catalan_eq_centralBinom_div (n : ℕ) : catalan n = n.centralBinom / (n + 1) := by
   suffices (catalan n : ℚ) = Nat.centralBinom n / (n + 1) by

26b40791

chore: fix names in Combinatorics.Catalan (#2948)

These were already wrong in mathlib3.

2e567a95

Diff

@@ -180,40 +180,40 @@ def treesOfNumNodesEq : ℕ → Finset (Tree Unit)
 #align tree.trees_of_num_nodes_eq Tree.treesOfNumNodesEq
 
 @[simp]
-theorem treesOfNodesEq_zero : treesOfNumNodesEq 0 = {nil} := by rw [treesOfNumNodesEq]
-#align tree.trees_of_nodes_eq_zero Tree.treesOfNodesEq_zero
+theorem treesOfNumNodesEq_zero : treesOfNumNodesEq 0 = {nil} := by rw [treesOfNumNodesEq]
+#align tree.trees_of_nodes_eq_zero Tree.treesOfNumNodesEq_zero
 
-theorem treesOfNodesEq_succ (n : ℕ) :
+theorem treesOfNumNodesEq_succ (n : ℕ) :
     treesOfNumNodesEq (n + 1) =
       (Nat.antidiagonal n).bunionᵢ fun ij =>
         pairwiseNode (treesOfNumNodesEq ij.1) (treesOfNumNodesEq ij.2) := by
   rw [treesOfNumNodesEq]
   ext
   simp
-#align tree.trees_of_nodes_eq_succ Tree.treesOfNodesEq_succ
+#align tree.trees_of_nodes_eq_succ Tree.treesOfNumNodesEq_succ
 
 @[simp]
-theorem mem_treesOfNodesEq {x : Tree Unit} {n : ℕ} : x ∈ treesOfNumNodesEq n ↔ x.numNodes = n :=
+theorem mem_treesOfNumNodesEq {x : Tree Unit} {n : ℕ} : x ∈ treesOfNumNodesEq n ↔ x.numNodes = n :=
   by
   induction x using Tree.unitRecOn generalizing n <;> cases n <;>
-    simp [treesOfNodesEq_succ, Nat.succ_eq_add_one, *]
+    simp [treesOfNumNodesEq_succ, Nat.succ_eq_add_one, *]
   exact (Nat.succ_ne_zero _).symm
-#align tree.mem_trees_of_nodes_eq Tree.mem_treesOfNodesEq
+#align tree.mem_trees_of_nodes_eq Tree.mem_treesOfNumNodesEq
 
-theorem mem_trees_of_nodes_eq_numNodes (x : Tree Unit) : x ∈ treesOfNumNodesEq x.numNodes :=
-  mem_treesOfNodesEq.mpr rfl
-#align tree.mem_trees_of_nodes_eq_num_nodes Tree.mem_trees_of_nodes_eq_numNodes
+theorem mem_treesOfNumNodesEq_numNodes (x : Tree Unit) : x ∈ treesOfNumNodesEq x.numNodes :=
+  mem_treesOfNumNodesEq.mpr rfl
+#align tree.mem_trees_of_nodes_eq_num_nodes Tree.mem_treesOfNumNodesEq_numNodes
 
 @[simp, norm_cast]
-theorem coe_treesOfNodesEq (n : ℕ) :
+theorem coe_treesOfNumNodesEq (n : ℕ) :
     ↑(treesOfNumNodesEq n) = { x : Tree Unit | x.numNodes = n } :=
   Set.ext (by simp)
-#align tree.coe_trees_of_nodes_eq Tree.coe_treesOfNodesEq
+#align tree.coe_trees_of_nodes_eq Tree.coe_treesOfNumNodesEq
 
-theorem treesOfNodesEq_card_eq_catalan (n : ℕ) : (treesOfNumNodesEq n).card = catalan n := by
+theorem treesOfNumNodesEq_card_eq_catalan (n : ℕ) : (treesOfNumNodesEq n).card = catalan n := by
   induction' n using Nat.case_strong_induction_on with n ih
   · simp
-  rw [treesOfNodesEq_succ, card_bunionᵢ, catalan_succ']
+  rw [treesOfNumNodesEq_succ, card_bunionᵢ, catalan_succ']
   · apply sum_congr rfl
     rintro ⟨i, j⟩ H
     rw [card_map, card_product, ih _ (fst_le H), ih _ (snd_le H)]
@@ -228,6 +228,6 @@ theorem treesOfNodesEq_card_eq_catalan (n : ℕ) : (treesOfNumNodesEq n).card =
       trans (numNodes l, numNodes r)
       · simp at h1; simp [h1]
       · simp at h2; simp [h2]
-#align tree.trees_of_nodes_eq_card_eq_catalan Tree.treesOfNodesEq_card_eq_catalan
+#align tree.trees_of_nodes_eq_card_eq_catalan Tree.treesOfNumNodesEq_card_eq_catalan
 
 end Tree

26b40791

feat: Port Combinatorics.Catalan (#2588)

dec364a4

`combinatorics.catalan` ⟷ `Mathlib.Combinatorics.Catalan`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

TODO

Renames

Dependencies 7 + 247

combinatorics.catalan ⟷ Mathlib.Combinatorics.Catalan

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

TODO

Renames

Dependencies 7 + 247

`combinatorics.catalan` ⟷ `Mathlib.Combinatorics.Catalan`