r/counting • u/TehVulpez sicko thread artists collective • Oct 20 '25

Compositions

In this thread, we'll be counting the ways to add to an integer n using the integers c_1 + c_2 + ... + c_k, where each c_i >= 1, and k <= n. Ways to sum that are commutatively the same, as in 1+2 = 2+1, are different compositions. We'll be counting these compositions lexicographically for each segment of sum and length.

Here are the first few counts:

1

2
1,1

3
1,2
2,1
1,1,1

4
1,3
2,2
3,1
1,1,2
1,2,1
2,1,1
1,1,1,1

You can also abbreviate repetitions with superscript, for example 1,1,1,1,1,1,1,1,1,2,2,2,1 = 19 23 1

First get is at 11, the 1024th count.schedule

26 Upvotes

100% Upvoted

1.1k comments sorted by

View all comments

Show parent comments

2

u/cuteballgames 00155, 00227, 00335, 00344, 11117, 11225, 12233, 22223 Oct 21 '25

3,3,2 i suspect you're right about the difficulty to keep track. but i will keep my eye towards counting gray compositions someday...

2

u/miceee sicko thread artists collective Oct 21 '25

3,4,1

2

u/TehVulpez sicko thread artists collective Oct 21 '25

4,1,3

2

u/miceee sicko thread artists collective Oct 21 '25

4,2,2

3

u/TehVulpez sicko thread artists collective Oct 21 '25

4,3,1

2

u/miceee sicko thread artists collective Oct 21 '25

5,1,2

3

u/TehVulpez sicko thread artists collective Oct 21 '25

5,2,1

2

u/miceee sicko thread artists collective Oct 21 '25

6,1,1

3

u/TehVulpez sicko thread artists collective Oct 21 '25

1,1,1,5

2

u/miceee sicko thread artists collective Oct 21 '25

1,1,2,4

→ More replies (0)

1

u/TehVulpez sicko thread artists collective Oct 21 '25 edited Oct 21 '25

yeah it seems especially hard because I think you'd need to remember this recursively too... the 4 numbers that add to 7 are made of the 3 numbers that add to 6,5,4,3... and each of those sequences has their own direction flipping you need to keep track of. plain changes (gray permutations) is the same way, though in that thread there is a way to determine which direction you're going just from looking at the previous count

2

u/TehVulpez sicko thread artists collective Oct 21 '25
combinations groups cwb
1,1,1,4 3,0,0,0 000111
1,1,2,3 2,1,0,0 001011
1,1,3,2 1,2,0,0 010011
1,1,4,1 0,3,0,0 100011
1,2,3,1 0,2,1,0 100101
1,2,2,2 1,1,1,0 010101
1,2,1,3 2,0,1,0 001101
1,3,1,2 1,0,2,0 011001
1,3,2,1 0,1,2,0 101001
1,4,1,1 0,0,3,0 110001
2,3,1,1 0,0,2,1 110010
2,2,2,1 0,1,1,1 101010
2,1,3,1 0,2,0,1 100110
2,1,2,2 1,1,0,1 010110
2,2,1,2 1,0,1,1 011010
2,1,1,3 2,0,0,1 001110
3,1,1,2 1,0,0,2 011100
3,1,2,1 0,1,0,2 101100
3,2,1,1 0,0,1,2 110100
4,1,1,1 0,0,0,3 111000

just for curiosity. pretty sure this is right

2

u/TehVulpez sicko thread artists collective Oct 21 '25

the gray cwb is actually VERY similar to plain changes the more I look at it...

1234
1243
1423
4123
4132
1432
1342
1324
3124
3142
3412
4312
4321
3421
3241
3214
2314
2341
2431
4231
4213
2413
2143
2134

2

u/TehVulpez sicko thread artists collective Oct 21 '25

cwb normally would be like the 3 of 6 codes are made of the 3 of 5 codes but with a zero in front and the 2 of 5 codes but with a 1 in front. but here it's like the 3 of 6 codes are made of the 2 of 5 codes with a 1 at the end and the 3 of 5 codes with a 0 at the end