For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

3
votes
3answers
150 views

What is the number of combinations of the solutions to $a+b+c=7$ in $\mathbb{N}$?

My professor gave me this problem: Find the number of combinations of the integer solutions to the equation $a+b+c=7$ using combinatorics. Thank you. UPDATE Positive solutions
1
vote
2answers
56 views

Finding the probability of a client getting the same token in two consecutive interactions.

I am trying to find the probability in the following real-world inspired scenario. If I have a finite set of whole numbers from 0 to 4 billion which I call tokens and $n$ clients. Each time a client ...
2
votes
3answers
64 views

Why are there 5 groups that contain the 2 enemies?

Suppose I must form a committee of 3 people chosen out of 7. 2 of the 7 are enemies of each other. These 2 people would wreak havoc if they are both chosen to be on the committee. How may ways are ...
1
vote
2answers
114 views

Proof for one of the Lucas problem

Can anybody provide a combinatorial proof or algebraic proof of following identity? $${n\choose 0 }+ {n-1\choose 1}+{n-2\choose 2}+ .. +{{n-\lfloor n/2\rfloor} \choose {\lfloor n/2\rfloor}} = ...
2
votes
2answers
260 views

Number of solutions of $x_1+x_2+x_3+x_4=1000$

How many solutions possible for the equation $x_1+x_2+x_3+x_4=1000$ if all $x_1,x_2,x_3,x_4$ are non-negative integer and $\left| {{x_i} - {x_j}} \right| \in \left\{ {0,1} \right\}\text{ }\forall 1 ...
10
votes
3answers
1k views

In the card game Set, what's the probability of a Set existing in n cards?

Given $n$ randomly drawn Set cards on a table from a standard 81-card deck, how can I determine the probability of one or more Sets existing on the table? First, for those who may not be familiar ...
1
vote
1answer
98 views

Gambler with infinite bankroll reaching his target

Suppose a gambler with infinite bankroll has a target of winning 10 dollars. He wins/loses $\$1$ with probabilities $0.48=p$ and $0.52=q$ respectively. What is the probability that he meets the ...
0
votes
1answer
73 views

There are some $1$ in the$ n\times n$ grid such that the number of $1$ in each row and each column is $K (K<n).$

Prove that I can choose exactly one $\mathbf{1}$ from each row such that for every two of them,they are not in the same column.
2
votes
1answer
80 views

Bounding the number of monovalent vertices in a graph satisfying a certain condition

Show that a graph with exactly one vertex of degree $i$ : $2\le i \le m$ and $k$ other vertices (which are monovalent) satisfies $$\left\lfloor\frac{m+3}2\right\rfloor \le k\;.$$ Here is my ...
5
votes
7answers
4k views

How do I compute binomial coefficients efficiently?

I'm trying to reproduce [Excel's COMBIN function][1] in C#. The number of combinations is as follows, where number = n and number_chosen = k: $${n \choose k} = \frac{n!}{k! (n-k)!}.$$ I can't use ...
1
vote
2answers
77 views

Put some $1$ into an $n\times n$ grid (every check has at most one $1$) such that the number of $1$ in each row and each column is $k \ (<n)$

I want to ask if I can find a $1$ from each row such that for every two of $1$ they are not in the same column.
1
vote
3answers
436 views

Finding the coefficient of a geometric series

I've been asked to compute $[x^n]\frac{1}{(1-2x)(1+3x^2)}$ where $[x^n]$ is the coefficient of the series. I've recognized that it is a geometric series, and have been able to put it into this ...
6
votes
0answers
157 views

Calculating $\sum_{y=0}^x \Pr[Y= y] \Pr[Z\leq k-y]^2$ when Y,Z are binomially distributed?

Remark: I recently rewrote this post, hoping to get answers! I am analyzing the following experiment: Pick an $x \in \{0,\ldots,2k\}$ uniformly at random Pick $(2k+1)$-bit bitstring $b_1=(u,v_1)$ ...
1
vote
1answer
327 views

Equal scores in a round-robin tournament implies wins=losses?

Suppose you have a round robin tournament with $n$ teams where each team get in every single 1-1 match: $3$ points for a win, $1$ point for a tie, $0$ points for a loss. I would like to decide ...
2
votes
3answers
240 views

Arrange n black and 4 white marbles

I have this question that I can't seem to wrap my brain around. It goes something like this. How many ways are there to arrange n black and 4 white marbles so that every white marble is adjacent to at ...
1
vote
1answer
60 views

Lower bound of a series

