---
title: "Stars and Bars Theorem | Combinatorics"
description: "Stars and Bars Theorem counts ways to split identical objects among distinct groups, a core Combinatorics tool for repetition and distribution problems."
canonical: "https://fiveable.me/combinatorics/key-terms/stars-and-bars-theorem"
type: "key-term"
subject: "Combinatorics"
unit: "Unit 2"
---

# Stars and Bars Theorem | Combinatorics

## Definition

The Stars and Bars Theorem is a counting method in combinatorics for distributing identical objects into distinct groups. It turns a distribution problem into a binomial coefficient, usually \(\binom{n+k-1}{k-1}\).

## What It Is

The Stars and Bars Theorem is the combinatorics method you use when you need to count ways to place identical items into distinct boxes. The “stars” are the identical objects, and the “bars” are the dividers that separate the groups. That picture turns a messy distribution problem into a clean counting problem.

The standard setup is: you have n identical objects and k distinct categories, and each category can get zero or more objects. The number of distributions is \(\binom{n+k-1}{k-1}\), which is the same as \(\binom{n+k-1}{n}\). Those two forms say the same thing, just from different counting viewpoints.

A fast way to see why it works is to line up all the stars in a row, then choose where the bars go. If you have 5 identical candies and 3 children, one distribution might look like \(\ast\ast|\ast|\ast\ast\). That means the first child gets 2 candies, the second gets 1, and the third gets 2. Every valid distribution with possible empty groups has one and only one stars-and-bars picture.

The condition that the objects are identical matters a lot. If the objects were different, stars and bars would not be the right tool, because then order and identity would matter too. This method is really about combinations with repetition, not about arranging distinct items.

A common mistake is forgetting that empty groups are allowed in the basic version. An empty box just means two bars can sit next to each other, or a bar can appear at an edge of the row. That is why the formula uses \(k-1\) bars and not something more complicated.

If the problem adds restrictions, like each group must get at least one object, you usually adjust the setup first. For example, you may give one object to each group before using stars and bars on the remaining objects. That small shift is often the whole trick.

## Why It Matters

Stars and Bars Theorem shows up whenever Combinatorics asks you to count distributions instead of arrangements. It gives you a direct way to handle repetition without listing every possibility, which is exactly the kind of move that saves time on problem sets and quizzes.

It also connects a few ideas that show up all over the course. You can see it as a special case of combinations with repetition, and it sits close to binomial coefficients because the final answer is written as a choose function. That makes it a bridge between counting objects, choosing positions, and building integer solutions.

This theorem is especially useful in problems that look like “How many ways can you split X identical items among Y people?” or “How many nonnegative integer solutions does \(x_1 + x_2 + x_3 = n\) have?” Once you spot that the variables are nonnegative and the total is fixed, you can translate the problem into stars and bars instead of guessing or listing cases.

It also trains a habit that matters throughout combinatorics: reframe the question before you count. Instead of treating every problem as a direct multiplication or permutation question, you learn to look for structure, like identical objects, distinct categories, and allowed repeats. That pattern recognition is a big part of doing well in the course.

## Connections

### Combinations with Repetition

Stars and Bars is one of the main ways to count combinations with repetition. The connection is that you are choosing how many of each type to take, not which distinct objects to order. If a problem says repeats are allowed and order does not matter, this theorem is often the counting move behind the scenes.

### Binomial Coefficient

The final answer in stars and bars is written with a binomial coefficient, usually \(\binom{n+k-1}{k-1}\). That means the problem gets converted into choosing positions for bars or stars. If you already know how to read and simplify choose notation, the theorem feels much more natural.

### [Arranging Indistinguishable Objects](/combinatorics/key-terms/arranging-indistinguishable-objects)

This is the visual idea at the heart of stars and bars. The stars represent identical objects, so swapping them does not create a new outcome. The arrangement is really about where the separators go, which is why the method works so cleanly for identical items.

