Integer compositions count
The number 5 can be written as an ordered sum in 16 ways, because the count of compositions is always 2^(n-1). Enter n up to 10000 and get the exact count, even when it runs to thousands of digits. Free in your browser.
- Free
- Runs in your browser
- No sign-up
- Your data stays on your device
Run — free
Worked example
- N
- 5
- Quantity
- 16
An ordered composition of a positive integer n is a tuple of positive integers that add to n, where the order of the parts is part of the identity: 1+3 and 3+1 are two different compositions of four. Classic combinatorics proves that the number of such ordered sums is always two to the power of n minus one.
Why the number of ordered compositions is two to the n minus one
Write n ones in a row. Between those ones sit exactly n minus one gaps. For each gap you may either insert a bar that splits the sequence into a new part or leave the gap empty so the adjacent ones stay glued together as a larger part.
Every pattern of bars and empty gaps produces one ordered composition of n, and every composition arises from exactly one such pattern. Because each of the n minus one gaps has two independent choices, the total number of patterns is two raised to the power n minus one. That identity is the entire algorithm this capability evaluates: it does not recurse through first-part branches, does not allocate an array of tuples, and does not sample.
A one-line check for n equals four is eight, matching the eight compositions (4), (1,3), (3,1), (2,2), (1,1,2), (1,2,1), (2,1,1), and (1,1,1,1). For n equals one there is a single empty-gap pattern and the count is one, the composition (1) itself. The closed form is exact for every positive integer, so a homework paper that claims nine compositions of four is simply wrong, and a generator that needs the size of the composition family can size buffers from this count without ever listing them.
Order is essential: if you identify 1+3 with 3+1 you have left compositions and entered the world of partitions, whose count p(n) has no such power-of-two formula and is a different search intent.
Where a compositions count belongs, and how it is priced
Use this count when the question is how many ordered sums exist, not which tuples they are. Contest programmers assert candidate solutions for composition-counting problems against a deterministic oracle instead of reimplementing a BigInt power in every language harness. Teachers assign the gap-separator proof and need a machine check that 2^(n-1) really is the size of the family before students try to list it.
Interview sandboxes and generating-function demos need the same number every time they ask. Data and compiler work sometimes sizes a search space of ordered stage splits of a budget n and must know the cardinality before allocating. If you actually need every tuple, stop here and use a listing tool on a small n; if you need compositions into exactly k parts, that is the binomial C(n-1, k-1) and a different landing; if order does not matter, you want the partition function p(n).
Keep n inside the documented bounds, treat the string count as the exact integer, and you get a reproducible compositions count without installing a computer-algebra system.
What you can do with it
Homework checks of the 2^(n-1) identity
Give students a positive n and verify that their hand-counted compositions match the closed form before they list every tuple.
Contest and interview validators
Assert candidate solutions for composition-counting problems against an exact BigInt count instead of reimplementing a power of two in every harness.
Search-space sizing for ordered splits
Learn how many ordered stage splits of a budget n exist before allocating buffers or launching an enumerator.
FAQ
What does the integer compositions count return?
For a positive integer n it returns the exact number of ordered compositions of n as a decimal string, plus the formula 2^(n-1). It does not list the tuples.
Why is the formula two to the n minus one and not 2^n?
There are n ones in a row and only n−1 gaps between them. Each gap is a binary choice (bar or no bar), so the count is 2^(n−1), not 2^n.
Does this enumerate every composition?
No. This landing answers how many compositions exist. Listing every ordered tuple is a different task and is only practical for small n.
How is the compositions count priced?
The browser tool is free and runs locally.
How many compositions does the number 5 have?
It has 16. Between five ones there are 4 gaps, and each gap either gets a split or not: 2 choices per gap, so 2^4 = 16 ordered sums in total.
Related tools
For developers — API access
Everything on this page is available programmatically. This section is for teams who want to wire it into their own systems; everyone else can just use the tool above.
API endpoint
Prefer to automate it? One authenticated POST creates the task; the result comes back by webhook or a signed link. The same capability also runs here on the web, by email and from Telegram — and soon from our app too.
Call it from your stack
curl -X POST https://api.kit.forhosting.com/numth/compositions-count \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"n":5}'const res = await fetch("https://api.kit.forhosting.com/numth/compositions-count", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"n": 5
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/compositions-count",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"n": 5
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/compositions-count", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"n":5}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"n":5}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/compositions-count", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Example request
{
"n": 5
}Example response
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.compositions_count",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}The API is asynchronous: the call returns a task_id immediately and the result arrives by webhook. Polling is capped at 1 req/s per task.
Pricing
Published price — no tokens, no invented credits. A failed task is never charged.
Limits
min_n | 1 |
max_n | 10000 |
Errors
| HTTP | Code | Meaning |
|---|---|---|
401 | unauthorized | Missing or invalid API key. |
402 | insufficient_balance | Your balance doesn't cover the task price. |
404 | unknown_type | That task type doesn't exist. |
429 | rate_limited | Too many requests. Use the webhook instead of polling. |
Technical notes
The same pure function runs in the free browser tool and on the API path. Values of n below one are rejected with invalid_input and are never billed.
What you send, what you get back, and when the request fails
The product rule is strict: n below one is invalid, including zero and every negative, because the usual definition of a composition requires a positive integer to compose. The count is a string on purpose: two to the fifty-three already leaves the JavaScript safe-integer range, and this landing is useful precisely when n is large enough that listing every composition is hopeless. Failed validation is not charged. POST a JSON body with the required positive integer n, the integer whose ordered compositions you want to count. Aliases integer, value, and N are accepted for the same field. n must be a whole number from one through ten thousand; numeric strings of digits are accepted, while fractions, booleans, empty strings, and missing fields fail with invalid_input naming n. Values above the published maximum also fail so a multi-thousand-digit power of two cannot stall the Worker or the browser. On success the response echoes the normalized n, returns count as a decimal string of the exact value 2^(n-1), and includes formula as the identity string 2^(n-1) so clients can display the theorem without hard-coding it. Typical checks you can pin in tests: n equals one yields count 1; n equals five yields count 16; n equals ten yields count 512; n equals zero is invalid_input.
Where a compositions count belongs, and how it is priced
API usage draws from prepaid KIT balance at the published $0.002 base price per successful item; invalid_input does not consume balance.
Technical questions
Which values of n are accepted?
Integers from 1 through 10000. Zero, negatives, fractions, missing n, and values above the maximum fail with invalid_input and are not charged.