I want to find a lower bound of the following $$\sum_{i=0}^{100000}\left|\sum_{j=0}^i (-1)^j \binom{167}{j}\binom{99833}{i-j}\right|.$$ Will you kindly give some way?
1
vote
1answer
127 views

Combinations of resistor networks?

I formulated this question while thinking about resistor networks. Suppose you are given N distinct resistors. How many ways are there to combine them into a resistor network? A resistor network is ...
4
votes
2answers
218 views

center of mass of triangle

We arbitrarily choose n lattice points in a 3-dimensional Euclidean space such that no three points are on the same line. What is the least n in order to guarantee that there must be three points x, ...
3
votes
1answer
94 views

Possible Bijection? Counting Problem

I tend to struggle in counting because I just am not that insightful so I was wondering if someone could help me with a counting problem that I found in a book from Art of Problem Solving. Also, there ...
1
vote
2answers
953 views

If two members refuse to be on the same team, how many teams are possible?

An engineering group consists of 12 men and 13 women. If 2 women refuse to be on the same team together, how many different project teams can be formed consisting of 5 men and 5 women?
3
votes
1answer
57 views

What are the chances that a particular suit shows up at least once in the first two cards?

A standard deck of 52 cards. It seems obvious that the probability of getting a particular suit (say diamonds) on the first try is 13/52. After that, if we do not get diamonds, our chances are 13/51. ...
2
votes
2answers
233 views

How many ways can a television producer air commercials…

A television director has to schedule commercials during 6 time slots. There are four distinct commercials, A, B, C, and D. A must be aired three times but never twice consecutively. How many ways ...
2
votes
1answer
169 views

Count the number of solutions of the inequality $a+b+c+d=n$, $a \geq b \geq c \geq d \geq 0$.

How would I count the number of integer solutions to: $a+b+c+d=n$, $a \geq b \geq c \geq d \geq 0$. Thanks for your help!
2
votes
2answers
108 views

Combinatorial (non-algebraic) Proof: $ {}_{n}C_{4}={}_{n-1}C_{3}$ +${}_{n-2}C_{3} +{}_{n-3}C_{3} + \cdots + {}_{3}C_{3} $

Show $ {}_{n}C_{4}={}_{n-1}C_{3}$ +${}_{n-2}C_{3} +{}_{n-3}C_{3} + \cdots + {}_{3}C_{3} $ where: ${}_{n}C_{i}$ is the number of ways of choosing $i$ elements from $n$ -I've been explicitly requested ...
1
vote
1answer
71 views

Deducing a list of natural numbers from the list of sums

Let $S$ be a list of k natural numbers (including 0). Let $S'$ be another such list. Each such list gives way to a list of $2^k$ sums of its members. Can $S$ be recovered if I'm given the list of ...
3
votes
0answers
1k views

How many different ways are there to get the same product from a sequence of integers?

Let's say we have a list of integers from 0 to (n-1), where n > 0: 0, 1, 2, 3, 4, ..., ...
1
vote
1answer
63 views

sampling with replacement (choosing 6 items from a set of 4 elements)

I'm having trouble finding the number of $6$ ordered letter sequences from a $4$-set (i.e. $\{a, b, c, d\}$), that contain at least one of each different letter. Should it be $4\times 4\times 4!$ ...
3
votes
1answer
196 views

Sufficient and Necessary Conditions for A(X)Q(X)=P(X)

I am given two formal power series. $$ P(X) = \sum_{n \ge r} p_nx^n $$ $$ Q(X) = \sum_{n \ge s} q_nx^n $$ With the conditions that $p_r \ne 0$ and $q_s \ne 0$ I'm looking for a necessary and ...
1
vote
3answers
171 views

A card counting problem in which order matters

I can't seem to figure out the correct solution to this problem I'm having. Out of a deck of 40 cards, 4 are selected. What is the probability that the third card is the first ace chosen? Note that ...
16
votes
4answers
425 views

Prove that $n! \equiv \sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k+r)^{n} $

Basically I had some fun doing this: 0 1 1 6 7 6 8 12 19 6 27 18 37 6 64 24 61 125 etc. starting with ...
1
vote
1answer
59 views

Noise sensitivity of Boolean functions

Is there any Boolean function from $\{-1,1\}^n$ to $\{-1,1\}$ such that whose noise sensitivity is greater than delta, where Delta is the probability of each bit is flipped in n-tupple.
1
vote
1answer
82 views

List number of moves to defeat the opponent

Given the position of chess board of two players, we have to find the minimum number of moves (and output them) so that only one player playing continuously and optimally defeat the other one ...
2
votes
2answers
581 views

In how many ways one can answer a 20-question exam with two-choice questions?

