Alternative way of writing the stars and bars formula where each bar is associated with at least one

logiski9s 2022-07-08 Answered
Alternative way of writing the stars and bars formula where each bar is associated with at least one star.
I was looking for a different way of writing the formula of the number of different k-tuples of non-negative integers whose sum is equal to n and I thought of this formula followed by this combinatorial proof:
i = 1 k ( n + 1 i ) ( k 1 i 1 )
The first combination is the number of positions that we can choose from to place the bars. There are n + 1 positions to choose from, since now we can also place the bars before and after the stars. The next combination is the number of different ways of splitting the stars between the positions that were chosen for the bars to be placed.
Lastly, we'll have to add all the different ways of combinations of bar positions and number of bars in each position. I haven't found a flaw in my proof yet but I can't seem to conclude that the above formula is equal to
( n + k 1 k 1 )
Could someone more experienced verify my proof or show me where the flaw is?
You can still ask an expert for help

Want to know more about Discrete math?

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

Kiana Cantu
Answered 2022-07-09 Author has 22 answers
Step 1
Your formula and argument are incorrect, but they can both be made correct with a small change. The correct formula is i = 1 n + 1 ( n + 1 i ) ( k 2 i 1 )
The idea is this; once you have chosen the i spaces out of n + 1 which will receive bars, you now need to split the k 1 bars into i non-empty groups. This can be done in ( k 2 i 1 ) ways; if we now imagine a line of k 1 bars, with k 2 spaces between them, then such a partition is uniquely chosen by selecting a subset of i 1 spaces, and splitting at those spaces.
Step 2
This combinatorial proof establishes the fact that
i = 1 n + 1 ( n + 1 i ) ( k 2 i 1 ) = ( n + k 1 k 1 )
It is easy to give an alternative proof of this by rewriting ( k 2 i 1 ) as ( k 2 k 1 i ) , and applying Vandermonde's identity.

We have step-by-step solutions for your answer!

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2020-11-09
Use proof by Contradiction to prove that the sum of an irrational number and a rational number is irrational.
asked 2021-08-15
How many elements are in the set { 0, { { 0 } }?
asked 2021-08-02
Suppose that A is the set of sophomores at your school and B is the set of students in discrete mathematics at your school. Express each of these sets in terms of A and B.
a) the set of sophomores taking discrete mathematics in your school
b) the set of sophomores at your school who are not taking discrete mathematics
c) the set of students at your school who either are sophomores or are taking discrete mathematics
Use these symbols:
asked 2021-07-28

Let A, B, and C be sets. Show that (AB)C=(AC)(BC)
image

asked 2022-07-10
Is there an algorithm to define a recursive function such that consecutive terms approach any arbitrary constant?
The Fibonacci sequence is defined by the recursive function, f ( n ) = f ( n 1 ) + f ( n 2 ). Consecutive terms in this sequence approach the constant, 1 + 5 2 . Is there an algorithm that produces recursive functions such that f ( n ) / f ( n 1 ) approaches any arbitrary algebraic constant?
asked 2022-08-18
2 points) Page Turner loves discrete mathematics. She has 8 ''graph theory'' books, 6 books about combinatorics, and 4 ''set theory'' books.
How many ways can she place her discrete mathematics books on the same shelf in a row if:
a) there are no restrictions.
b) graph theory books are next to each other but the others could be anywhere on the shelf.
c) books are organized by their topic (same kinds are next to each other).
asked 2022-07-09
Multiplicative inverse of [ 9 ] 23
I'm new to modular arithmetic and this has been very confusing for me. I know that in order for an element [ a ] m to be invertible, the GCD of (a,m) has to be 1.
I have the element [ 9 ] 23 .
Now, the GCD of those two numbers is 1. We form the Diophantine equation
9 x + 23 y = 1 ,, and after performing the extended Euclidean algorithm we have that 1 = 2 23 5 9 which is true. The solution for x is x = λ 1 b + t a 2 where λ 1 is the first coefficient in the euclidean algorithm and equal to 2, b is the right side of the equation 1, and a 2 is the second coefficient in the equation, which is 23.
This gives me x = 2 + 23 t for any integer t.
I need to look for the typical represent, so x [ 0 , 23 ]. We can achieve this by plugging t = 0, and thus x = 2.
However, [ 9 ] 23 [ 2 ] 23 [ 1 ] 23 .
Where did I go wrong? The only thing my workbook did different was they switched the places in the euclidean algorithm 1 = 5 9 + 2 23 which gave them a solution that checks out. They got x = 5 + 23 t, and for t = 1 they got x = 18, which is the multiplicative inverse.
This made me curious where I went wrong. In my mind, the only thing I did differently was switch the places of the two operands in the euclidean algorithm.

New questions

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question