Stars and Bars

Stars and bars counts distributions of identical objects among distinct labeled groups. It is not a permutation formula: objects are indistinguishable, but the recipient groups have identities. Translating an allocation into stars separated by bars gives a bijection to choosing bar positions. We implement exact counts for nonnegative and strictly positive solutions within a small safe Pascal-table bound.

Prerequisites: Combinations; Pascal DP; careful counting models.

Build the idea

1. 1. Encode a nonnegative solution

   For x₁+…+x_k=n with xᵢ≥0, write n stars and k−1 bars. Stars before the first bar go to group one, between bars to the next group, and after the last bar to the last. Adjacent bars represent an empty group, so zero allocations are allowed. Every allocation has exactly one encoding and every encoding decodes uniquely.

   $$x₁+\dots +x_k=n\Rightarrow \mathrm{count}=C(n+k-1,k-1)$$

2. 2. Choose the bar positions

   There are n+k−1 positions containing n identical stars and k−1 identical bars. Choose which k−1 positions contain bars, giving C(n+k−1,k−1). For n=5,k=3 the count is C(7,2)=21. No factor k! is removed because the groups are labeled: allocating (5,0,0) differs from (0,5,0).

3. 3. Convert strictly positive allocations

   Require each xᵢ≥1 by assigning one object to each group first. Set yᵢ=xᵢ−1≥0, leaving total n−k. If n<k, no solution exists. Otherwise the nonnegative formula becomes C(n−1,k−1). For five objects in three positive groups, C(4,2)=6.

   $$xᵢ\ge 1,yᵢ=xᵢ-1,\Sigma yᵢ=n-k$$

4. 4. Handle boundaries and repetitions correctly

   For n=0,k≥1, the nonnegative allocation is uniquely all zeros. With k=1, either model has one allocation when its lower bound is satisfied. The program excludes k=0 to avoid a separate empty-group convention. Choosing a multiset of n items from k TYPES is equivalent to nonnegative counts per type and has C(n+k−1,n) possibilities, unlike choosing n distinct objects without repetition.

5. 5. Know when the model breaks

   Upper bounds xᵢ≤uᵢ are not handled by the simple formula; use inclusion–exclusion or DP. Distinct objects, unlabeled groups and order within groups change the combinatorial model. The exact implementation uses a Pascal table only through n+k−1≤60, avoiding overflow and modular inverses. Larger parameters need a different number representation or modular method.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: 5. Know when the model breaks Upper bounds xᵢ≤uᵢ are not handled by the simple formula;
// use inclusion–exclusion or DP.
#include<iostream>
#include<vector>
int main(){
    int n,k;
    std::cin>>n>>k;
    int N=n+k-1;
    std::vector<std::vector<long long>>choose(N+1,std::vector<long long>(N+1,0));
    for(int i=0;i<=N;++i){
        choose[i][0]=choose[i][i]=1;
        for(int j=1;j<i;++j){
            choose[i][j]=choose[i-1][j]+choose[i-1][j-1];
        }
    }
    long long nonnegative=choose[N][k-1];
    long long positive=n<k?0:choose[n-1][k-1];
    std::cout<<nonnegative<<' '<<positive<<'\n';
}

Complexity analysis

O((n+k)²) time and memory for the exact Pascal table; final lookups are O(1). The contract n≥0,k≥1,n+k−1≤60 keeps all coefficients within long long. A preprocessed modular table can support larger suitable queries but changes exact counts into residues.

Example input and output

Read n k with n≥0, k≥1 and n+k−1≤60. Print counts of nonnegative and strictly positive integer solutions to x₁+…+x_k=n.

Input

5 3

Output

21 6

Nonnegative solutions choose two bars among seven positions; positive solutions first reserve one star per group, leaving two stars and two bars.

Practical applications

Use for integer composition counts, distributing identical units and combinations with repetition. For bounded allocations use DP or inclusion–exclusion. For arrangements of distinct objects use permutations or other assignment counts instead.

Check your understanding

Which assumption belongs to the basic stars-and-bars formula?

Put it into practice

Enumerate all triples summing to small n and compare both lower-bound versions.