### Multinomial Coefficient

Both topics count ways to break something into parts, but they do it in different settings. Stars and bars is for identical objects going into distinct groups, while multinomial coefficients usually count ways to split or arrange categories in a more direct algebraic form. They can appear in similar distribution problems, so it helps to know which structure the question gives you.

## On the AP Exam

A problem set or quiz question will usually ask you to count nonnegative integer solutions, distribute identical objects, or choose items with repetition allowed. Your job is to spot the stars and bars setup, rewrite the situation as a sum or distribution, and then apply the choose formula correctly. A common move is to check whether empty groups are allowed, since that changes whether you use the basic form right away or shift the variables first.

If the problem adds a minimum requirement, like each category must get at least one, you often subtract 1 from each variable first and count the leftover objects. If the question uses words like “identical,” “indistinguishable,” “repetition allowed,” or “nonnegative integer solutions,” that is a strong signal to try stars and bars before anything else.

## Stars and Bars Theorem vs Multinomial Coefficient

These get mixed up because both involve splitting something into parts. Stars and Bars counts ways to distribute identical objects into distinct boxes, while multinomial coefficients usually count arrangements when you already have category sizes or labeled groups. If the objects are indistinguishable and you are only tracking how many go in each group, stars and bars is usually the better fit.

## Key Takeaways

- Stars and Bars is the combinatorics method for counting ways to distribute identical objects into distinct groups.
- The basic formula is \(\binom{n+k-1}{k-1}\), where n is the number of objects and k is the number of groups.
- The method works for nonnegative counts, so empty groups are allowed unless the problem says otherwise.
- If a problem requires at least one object in each group, adjust the counts first before using the formula.
- When you see identical objects, repetition, or nonnegative integer solutions, stars and bars is often the right counting setup.

## FAQs

### What is Stars and Bars Theorem in Combinatorics?

It is a counting method for distributing identical objects into distinct groups. You represent the objects as stars and the dividers as bars, then count the arrangements with a binomial coefficient. In the basic form, the number of distributions is \(\binom{n+k-1}{k-1}\).

### When do you use Stars and Bars Theorem?

Use it when the objects are identical, the groups are distinct, and repetition is allowed in the sense that a group can get more than one object. It also shows up in nonnegative integer equations like \(x_1+x_2+\cdots+x_k=n\). If order matters or the objects are different, this is usually not the right tool.

### What is the formula for Stars and Bars Theorem?

The basic formula is \(\binom{n+k-1}{k-1}\), where n is the number of identical objects and k is the number of distinct groups. You can also write it as \(\binom{n+k-1}{n}\). Both forms count the same thing, just from different viewpoints.

### How is Stars and Bars different from a multinomial coefficient?

Stars and Bars counts distributions of identical items among labeled groups. A multinomial coefficient is usually used when you are arranging items into categories with fixed counts, or when the categories are part of a larger arrangement problem. They can look similar, but stars and bars is the cleaner choice for nonnegative integer distribution problems.

## Related Study Guides

- [2.4 Combinations with repetition](/combinatorics/unit-2/combinations-repetition/study-guide/7VKVq8hvWxc0lPHI)

## About This Document

Canonical Fiveable pages are available as Markdown at the same path plus `.md`.

