I think I'm just going to do part 1 naievely; a simple DFS of avaliable towels along with the remaining pattern.

private bool IsAnyPatternPossible(string pattern)
{
    if (pattern.Length == 0) return true;

    foreach (var towel in towels)
    {
        if (pattern.StartsWith(towel) && IsAnyPatternPossible(pattern.Substring(towel.Length)))
        {
            return true;
        }
    }

    return false;
}

Easy.

My first though it to enumerate every bit of the list, with some memoization to help speed things along...

public Dictionary<string, ImmutableList<ImmutableList<string>>> knownPatterns = new Dictionary<string, ImmutableList<ImmutableList<string>>>();

private ImmutableList<ImmutableList<string>> GetAllArrangements(string pattern)
{
    if (knownPatterns.TryGetValue(pattern, out var cachedResult)) return cachedResult;
    if (pattern.Length == 0) return ImmutableList.Create<ImmutableList<string>>();

    var results = new List<ImmutableList<string>>();

    foreach (var towel in towels)
    {
        if (pattern == towel)
        {
            results.Add(ImmutableList.Create(towel));
        }
        else if (pattern.StartsWith(towel))
        {
            foreach (var subList in GetAllArrangements(pattern.Substring(towel.Length)))
            {
                results.Add(subList.Prepend(towel).ToImmutableList());
            }
        }
    }

    knownPatterns[pattern] = results.ToImmutableList();
    return knownPatterns[pattern];
}

... but this is running incredibly slow on the real input.

Actually on second thought this is reminding me a lot of Day 11. I don't need to keep track of the actual pattern lengths, just the actual valid patterns. Much easier just to keep count.

public Dictionary<string, long> knownPatternCounts = new Dictionary<string, long>();
private long GetArrangementCount(string pattern)
{
    if (knownPatternCounts.TryGetValue(pattern, out var cachedResult)) return cachedResult;

    long sum = 0;
    foreach (var towel in towels)
    {
        if (pattern == towel) sum++;
        else if (pattern.StartsWith(towel)) sum += GetArrangementCount(pattern[towel.Length..]);
    }

    knownPatternCounts[pattern] = sum;
    return sum;
}

Shorter, simpler, and runs in 200ms!