Combinatorics of Positional Colored Compositions

Basic Information

• Paper ID: 2511.08529
• Title: Combinatorics of positional colored compositions
• Authors: Andrew Li (Princeton University), Hua Wang (Georgia Southern University)
• Classification: math.CO (Combinatorics)
• Publication Date: November 11, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2511.08529
• Keywords: integer compositions, colored compositions, combinatorial proofs
• MSC Classification: 05A17, 11B37

Abstract

This paper investigates positional colored compositions, which are integer compositions where coloring is permitted only for parts at specific positions. The authors derive counting sequences via generating functions and discover profound connections between these sequences and various other combinatorial objects, providing bijective proofs and generalizations for these relationships.

Research Background and Motivation

Research Problem

The core problem addressed is: how to count integer compositions where only parts at specific positions are permitted n-coloring, and what relationships exist between such structures and other combinatorial objects.

Problem Significance

1. Theoretical Importance: Integer compositions are fundamental objects in combinatorics. Since n-colored compositions were introduced by Agarwal in 2000, they have been extensively studied. Positional colored compositions, as a new variant, enrich this research domain.
2. Connectivity: The research reveals that positional colored compositions are equivalent to compositions with restricted colors, (n choose 2)-colored compositions, ternary strings, binary strings, 321-avoiding separable permutations, and other combinatorial objects, uncovering deep connections between different combinatorial structures.
3. Methodological Value: Through generating functions and bijective proofs, the work provides new tools and perspectives for combinatorial counting.

Limitations of Existing Methods

• Existing research primarily focuses on compositions where all parts are colored or specific colors are restricted
• Systematic research on position-based coloring rules is lacking
• Equivalence relationships between different combinatorial objects have not been fully explored

Research Motivation

The authors discovered coincidences in certain counting sequences through OEIS (Online Encyclopedia of Integer Sequences), prompting exploration of intrinsic connections between positional colored compositions and other combinatorial structures, with combinatorial arguments providing deeper understanding.

Core Contributions

1. Introduction of Positional Colored Compositions: Defines (m,k)-n-colored compositions, where parts at positions k (mod m) are n-colored while others are uncolored.
2. Derivation of Generating Functions:
   • Generating function for EVEN-colored compositions (even positions colored)
   • Generating function for ODD-colored compositions (odd positions colored)
   • Generating function for general (m,k)-n-colored compositions
3. Establishment of Multiple Bijections:
   • EVEN-colored compositions ↔ n-colored compositions with restricted color 2
   • ODD-colored compositions ↔ (n choose 2)-colored compositions
   • EVEN-colored compositions ↔ specific ternary strings
   • EVEN-colored compositions ↔ products of 1-runs in binary strings
   • EVEN-colored compositions ↔ 321-avoiding separable permutations
4. Bijective Proofs of Combinatorial Identities: Proves identities such as e(k+1) = e(k) + o(k) and generalizes to general cases.
5. Discovery of New Combinatorial Equivalences: Reveals deep connections between seemingly unrelated combinatorial objects.

Detailed Methodology

Task Definition

Basic Concepts:

• Composition: An ordered sum of positive integers. For example, compositions of 3 are: 1+1+1, 1+2, 2+1, 3
• n-colored composition: Each part of size k in a composition can be assigned a color from 1 to k, denoted by subscript
• (m,k)-n-colored composition: Parts at positions k (mod m) are n-colored; other parts are uncolored

Special Cases:

• EVEN-colored composition: (2,0)-n-colored composition, i.e., even positions colored
• ODD-colored composition: (2,1)-n-colored composition, i.e., odd positions colored

Generating Function Method

Basic Building Blocks

1. Generating function for uncolored parts: $x + x^2 + x^3 + \cdots = \frac{x}{1-x}$
2. Generating function for n-colored parts: $x + 2x^2 + 3x^3 + \cdots = \frac{x}{(1-x)^2}$

This holds because a part of size k has k color choices.

EVEN-Colored Compositions

Two cases are considered:

