# How many Carlitz compositions are there?

OEIS sequence A003242 comprises the numbers of Carlitz compositions for any given positive integer. This is the number of integer partitions of the integer for which no two adjacent parts are equal.

For example, for 4:

1. Generate the possible integer partitions (and their permutations): [1,1,1,1], [1,1,2], [1,2,1], [2,1,1], [1,3], [3,1], [2,2], [4]
2. Filter out those which have adjacent equal parts, leaving: [1,2,1], [1,3], [3,1], [4]
3. Count, giving us our result of 4

The first 16 terms, using zero-indexing are:

1, 1, 1, 3, 4, 7, 14, 23, 39, 71, 124, 214, 378, 661, 1152, 2024

Pleasingly, the recently arrived year, 2024, is the value of this sequence where $$\n = 15\$$.

This is code golf, so the shortest answer in bytes per language wins. Standard loopholes are forbidden. This is also a sequence challenge, so you may take an integer argument and return the nth term, take an integer argument and return the first n terms, or take no arguments and return the infinite sequence. You may use zero- or one- indexing.

• What does "You may use zero- or one- indexing" mean in this case? For input 4, what possible outputs are allowed, assuming I'm only outputting one term per input and other inputs are consistent with this.
– Tbw
Jan 3 at 0:18
• For example, I have an answer where f(0)=1, f(1)=1, f(2)=3, f(14)=2024. Is that ok?
– Tbw
Jan 3 at 0:19
• @Tbw that wasn’t quite what I meant, but happy with that approach Jan 3 at 1:25

# Maxima, 54 bytes

The G.f.(Generating function) of the sequence is:

$$\frac{1}{1 - \sum\limits_{k>0} \frac{x^k}{(1+x^k)}}$$

Golfed version (process-oriented programming, 42 bytes). Try it online!

taylor(1/(1-sum(x^k/(1+x^k),k,1,N)),x,0,N)

Golfed version (lambda function that returns the first N terms, 54 bytes). Try it online!

lambda([N],taylor(1/(1-sum(x^k/(1+x^k),k,1,N)),x,0,N))

# Nekomata + -n, 5 bytes

řJĉᵐz

Attempt This Online!

řJĉᵐz   Take input n
ř       Generate a list of n copies of n
e.g. 3 -> [3,3,3]
J      Non-deterministically split into a list of sublists
e.g. [3,3,3] -> [[3],[3],[3]] or [[3],[3,3]] or [[3,3],[3]] or [[3,3,3]]
ĉ     Split into runs of identical elements
e.g. [[3],[3],[3]] -> [[[3],[3],[3]]]
[[3],[3,3]]   -> [[[3]],[[3,3]]]
[[3,3],[3]]   -> [[[3,3]],[[3]]]
[[3,3,3]]     -> [[[3,3,3]]]
ᵐz   Check if each run has length 1
e.g. [[[3],[3],[3]]] fails, others pass

-n counts the number of solutions. In the example above, there are 3 solutions that pass the final check, so the output for 3 is 3.

# R, 91 84 bytes

\(n)sum(sapply(unique(combn(rep(0:n,n),n,\(x)x[x>0],F)),\(y)sum(y)==n&all(diff(y))))

Attempt This Online!

Starts from 1.

-20 bytes thanks to @xnor!

