Contemporary Mathematics

Application of Logic to Combinatorial Sequences

and

Their Recurrence Relations

Eldar Fischer, Tomer Kotek, and Johann A. Makowsky

Part 1. Introduction and Synopsis

1. Sequences of integers and their combinatorial interpretations

2. Linear recurrences

3. Logical formalisms

4. Finiteness conditions

5. Logical interpretations of integer sequences

Part 2. Guiding Examples

6. The classical recurrence relations

7. Functions, permutations and partitions

8. Trees and forests

9. Graph properties

10. Latin squares

Part 3. C-Finite and Holonomic Sequences

11. C-Finite sequences

12. Holonomic sequences

Part 4. Modular Recurrence Relations

13. DU-index and Specker index

14. The rˆ ole of logic

15. Structures of bounded degree

16. Structures of unbounded degree

References

2010 Mathematics Subject Classification. 03-02, 03C98, 05-02, 05A15, 11B50 .

Partially supported by an ISF grant number 1101/06 and an ERC-2007-StG grant number

202405.

Partially supported by the Fein Foundation and the Graduate School of the Technion - Israel

Institute of Technology.

Partially supported by the Israel Science Foundation for the project “Model Theoretic Inter-

pretations of Counting Functions” (2007-2010) and the Grant for Promotion of Research by the

Technion–Israel Institute of Technology.

2011 American Mathematical Society

1

Contemporary Mathematics

Volume 558, 2011

cc 2011 American Mathematical Society

1

Application of Logic to Combinatorial Sequences

and

Their Recurrence Relations

Eldar Fischer, Tomer Kotek, and Johann A. Makowsky

Part 1. Introduction and Synopsis

1. Sequences of integers and their combinatorial interpretations

2. Linear recurrences

3. Logical formalisms

4. Finiteness conditions

5. Logical interpretations of integer sequences

Part 2. Guiding Examples

6. The classical recurrence relations

7. Functions, permutations and partitions

8. Trees and forests

9. Graph properties

10. Latin squares

Part 3. C-Finite and Holonomic Sequences

11. C-Finite sequences

12. Holonomic sequences

Part 4. Modular Recurrence Relations

13. DU-index and Specker index

14. The rˆ ole of logic

15. Structures of bounded degree

16. Structures of unbounded degree

References

2010 Mathematics Subject Classification. 03-02, 03C98, 05-02, 05A15, 11B50 .

Partially supported by an ISF grant number 1101/06 and an ERC-2007-StG grant number

202405.

Partially supported by the Fein Foundation and the Graduate School of the Technion - Israel

Institute of Technology.

Partially supported by the Israel Science Foundation for the project “Model Theoretic Inter-

pretations of Counting Functions” (2007-2010) and the Grant for Promotion of Research by the

Technion–Israel Institute of Technology.

2011 American Mathematical Society

1

Contemporary Mathematics

Volume 558, 2011

cc 2011 American Mathematical Society

1