1. Odd number of parts: At least one uncolored part, followed by any number of pairs (colored part + uncolored part) $\frac{x}{1-x} \sum_{i=0}^{\infty} \left(\frac{x^2}{(1-x)^3}\right)^i = \frac{x(1-x)^2}{(1-x)^3 - x^2}$
2. Even number of parts: Positive number of pairs (colored part + uncolored part) $\sum_{i=1}^{\infty} \left(\frac{x^2}{(1-x)^3}\right)^i = \frac{x^2}{(1-x)^3 - x^2}$

Total generating function: $F_e(x) = \frac{x^3 - x^2 + x}{-x^3 + 2x^2 - 3x + 1}$

This corresponds to OEIS sequence A034943.

ODD-Colored Compositions

Similar analysis yields the generating function: $F_o(x) = \frac{x}{-x^3 + 2x^2 - 3x + 1}$

This corresponds to OEIS sequence A095263.

General (m,k)-n-Colored Compositions

Analysis by part count modulo m yields three cases:

1. 0 (mod m): One colored part and m-1 uncolored parts per m parts
2. j (mod m), 1≤j≤k-1: j uncolored parts plus case 1
3. ℓ (mod m), k≤ℓ≤m-1: ℓ-1 uncolored parts + 1 colored part plus case 1

Bijection Construction Method

The core technical innovation lies in constructing multiple elegant bijections.

Bijection with Restricted Color 2 Compositions (Theorem 3.1)

Mapping Direction 1 (Restricted color 2 → EVEN-colored):

• Process each part from left to right
• For colored parts p_c at odd positions (c≥3), split as: (c-2) + (p-c+2)_2
• Remove color from parts with color 1 at odd positions

Inverse Mapping:

• For color 2 parts q_2 at even positions, merge with preceding part p to form (p+q)_{p+2}

Example: 3_3, 1_1, 6_4, 4_4 → 1, 2_2, 1, 6_4, 2, 2_2

Bijection with (n choose 2)-Colored Compositions (Theorem 3.2)

This is a bijection between ODD-colored compositions and (n choose 2)-colored compositions (each part has two distinct spots).

Mapping (ODD-colored → (n choose 2)-colored):

• Even number of parts: Merge each pair of adjacent tiles into one tile, preserving spot positions; extend final tile with a spotless unit
• Odd number of parts: First append a spotted unit at the end, then execute above operation

Inverse Mapping: Cut each tile before the second spot, delete the final unit.

Bijection with Ternary Strings (Theorem 3.3)

EVEN-colored compositions ↔ Ternary strings with restricted consecutive digits, not starting with 2, not ending with 0

Mapping Rules (based on spotted tiling representation):

• Lines within tiles → 1
• Lines before spots → 0
• Lines after spots → 2
• Lines at end of odd-position parts → 1

Constraint Guarantees:

• 0 can only be followed by 0 or 2
• 1 can only be followed by 1 or 0
• Cannot start with 2 (0 must precede first 2)
• Cannot end with 0

Bijection with Binary Strings (Theorem 3.4)

Number of EVEN-colored compositions = Sum of products of 1-run lengths across all k-length binary strings

Mapping:

• Prepend 0 to binary string
• Consecutive 0 or 1 substrings map to parts of corresponding size
• 0 substrings → uncolored parts at odd positions
• 1 substrings → colored parts at even positions
• Color choices for each EVEN-colored composition = product of even-position part sizes

Bijection with 321-Avoiding Separable Permutations (Theorem 3.7)

Uses marked binary tree structure:

Mapping (Permutation → EVEN-colored composition):

• For each negative node: left subtree with a leaves + right subtree with b leaves → colored part (a+b-1)_a at even position
• c consecutive increasing leaves between negative nodes → uncolored part c+1 at odd position

Inverse Mapping:

• Odd-position parts minus 1 → leaf count between negative nodes
• Even-position parts plus 1 with color allocation → leaf distribution under negative nodes

Experimental Setup

Data Verification

This is a pure theoretical combinatorics paper without traditional experiments. Verification methods include:

1. OEIS Sequence Verification: Verification through OEIS database
   • A034943: EVEN-colored compositions
   • A095263: ODD-colored compositions