p#0=1
p#n=sum[i#(n-i)|i<-[1..n],i/=p]
f=(0#)

Try it online!

• You don't need to generate the compositions and take their lengths, you can work with the counts directly: TIO
– xnor
Jan 1 at 23:13

# Vyxal, 11 bytes

ṄvṖÞfU'¯A;L

Try it Online!

Ṅ           # Integer partitions
vṖÞf       # All permutations of each
U      # Uniquified
'  ;  # Filtered by
¯    # Consecutive differences
A   # Are all nonzero
L # Length

# JavaScript (Node.js), 44 bytes

f=(n,e,i=n)=>i?f(n,e,i-1)+(i^e&&f(n-i,i)):!n

Try it online!

n(input) e(last choice) i(loop)

# Haskell + hgl, 13 bytes

l<pST(fo<pnq)

Attempt This Online!

## Explanation

Does the task as straight forward as possible:

• l number of
• pST partitions such that
• fo all
• pnq consecutive elements are non-equal

Notably because pST works on any type of free monoid, you can give this a list as well.

# Reflection

I am quite happy with this answer. The one thing I would add is a function which precomposes l with pST.

# Charcoal, 30 bytes

⊞υ⟦¹⟧ＦＮ⊞υＥ⁺²ι∧κΣＥ§υ±κ∧⁻νκμＩΣ⊟υ

Try it online! Link is to verbose version of code. Explanation: Uses dynamic programming to calculate the number of permutations of n that end in each of the values 1 .. n.

⊞υ⟦¹⟧

ＦＮ

Repeat n times.

⊞υＥ⁺²ι∧κΣＥ§υ±κ∧⁻νκμ

For each i from 1 to n, calculate how many of the permutations of n-i do not end in i.

ＩΣ⊟υ

Output the total number of permutations for n.

• Really like your approach here! Jan 1 at 18:03

# APL(Dyalog Unicode), 34,2521 bytes SBCS

{≢⍸(∧/2≢/⊂⍨)¨2|⍳2⌊⍳⍵}

Try it on APLgolf!

-4 bytes thanks to att.

A function which takes a positive integer on the right and returns the numbers of Carlitz compositions for that number.

### Explanation

{≢⍸(∧/2≢/⊂⍨)¨2|⍳2⌊⍳⍵}­⁡​‎‎⁪⁡⁪⁠⁪⁢⁡⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁡⁤⁪‏‏​⁡⁠⁡‌⁢​‎‎⁪⁡⁪⁠⁪⁢⁡⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁡⁢⁪‏‏​⁡⁠⁡‌⁣​‎‎⁪⁡⁪⁠⁪⁤⁤⁪‏‏​⁡⁠⁡‌⁤​‎‎⁪⁡⁪⁠⁪⁤⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁤⁣⁪‏‏​⁡⁠⁡‌⁢⁡​‎‎⁪⁡⁪⁠⁪⁤⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁤⁪‏⁠‎⁪⁡⁪⁠⁪⁤⁡⁪‏‏​⁡⁠⁡‌⁢⁢​‎‎⁪⁡⁪⁠⁪⁣⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁣⁪‏‏​⁡⁠⁡‌⁢⁣​‎‎⁪⁡⁪⁠⁪⁢⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁤⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁡⁪‏‏​⁡⁠⁡‌⁢⁤​‎‎⁪⁡⁪⁠⁪⁢⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁢⁪‏‏​⁡⁠⁡‌⁣⁡​‎‎⁪⁡⁪⁠⁪⁣⁪‏‏​⁡⁠⁡‌⁣⁢​‎‎⁪⁡⁪⁠⁪⁢⁪‏‏​⁡⁠⁡‌­
⍳⍵   ⍝ ‎⁡‎⁡1,2,3,...,input
2⌊     ⍝ ‎⁢‎⁢min each with 2
⍳       ⍝ ‎⁣range
⍝ ‎⁣  on an array, all combinations of ranges
2|        ⍝ ‎⁤each mod 2
(       )¨          ⍝ ‎⁢⁡for each:
⊂⍨            ⍝ ‎⁢⁢partition itself, splitting on 1s
2≢/              ⍝ ‎⁢⁣tests if consecutive runs don't match
∧/                 ⍝ ‎⁢⁤AND reduce
⍝ ‎⁢⁤  tests if all consecutive don't match
⍸                    ⍝ ‎⁣⁡locations of 1s
≢                     ⍝ ‎⁣⁢count
💎

Created with the help of Luminespire.

• 21 bytes
– att
Jan 3 at 3:36

# 05AB1E, 9 bytes

и.œʒÅγP}g

Port of alephalpha's Nekomata answer, so make sure to upvote that answer as well!

A straight-forward approach would be 12 bytes instead:

ÅœεœÙεüÊP]˜O

Explanation:

и         # Repeat the (implicit) input the (implicit) input amount of times as list
.œ       # Get all partitions of this list
ʒ      # Filter it by:
Åγ    #  Run-length encode it; pushing a list of values and lengths
P   #  Take the product of the list of lengths
#  (only 1 is truthy in 05AB1E)
}g     # After the filter: pop and push the length
# (which is output implicitly as result)
Åœ        # Get all (sorted) lists of positive integers that sum to the (implicit) inpt
ε       # Map over each inner list:
œ      #  Get all its permutations
Ù     #  Uniquify this list of lists
ε    #  Inner map over each unique permutation-list:
ü   #   Map over each overlapping pair of values:
Ê  #    Check that they are NOT the same
P #   Check that this is truthy for all of them in this permutation
]       # Close the nested maps
˜      # Flatten the list of lists
O     # Sum all truthy values together
# (which is output implicitly as result)

# Desmos, 106 104 bytes

f(k)=1+∑_{n=2}^{k^k}0^{(B.total-k)^2}sgn(BB[2...]-BB)^2.min
B=mod(floor(n/k^{[floor(log_kn)...-1]}),k)

Try It On Desmos!

Try It On Desmos! - Prettified

Brute force but horribly inefficient. I tried looking at the other answers for some other methods but I'm too smooth brained to understand any of it so I just decided to do brute force lmfao. This is definitely slower than $$\O(k^k)\$$ time complexity, where $$\k\$$ is input. It can only run inputs $$\0\$$ through $$\7\$$ in a reasonable amount of time, and $$\8\$$ took a couple minutes to run, but still returned the right answer, $$\39\$$ (you can try this yourself if you have a bit of time to kill lol). I would not suggest you try $$\9\$$, unless you got supercomputers or something.

But with that being said, I still like this answer because it involves a bit of ingenuity by combining two conditions into one with sgn(BB[2...]-BB)^2.min. I tried to combine the third condition, 0^{(B.total-k)^2}, into there as well, but couldn't think of a way to make it work. I might post an explanation in the near future to elaborate further on this.

# R, 65 bytes

a=\(n)"if"(n,sum(sapply(1:n,\(k)a(n-k)*-(-1)^(1:k)%*%!k%%1:k)),1)

Attempt This Online!

OEIS contains the following formula: a(n) = Sum_{k=1..n} A048272(k)*a(n-k), n>1, a(0)=1, where A048272(k) is the number of odd divisors of k minus the number of even divisors of k. No need to generate all the partitions or to understand generating functions.