- [llms.txt](https://fiveable.me/llms.txt): index of Fiveable's sections and URL patterns
- [llms-full.txt](https://fiveable.me/llms-full.txt): complete subject and unit listing
- [MCP server](https://fiveable.me/mcp): call Fiveable as tools instead of fetching pages (`https://fiveable.me/api/mcp`)
- [MCP server for AP teachers](https://fiveable.me/mcp/teachers): a teacher's classes, assignments and AP-rubric grading (`https://fiveable.me/api/mcp/teacher`)

## Structured Data

```json
{"@context":"https://schema.org","@graph":[{"@type":"LearningResource","@id":"https://fiveable.me/combinatorics/key-terms/stars-and-bars-theorem#resource","name":"Stars and Bars Theorem | Combinatorics","url":"https://fiveable.me/combinatorics/key-terms/stars-and-bars-theorem","learningResourceType":"Concept explainer","educationalLevel":"AP® / High School","about":{"@id":"https://fiveable.me/combinatorics/key-terms/stars-and-bars-theorem#term"},"audience":{"@type":"EducationalAudience","educationalRole":"student"},"dateModified":"2026-07-03T02:21:06.613Z","isPartOf":{"@type":"Collection","name":"Combinatorics Key Terms","url":"https://fiveable.me/combinatorics/key-terms"},"author":{"@type":"Organization","@id":"https://fiveable.me/editorial#content-team","name":"Fiveable Content Team","url":"https://fiveable.me/editorial","parentOrganization":{"@id":"https://fiveable.me/#organization"},"member":[{"@type":"Person","name":"Amanda DoAmaral","sameAs":["https://www.linkedin.com/in/adoamaral"]},{"@type":"Person","name":"Becky Bahr","sameAs":["https://www.linkedin.com/in/becky-bahr-b52743132"]}]},"publisher":{"@type":"Organization","name":"Fiveable","url":"https://fiveable.me"}},{"@type":"DefinedTerm","@id":"https://fiveable.me/combinatorics/key-terms/stars-and-bars-theorem#term","name":"Stars and Bars Theorem","description":"The Stars and Bars Theorem is a counting method in combinatorics for distributing identical objects into distinct groups. It turns a distribution problem into a binomial coefficient, usually \\(\\binom{n+k-1}{k-1}\\).","url":"https://fiveable.me/combinatorics/key-terms/stars-and-bars-theorem","inDefinedTermSet":{"@type":"DefinedTermSet","name":"Combinatorics Key Terms","url":"https://fiveable.me/combinatorics/key-terms"}},{"@type":"FAQPage","mainEntity":[{"@type":"Question","name":"What is Stars and Bars Theorem in Combinatorics?","acceptedAnswer":{"@type":"Answer","text":"It is a counting method for distributing identical objects into distinct groups. You represent the objects as stars and the dividers as bars, then count the arrangements with a binomial coefficient. In the basic form, the number of distributions is \\(\\binom{n+k-1}{k-1}\\)."}},{"@type":"Question","name":"When do you use Stars and Bars Theorem?","acceptedAnswer":{"@type":"Answer","text":"Use it when the objects are identical, the groups are distinct, and repetition is allowed in the sense that a group can get more than one object. It also shows up in nonnegative integer equations like \\(x_1+x_2+\\cdots+x_k=n\\). If order matters or the objects are different, this is usually not the right tool."}},{"@type":"Question","name":"What is the formula for Stars and Bars Theorem?","acceptedAnswer":{"@type":"Answer","text":"The basic formula is \\(\\binom{n+k-1}{k-1}\\), where n is the number of identical objects and k is the number of distinct groups. You can also write it as \\(\\binom{n+k-1}{n}\\). Both forms count the same thing, just from different viewpoints."}},{"@type":"Question","name":"How is Stars and Bars different from a multinomial coefficient?","acceptedAnswer":{"@type":"Answer","text":"Stars and Bars counts distributions of identical items among labeled groups. A multinomial coefficient is usually used when you are arranging items into categories with fixed counts, or when the categories are part of a larger arrangement problem. They can look similar, but stars and bars is the cleaner choice for nonnegative integer distribution problems."}}]},{"@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"name":"Combinatorics","item":"https://fiveable.me/combinatorics"},{"@type":"ListItem","position":2,"name":"Key Terms","item":"https://fiveable.me/combinatorics/key-terms"},{"@type":"ListItem","position":3,"name":"Unit 2","item":"https://fiveable.me/combinatorics/unit-2"},{"@type":"ListItem","position":4,"name":"Stars and Bars Theorem"}]}]}
```