2. Small-Scale Enumeration Verification: Manual enumeration of small integer cases to verify formulas
3. Bijection Correctness: Demonstration through concrete examples of bijection construction

Theoretical Tools

• Generating function theory
• Bijective proof methods
• Spotted tiling visualization

Experimental Results

Main Results

The "results" of this paper are embodied in established equivalences:

1. Theorem 3.1: EVEN-colored compositions ≡ n-colored compositions with restricted color 2
   • Provides constructive bijection based on spotted tilings
2. Theorem 3.2: ODD-colored compositions(k) ≡ (n choose 2)-colored compositions(k+1)
   • Explains sequence relationships observed in OEIS
3. Corollary 1: ODD-colored compositions(k) ≡ 01- and 12-avoiding ternary strings of length k-1
   • Indirectly establishes connection with reference 3
4. Theorem 3.3: EVEN-colored compositions(k) ≡ ternary strings with restricted consecutive digits (length k)
5. Theorem 3.4: EVEN-colored compositions(k+1) = Σ(products of 1-run lengths in k-length binary strings)
6. Theorem 3.5: ODD-colored compositions(k) = Σ(products of 1-run lengths in k-length binary strings starting with 1)
7. Theorem 3.7: EVEN-colored compositions(k) ≡ 321-avoiding separable permutations(k)

Identity Proofs

Theorem 3.6: For any k≥1, ℓ≥2, 1≤m≤ℓ-1: $c_{m,k+1}(\ell+1) = c_{m,k+1}(\ell) + c_{m,k}(\ell)$

Combinatorial proof of special case e(k+1) = e(k) + o(k):

• EVEN-colored compositions(k+1) with first part = 1 → deletion yields ODD-colored compositions(k)
• EVEN-colored compositions(k+1) with first part > 1 → decrement yields EVEN-colored compositions(k)
• This provides bijection to disjoint union

Case Studies

Example 1 (Theorem 3.1):

• Restricted color 2: 3_3, 1_1, 6_4, 4_4
• Mapping process: 3_3 splits to 1+2_2; 1_1 preserved; 6_4 preserved; 4_4 splits to 2+2_2
• Result: 1, 2_2, 1, 6_4, 2, 2_2 (EVEN-colored)

Example 2 (Theorem 3.2):

• ODD-colored: 4_2 + 3_1 + 5_4 + 2_1 + 1_1 = 15
• Maps to (n choose 2)-colored: 7_{2,5} + 7_{4,6} + 2_{1,2} = 16

Example 3 (Theorem 3.3):

• EVEN-colored: 1 + 2_i + 1 + 6_j + 4 (i∈{1,2}, j∈{1,...,6})
• Maps to ternary string: 00200002221111

Example 4 (Theorem 3.7):

• 321-avoiding separable permutation: (1,2,6,7,3,4,5,8,9,10,12,13,11)
• Via binary tree representation maps to: 3 + 4_2 + 4 + 2_2

Theoretical Findings

1. Unified Framework: Positional colored compositions provide a unified counting framework for multiple seemingly unrelated combinatorial objects.
2. Power of Generating Functions: Analysis via generating functions systematically handles position-dependent coloring rules.
3. Constructive Bijections: All bijections are constructive, providing explicit algorithms for object transformation.
4. Importance of Visualization: Spotted tiling representation plays a crucial role in bijection construction.

Related Work

Integer Compositions and Colored Compositions

1. Agarwal (2000)1: First introduced n-colored compositions
2. Hopkins (2012)6: Introduced spotted tiling representation
3. Hopkins & Wang (2021)2: Studied restricted color n-colored compositions
4. Acosta et al. (2019)4: Studied new restricted n-colored composition functions

Related Combinatorial Structures

5. Dedrickson (2012)3: Studied bijections between (n choose 2)-colored compositions and ternary strings
6. Agarwal & Narang (2008)11: Connections between n-colored compositions and lattice paths
7. Collins et al. (2013)10: Relationships between binary words and n-colored compositions

Cyclic and Palindromic Variants

8. Gibson et al. (2018)5: n-colored cyclic compositions
9. Narang & Agarwal (2006)8, Guo (2010)9: Palindromic n-colored compositions

