Question

How many compositions of n with k parts are there in which each part is a even number
except that a 1 may occur as a part at most once?

Answer 1

I can't figure out the generating series to solve for this because I don't know how to deal with the 1 occurring at most once part.

Answer 2

What is a composition in this context?

Answer 3

A composition of n is (c1,...,ck) such that each ci is a positive integer and c1+...+ck = n

Answer 4

Interesting.

Answer 5

so the compositions of 4 are (4),(3,1),(2,2),(1,3),(2,1,1) etc

Answer 6

So 1 many occur 0 or 1 times.

Answer 7

yes

Answer 8

Order of the sum doesn't matter?

Answer 9

You distinguish (1,3) and (3,1)

Answer 10

I think those would be distinct compositions

Answer 11

What reasoning did you use to get the case with no extra conditions?

Answer 12

well I could use a generating series that looks like this\[\Phi_S(x) = (\sum\limits_{i\geq0}^{}x^{2i+2})^k\]

Answer 13

That doesn't have \(n\) in it. What does it count?

Answer 14

then you can simplify that to be
\[(x^2(1-x^2))^k\] by using the geometric series
then you find the nth coefficient of that. so,
\[[x^n](x^2(1-x^2))^k\]

where [x^n] is the nth coeffiecient and that gives the answer

Answer 15

Is there some theorem you are using? Where did you get \(x^{2i+2}\)?

Answer 16

I think I'm making this a lot more complicated sounding. I'm going to post the example I'm looking at

Answer 17

https://db.tt/PkWzwRXl
https://db.tt/G9FGb8cO

Answer 18

this is the simpler example for finding the number of k-part compositions of n in which each part is an odd number

Answer 19

Why did you go with \(2i+2\) instead of just \(2i\), out of curiosity?

Answer 20

I needed to exclude 0 since it's not a positive integer

Answer 21

Hmmm, okay we can count the ways in which 1 happens 0 times (all even)
Then we can count the ways in which 1 occurs one times.
There should be no overlap, right? So add these ones up.

Answer 22

For 1 to happens once, we simply guarantee it will be in the composition.
This means we first subtract it out of \(n\), giving us \(n-1\) and we deal with one less component giving us \(k-1\).

Answer 23

So find all even \(k-1\) part compositions for \(n-1\), and then stick a \(1\) in it.
How many places are there to put in the \(1\)? We we can stick it at the front, or behind any of the other numbers in the composition. Thus we have \(1+(k-21) = k\) places to put the \(1\).

Answer 24

So assuming \(f(n,k)\) counts even compositions, use \(f(n,k)+kf(n-1,k-1)\)

Answer 25

Ok, so determined that the number of compositions of n into k parts where each part is even is \[{k+(n/2)-1\choose n/2}\]

Answer 26

so if \[f(n,k)+kf(n−1,k−1)\]

then \[{k+(n/2)-1 \choose n/2}+k{k-1+((n-1)/2)-1 \choose (n-1)/2}\]
would be the solution

Answer 27

You have to worry a bit about whether n is even or not.

Answer 28

n would be even if all the numbers were even so you couldn't use one 1 in the composition

Answer 29

That's all the help I can give you. I don't understand anything about these generating series.

Answer 30

you've been extremely helpful, I've been stuck on this problem for hours and this is the first time it's started making sense. Generating series aren't a requirement of solving these, it's just an algorithmic method. Solving them through logic generally makes them much easier.

Answer 31

could you explain what you meant when you said that I need to worry a bit about whether n is even? Why is that significant?

Answer 32

Because putting 3.5 into a binomial can be troublesome

Answer 33

ok that makes sense I can see where restrictions would be applied to make it work

Answer 34

Honestly, Thank you so much!

Answer 35

Wait, if n is even, you can't put only one 1 in it, because it will give you an odd number.

Answer 36

If n is odd, then you have to use the other method.

Answer 37

What I mean is, if n is odd, you have to do the n-1, k-1 thing,

Answer 38

So, rather than adding them together, maybe each one is a separate answer for each case. That would certainly prevent any .5s making their way into the binomial.

Answer 39

oh that does make a lot of sense. the sum of all even numbers must be even and the sum of all even numbers plus one must be odd

Answer 40

separating them into cases makes way more sense