There is a problem in my book: In how many ways one can answer a 20-question exam with two-choice questions? which I would solve as follows: Since there are 20 questions, and each question has ...
4
votes
1answer
71 views

A harder tournament to schedule

Let us suppose that I have $n$ students in my class, and I break them up into $k$ groups per week. Let's also suppose that I want to repeat this each week, except that I don't want any student to ...
1
vote
0answers
33 views

How many different sets of groups can be formed so that nobody ever has the same group mates? [duplicate]

Possible Duplicate: Equal sized partitions without overlap There are 24 students in the class and I will divide them into 8 groups with 3 people in each group. In how many different ways ...
1
vote
2answers
68 views

Counting Question involving cards

I'm preparing for an exam in my stats class and there's a question that I can't seem to get the right answer to. The question says that from a deck of 40 cards (10 suits A-10), 4 are chosen randomly. ...
4
votes
3answers
591 views

How to divide currency?

Are we really making the right coins from a mathematical point of view? Is a penny,a nickel, a dime a quarter and 1,5,10,20,50 and 100 dollars bills the optimal configuration? Or is there a better ...
10
votes
5answers
376 views

What is the coefficient of the $x^3$ term in the expansion of $(x^2+x-5)^7$ (See details)?

I fail to see a simple way to answer this. As such, this is my long winded approach: Using the multinomial theorem, $$(x_1 + x_2 + \cdots + x_m)^n = \sum_{k_1+k_2+\cdots+k_m=n} {n \choose k_1, ...
3
votes
2answers
131 views

Arrangement Question

I'm trying to represent the number of ways to arrange n blue and 4 red balls whose colors are indistinguishable I've come up with, $${{n+4} \choose 4}$$ but I'm not sure how it works... How come I ...
2
votes
2answers
758 views

the number of non-empty subsets

What is the number of non-empty subsets from the set $ (1,2,3,...,12)$ and such that the sum of the least element and the greatest element in the set is equal to $13$
2
votes
1answer
89 views

completely polarized polynomial

Let $A$ be a $(r \times r)$-matrix. From the equation$$ \det\left(1+A\right)=\sum_{0\leq j \leq r} {r \choose j} H_j (A) $$ where $H_j (A)$ are homogenous polynomials of order $j$ in the entries of ...
1
vote
2answers
1k views

Combinatorial proof of an identity [duplicate]

Possible Duplicate: Combinatorially prove something I have to give a combinatorial proof of the identity: $$\sum_{i=0}^{n}{\binom{n}{i}}{2^i}=3^n$$ I can use prove it using the binomial ...
0
votes
1answer
137 views

Generating Function for number of triangulations

I'm currently working through Analytic Combinatorics (free online) and i'm stuck at a very interesting example. After introducing some admissible constructions (combinatorial sum, cartesian product, ...
1
vote
1answer
379 views

Maximize distance between points on a line

So lets say I have a certain duration of time starting at time(0) ranging to time(N). I also have a set of points whose values all exist within the range of values of that time frame. I want to pick ...
6
votes
7answers
384 views

Find the coefficient of $\sqrt{3}$ in $(1+\sqrt{3})^7$?

I just want to ask you if my solution is correct. Here's the problem, Using the Binomial Theorem, find the coefficient of $\sqrt{3}$ in $(1+\sqrt{3})^7$. Solution: The binomial theorem is, ...
2
votes
0answers
317 views

Multinomial Theorem, distinct objects to identical boxes?

sorry I'm not sure if the title of my question would best describe this problem. Well, I tried to solve the problem below, but not sure with my answer. Here's the question, In how many ways can nine ...
4
votes
3answers
191 views

Sum over subsets

I feel silly asking this as I should be able to work it out, but combinatorics are my enemy. Consider a collection $x_1, \ldots, x_n$ of real numbers and denote their sum by $s = x_1 + \ldots + x_n$. ...
6
votes
3answers
180 views

What is $\lim\limits_{n\to\infty} \frac{n^d}{ {n+d \choose d} }$?

What is $\lim\limits_{n\to\infty} \frac{n^d}{ {n+d \choose d} }$ in terms of $d$? Does the limit exist? Is there a simple upper bound interms of $d$?
3
votes
1answer
126 views

Square covered with tiles

A square $666\times666$ has been covered using tiles $5\times1$. A single square $1\times 1$ hasn't been covered. Find in how many places the not covered square can be.
2
votes
2answers
270 views

Chess combination

On the chess board 8x8, we have 8 Rooks that , each Rook don't atack the other. How many situation if we give out: a) 1 main diagonal b) 2 main diagonals That's mean we can't put the Rook to the ...