Innovation of This Paper

• Position-Dependent Coloring: First systematic study of position-based coloring rules
• New Bijections: Bijections with 321-avoiding separable permutations and specific ternary strings are novel
• Unified Perspective: Incorporates multiple known results into unified framework

Conclusions and Discussion

Main Conclusions

1. Theoretical Contributions:
   • Defined and studied positional colored compositions as new combinatorial objects
   • Obtained precise counting formulas via generating functions
   • Established equivalences with at least 6 classes of other combinatorial objects
2. Methodological Contributions:
   • Demonstrated effectiveness of generating functions in handling position-dependent rules
   • Provided multiple elegant bijection constructions, enriching combinatorial proof techniques
   • Proved spotted tiling representation to be powerful visualization and construction tool
3. Connectivity Discoveries:
   • Revealed deep connections between restricted color compositions, (n choose 2)-colored compositions, ternary strings, binary string runs, and separable permutations
   • These connections are not merely counting equivalences but have explicit bijective constructions

Limitations

1. General Case Insufficiently Explored:
   • Section 2.3 provides generating functions for (m,k)-n-colored compositions, but connections with other objects limited to m=2 case
   • Combinatorial interpretations for general m values remain to be studied
2. Partial Proof Indirectness:
   • Corollary 1 (ODD-colored compositions and ternary strings) obtained indirectly via Theorem 3.2 and reference 3
   • Direct combinatorial proof might provide deeper insight
3. Unsystematic Generalization:
   • While Theorem 3.6 generalization provided, generalizations of other results lack systematicity
   • Cases with restricted other colors (mentioned in Section 3.1) insufficiently studied
4. Computational Complexity:
   • Algorithm complexity for generating and enumerating these compositions not discussed
   • Computational efficiency of bijections not analyzed

Future Directions

Section 4 explicitly proposes:

1. Combinatorial Interpretations of General Positional Colored Compositions:
   • Study connections between (m,k)-n-colored compositions and other objects
   • Find bijections for general m,k values
2. Direct Proof of Corollary 1:
   • Construct direct bijection between ODD-colored compositions and 01- and 12-avoiding ternary strings
   • Generalize this result to other cases
3. Restricted Color Positional Colored Compositions:
   • Combine ideas from Section 3.1 to study positional colored compositions with restricted colors
   • Explore interesting properties of such compositions
4. Other Position Rules:
   • Consider more complex position-dependent coloring rules
   • E.g., coloring depending on both part size and position
5. Algorithmic and Computational Aspects:
   • Develop efficient generation and enumeration algorithms
   • Study random sampling methods

In-Depth Evaluation

Strengths

1. Strong Conceptual Innovation:
   • Positional colored compositions are natural and meaningful generalization
   • Unifies multiple known combinatorial objects
   • Opens new research directions
2. High Technical Rigor:
   • Generating function derivations clear and complete
   • Bijection constructions detailed and verifiable
   • All main results have rigorous proofs
3. Elegant Bijection Constructions:
   • Bijection with 321-avoiding separable permutations (Theorem 3.7) particularly clever, utilizing binary tree structure
   • Bijection with ternary strings (Theorem 3.3) elegantly exploits line partitioning in spotted tilings
   • Connection with binary string runs (Theorem 3.4) reveals profound counting principles
4. Excellent Visualization:
   • Spotted tiling representation intuitive and clear
   • Figures (e.g., Figures 2-6) effectively aid understanding
   • Examples well-chosen, covering key cases
5. Rich Connectivity:
   • Establishes equivalences with 6 different classes of combinatorial objects
   • Each connection has combinatorial significance
   • Provides multiple entry points for future research
6. High Writing Clarity:
   • Well-organized structure, progressing from special to general cases
   • Clear definitions, consistent notation
   • Proofs easy to follow

Weaknesses

1. Incomplete Generalization:
   • Combinatorial interpretations for general (m,k) cases missing
   • Generating function formulas in Section 2.3 underutilized
   • Limits theoretical completeness
