Search

• Understanding why counting formulae are used for different problem types requires focus on the set of outcomes • Students can leverage lists of outcomes to relate counting processes to formulae. • Tasks that target the structure of a list of outcomes can help students relate counting processes and formulae. Research has shown that solving counting problems correctly can be difficult for students at all levels, and mathematics educators have sought to identify strategies and interventions to help students reason conceptually about combinatorial tasks. A set-oriented perspective (Lockwood, 2014) is a way of thinking about counting problems that emphasizes the importance of reasoning about the set of outcomes being counted. From a set-oriented perspective, one possible type of intervention is to have students focus on the sets of outcomes rather than formulas and expressions, and specifically to reason about the structure of the set of outcomes. Yet, reasoning about sets of outcomes is not sufficient for students to make connections between outcomes and counting processes. In this paper, we investigate tasks where students wrote computer code to enumerate the set of outcomes in a specific order by implementing listing processes, and they were then asked to determine a specific numbered outcome in their list by using the structure of their enumeration scheme. We clarify particular aspects of a set-oriented perspective that were productive for students, and we demonstrate that tasks that asked students to name a specific outcome in their list elicited meaningful connections between counting processes and sets of outcomes. Further, such tasks reinforce desirable mathematical practices such as leveraging structure and connecting representations. [ABSTRACT FROM AUTHOR]

Abstract: This paper is a note on “Complexity analysis of job-shop scheduling with deteriorating jobs” [G. Mosheiov, Complexity analysis of job-shop scheduling with deteriorating jobs, Discrete Applied Mathematics 117 (2002) 195–209]. A proportional deterioration rate is assumed and the objective is the minimization of the makespan. Mosheiov presents NP-hardness results for flow-shops and open-shops with three or more machines and for job-shops with two or more machines. The proof of NP-hardness for the flow-shop case is however not correct. This paper provides a correct proof. [ABSTRACT FROM AUTHOR]

Abstract: Combinatorial topics have become increasingly prevalent in K-12 and undergraduate curricula, yet research on combinatorics education indicates that students face difficulties when solving counting problems. The research community has not yet addressed students’ ways of thinking at a level that facilitates deeper understanding of how students conceptualize counting problems. To this end, a model of students’ combinatorial thinking was empirically and theoretically developed; it represents a conceptual analysis of students’ thinking related to counting and has been refined through analyzing students’ counting activity. In this paper, the model is presented, and relationships between formulas/expressions, counting processes, and sets of outcomes are elaborated. Additionally, the usefulness and potential explanatory power of the model are demonstrated through examining data both from a study the author conducted, and from existing literature on combinatorics education. [Copyright &y& Elsevier]

Abstract: A graph is dot-critical if contracting any edge decreases the domination number. It is totally dot-critical if identifying any two vertices decreases the domination number. Burton and Sumner [Discrete Math. 306 (2006) 11–18] posed the problem: Is it true that for , there exists a totally -dot-critical graph with no critical vertices? In this paper, we show that this problem has a positive answer. [Copyright &y& Elsevier]

Abstract: In [On Mills''s conjecture on matroids with many common bases, Discrete Math. 240 (2001) 271–276], Lemos proved a conjecture of Mills [On matroids with many common bases, Discrete Math. 203 (1999) 195–205]: for two -connected matroids whose symmetric difference between their collections of bases has size at most , there is a matroid that is obtained from one of these matroids by relaxing circuit-hyperplanes and from the other by relaxing circuit-hyperplanes, where and are non-negative integers such that . In [Matroids with many common bases, Discrete Math. 270 (2003) 193–205], Lemos proved a similar result, where the hypothesis of the matroids being -connected is replaced by the weaker hypothesis of being vertically -connected. In this paper, we extend these results. [Copyright &y& Elsevier]

• Equivalence is a fundamental idea within combinatorics (and mathematics more broadly). • We draw on Harel's duality principle and describe and demonstrate an equivalence way of thinking in combinatorics. • This equivalence way of thinking can be valuable for students in a variety of combinatorial situations. Counting problems offer opportunities for rich mathematical thinking, and yet there is evidence that students struggle to solve counting problems correctly. There is a need to identify useful approaches and thought processes that can help students be successful in their combinatorial activity. In this paper, we propose a characterization of an equivalence way of thinking, we discuss examples of how it arises mathematically in a variety of combinatorial concepts, and we offer episodes from a paired teaching experiment with undergraduate students that demonstrate useful ways in which students developed and leverage this way of thinking. Ultimately, we argue that this way of thinking can apply to a variety of combinatorial situations, and we make the case that it is a valuable way of thinking that should be prioritized for students learning combinatorics. [ABSTRACT FROM AUTHOR]