2. Partial Proof Indirectness:
   • Corollary 1 relies on reference 3
   • Direct constructive proof might be more illuminating
   • Authors acknowledge this limitation in Section 4
3. Missing Computational Aspects:
   • Algorithm complexity not discussed
   • No implementation or code provided
   • Limited practical application value
4. Insufficient Comparison with Existing Work:
   • While related literature cited, methods and results not compared in depth
   • Advantages of present approach over existing methods not fully articulated
5. Unclear Application Scenarios:
   • As pure theory, practical applications not discussed
   • Practical significance of positional colored compositions unexplored
   • May limit reader interest
6. Some Proof Details Could Be More Complete:
   • E.g., Theorem 3.7 inverse mapping details on recovering complete permutation from part sizes somewhat sparse
   • Injectivity and surjectivity of bijections sometimes left for reader verification

Impact Assessment

1. High Theoretical Value:
   • Contributes new variant to integer composition theory
   • Reveals deep connections between multiple combinatorial objects
   • Generating functions and bijection methods exemplary
2. Methodological Contributions:
   • Demonstrates systematic approach to position-dependent combinatorial structures
   • Spotted tiling usage provides tool for other problems
   • Bijection construction techniques inspire similar research
3. Strong Potential for Follow-Up Research:
   • Multiple open problems in Section 4 merit exploration
   • Generalizable to other combinatorial object types
   • Possible connections with algebra, topology
4. Strong Reproducibility:
   • All constructions are explicit algorithms
   • Generating functions enable computational verification
   • OEIS sequences provide independent verification
5. Educational Value:
   • Suitable as supplementary course material for combinatorics
   • Demonstrates power of generating functions and bijective proofs
   • Rich examples suitable for learning

Applicable Scenarios

1. Combinatorics Research:
   • Researchers studying integer compositions and variants
   • Generating function theory research
   • Bijective combinatorics research
2. Related Fields:
   • Separable permutation research (related to Theorem 3.7)
   • String combinatorics (related to Theorems 3.3, 3.4)
   • Lattice paths and tilings theory
3. Educational Applications:
   • Case studies for combinatorics courses
   • Teaching examples for generating function methods
   • Training in bijective proof techniques
4. Potential Applications (requiring further research):
   • Coding theory (via string connections)
   • Algorithm analysis (via permutation connections)
   • Probability theory (randomness properties of combinatorial structures)

Key References

1 A.K. Agarwal, "n-colour compositions", Indian J. Pure Appl. Math. 31(2000) 1421–1437.

• Pioneering work introducing n-colored compositions

2 B. Hopkins, H. Wang, "Restricted Color n-color Compositions", Journal of Combinatorics, 12 (2021), 355-377.

• Studies restricted color compositions, directly related to Theorem 3.1

3 C. Dedrickson, "Compositions, Bijections, and Enumerations" (2012), Electronic Theses and Dissertations. 17.

• Establishes bijection between (n choose 2)-colored compositions and ternary strings, foundation for Corollary 1

6 B. Hopkins, "Spotted tilings and n-color compositions", Integers 12B (2012) Article A6

• Introduces spotted tiling representation, core visualization tool of this paper

Overall Assessment

This is a high-quality theoretical combinatorics paper with the following outstanding characteristics:

1. Innovation: Introduces positional colored compositions, providing valuable generalization to integer composition theory.
2. Depth: Beyond providing counting formulas, establishes profound connections with multiple combinatorial objects, each with rigorous bijective proof.
3. Completeness: Logical structure complete from definitions, generating functions, special cases to general cases, and connections with other objects.
4. Technical Excellence: Generating function derivations and bijection constructions demonstrate solid combinatorics foundation.
5. Inspirational Quality: Provides multiple explicit directions for subsequent research with strong continuity.

Recommended Improvements:

• Supplement with combinatorial interpretations for general (m,k) cases
• Provide direct proof of Corollary 1
• Include algorithmic and computational discussion
• Explore practical application scenarios

Overall, this is an excellent paper worthy of publication, making substantive contributions to combinatorics, particularly valuable for researchers interested in integer compositions, generating functions, and bijective proofs.