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)

4
votes
1answer
136 views

Congruences and pigeons

The question is this: Given $n$ integers, $(a_1, \dotsc, a_n)$, show that there is some subset $B\subseteq \{1,\dotsc, n\}$, such that $$\sum_{i\in B}i \equiv 0 \bmod n.$$ It looks likes this ...
0
votes
0answers
21 views

Hypothesis on mixed area

Let's consider polygons which are obtained from right-angled triangle with equal legs by deleting a convex polygon, one of the edges of which is the hypotenuse of the triangle (see the picture below). ...
2
votes
1answer
142 views

Proof with combinatorial argument

Show with combinatorial argument that this is equal : $$\dbinom{n}{k+1} = \dbinom{n-1}{k}+ \dbinom{n-2}{k} +...+ \dbinom{k}{k}$$ I have no idea how to do that so it would be really helpful ...
-1
votes
1answer
32 views

Number of ways to order a set of interdependent tasks

I am aware that this question has been asked and answered before here. (Combinatorics/Task Dependency) I'd like some help understanding a part of the answer. Consider the graph shown there: ...
1
vote
2answers
72 views

Combination Transversion

Suppose we have a lottery, consisting of 5 balls. The range of balls is 1-39. In any given pick, there will be no duplicate values, and the order need not matter. The upper limit of combinatorial ...
0
votes
2answers
43 views

Placing Objects: Englishman,French, Turkis

in how many ways can you place 6 english, 7 french and 10 turkish men in a line so that each englishman is between a french me and a turkish, and no french men is next to a turkish man.
1
vote
1answer
475 views

How many nonnegative integer solutions are there to the pair of equations $x_1+x_2+…+x_6=20$ and $x_1+x_2+x_3=7$?

How many nonnegative integer solutions are there to the pair of equations \begin{align}x_1+x_2+\dots +x_6&=20 \\ x_1+x_2+x_3&=7\end{align} How do you find non-negative integer solutions?
2
votes
1answer
45 views

Showing equivalence of two binomial expressions

I wish to show that $\sum_{k=0}^n {n\choose k}(\alpha + k)^k (\beta + n - k)^{(n-k)} = \sum_{k=0}^n {n\choose k}(\gamma + k)^k (\delta + n - k)^{(n-k)}$ given that $\alpha + \beta = \gamma + \delta$. ...
0
votes
1answer
46 views

n lines cut a plane into at least (n+1)(n+2)n/3 regions.

If a group of lines is in basic position, it means that there isn't a pair of parallel lines and each three don't intersect in a single point. A group of $n$ lines in basic position chop the plane ...
2
votes
1answer
121 views

1-Associated Stirling Number of the Second Kind identity verification

I recently posted this in regards to Associated Stirling Numbers of the Second Kind (SNSK) and I was trying to fix my equations to find and identity, and am now looking for verification that this ...
19
votes
2answers
505 views

Maximizing curious symmetric function from simple combinatorics

A curious symmetric function crossed my way in some quantum mechanics calculations, and I'm interested its maximum value (for which I do have a conjecture). (This question has been posted at ...
0
votes
2answers
42 views

10 objects are purely randomly assigned to 10 places - Number of arrangements

Quick and dirty: 10 objects are purely randomly assigned to 10 places. What is the number of possible arrangements? The answer: $19\choose{10}$ But this seems counterintuitive. Might someone shed ...
1
vote
1answer
70 views

Is there an error-correcting code where almost every word could be used as a codeword?

An error-correcting code for strings of length $n$ from a $K$ letter alphabet is a partition $\Pi$ of $K^n$ together with a choice function $\pi$ on $\Pi$. Let $A_i$ for $i<M$ enumerate $\Pi$, and ...
0
votes
1answer
67 views

Probability about balls and urns

$b$ balls are randomly placed in $b$ urns. What is the probability that exactly one urn is empty? I started studying Probability yesterday and a few doubts came out: a) should I consider balls and ...
1
vote
1answer
36 views

Why does the following formula cycle the bits by shifting the binary representation from left to right?

Intuitively, I was trying to come up with a formula that would cycle through the binary representation of numbers from left to right. Let our range of numbers goes from $0, .., N-1$ and let $m$ ...
3
votes
1answer
92 views

Associated Stirling Number of the Second Kind summation

A Norlund polynomial $B_n^{(z)}$ is defined by $$\sum_{n=0}^\infty B_n^{(z)}\frac{x^n}{n!}=\left(\frac{x}{e^x-1}\right)^z$$ and the $B_n^{(z)}$ is called a Bernoulli number of order $z$. We also have ...
0
votes
1answer
16 views

Set theory, injection's existence

Let $A^B$ be the set of all functions from $B$ to $A$, and $A \precsim B$ denotes the existence of an injection from $A$ to $B$. I need to prove that if the $ B \precsim C$ exists, so the $B^A ...
7
votes
5answers
474 views

Choice Problem: choose 5 days in a month, consecutive days are forbidden [duplicate]

I'm "walking" through the book "A walk through combinatorics" and stumbled on an example I don't understand. Example 3.19. A medical student has to work in a hospital for five days in January. ...
0
votes
2answers
26 views

divding numbers from 1 to 100 into sets

if sets are created using this rule $a \times 2^m$ where $a$ is an odd number e.g $a=1 {1,2,4,8,16,32,64}$ $a=3 {3,6,12,24,48,96}$ $a=99 {99}$ hence there are $50$ such sets. Will every ...
1
vote
1answer
101 views

Find a Recurrence Relation

I want to find a recurrence relation for number of decimal numbers with length n, (we called $a_0$ ) that not includes 0 and any combination of 11,12, 21. i see the result is: ...
1
vote
1answer
65 views

Number of answers of equation amongs odd natural numbers

How many answer The following Equation has, in set of odd natural numbers? $x_1+x_2+...+x_k=n$, $k \equiv^2 n$ Solution: Comb ( [(n+k)/2]-1, k-1), comb means combination. how we get this?
-2
votes
0answers
28 views

Solving a problem [closed]

Kelly is having a birthday party soon, and would like to invite all her friends to come. There is one problem though: her house is far too small to accommodate everyone! She has already written up ...
2
votes
4answers
372 views

Proving $ \binom n 0 ^2 + \binom n 1 ^2 + \dots + \binom n n ^2 = \binom { 2n} n $ without induction [duplicate]

I have to prove that: $$ \binom n 0 ^2 + \binom n 1 ^2 + \dots + \binom n n ^2 = \binom { 2n} n $$ I don't want a complete solution, but only a hint.
0
votes
1answer
66 views

A double sum with binomial coefficient

I'm trying to compute the double sum : $$ \sum_{1\leq i\leq j\leq n, \ i+j\leq n }\begin{pmatrix}i+j\\ i\end{pmatrix}x^i y^j $$ where $(x,y) \in \mathbb{R}^2$ ( Though it is not mentionned in the ...
3
votes
3answers
54 views

Determine the constant (that is, the coefficient of $x^0$) in $ (3x^2 - \frac{2}{x})^{15}$

I've been doing coefficient extractions for a bit but I've hit a stump. I've tried changing around the formula but just can't get it. This is what I've tried so far: $$ (3x^2 - ...
1
vote
1answer
37 views

Number of different vectors.

Let's say that I have a vector with 6 elements. I put two wedges in the vector, i.e., at position 2 and position 6, for instance. And when I say put a wedge, it means... for every time you traverse ...
1
vote
1answer
70 views

Perfect Coverings

This is a problem from Brualdi and no solution is given for this. The Question goes as .... Let g(n) be the number of different perfect covers of a 3-by-n chessboard by dominoes. Evaluate g(6). I ...
1
vote
1answer
45 views

colored grid with no repeated rows problem

suppose we are given an $n+1\times n+1$ square grid colored with black and white such that none of its rows are the same. Prove you can select a row and a column, and paint both of them blue so there ...
1
vote
2answers
105 views

The probability that 7 people taking an elevator will leave it in configuration 3-2-1-1

I'm learning some probability and i'm doing some additional tasks, unfortunately without hints or answers. Task: We have 7 people in the elevator in 10 level building. They are leaving the ...
0
votes
1answer
62 views

Large Family of Subsets with small overlap

Find upper and lower bounds on the cardinality of the largest family of subsets of an $n $ element set, $\mathcal{S}\subset \mathcal{P}(\{1,\dots ,n\})$ , if no pair of elements contain a third ...
1
vote
1answer
28 views

Logic behind rule of product solution for a question

Im working through a book of Discrete and combinatorial mathematics and there is one question that I answered correct, however the solution in the book is very different (and it seems far more ...
4
votes
0answers
49 views

Probabilistic counting inequality

I am reading a proof involving the existence of a property in a tournament (a directed complete graph). To make the proof work, we need to have $n^ke^{-n/2^k}<1$. Here $n$ is the order of the ...
0
votes
2answers
99 views

Number of ways to split 10 items into groups of 5 and 3 and 2

There are 10 people, you want to split them into groups of 5 and 3 and 2. How many combinations are there? I am wondering if the ordering in which you choose the groups matters. For example if I pick ...
2
votes
2answers
83 views

Number of Relatively Prime Factors

Given a number $n$, in how many ways can you choose two factors that are relatively prime to each other (that is, their greatest common divisor is 1)? Also, am I going in the correct direction by ...
1
vote
3answers
210 views

Problem with concepts of circular permutation.

I am having problem in understanding this concept: Circular permutation : The definition in my book goes like that ' Arrangements of things in a circle or a ring are called circular ...
0
votes
3answers
74 views

proving $\sum_{k=0}^{n}k\cdot 2^{n-k}=2^{n+1}$

Is the equation true? $\sum_{k=0}^{n}k\cdot 2^{n-k}=2^{n+1}$ I tried Generating function but didn't get anything. Thanks.
4
votes
4answers
487 views

How to prove this using combinatorics?

How do you proceed if you are required to prove for any natural number $n$ that $$\frac{n^2!}{(n!)^n}$$ is an integer. Here the ! sign represents factorial. I got absolutely no leads on this problem. ...
1
vote
0answers
27 views

Extra information needed to distinguish combinatorially isomorphic polytopes

The title pretty much sums up my question: what extra information do we need (or what is an example of sufficient information) on top of the face lattice in order to completely characterize a convex ...
0
votes
2answers
28 views

Find the probability of a full given that the first 2 cards are the 10 of diamonds and the 10 of hearts

A 5 card hand is dealt from a well-shuffled deck of 52 poker cards. If the first two cards are the 10 of diamonds and the 10 of hearts, what is the probability of having been dealt a full? This is ...
1
vote
1answer
255 views

Palindromic binary words with even or odd amounts of letters

Say you have one bag of apples and one bag of oranges. Each bag contains at least one fruit, and the number of fruit in each bag is an odd number. I have found that it is impossible to line up these ...
-1
votes
1answer
523 views

Use of rook polynomials

Use rook polynomials to count the number of permutations of 1,2,3,4 in which 1 is not in the second position, 2 is not in the fourth position, and 3 is not in the first or fourth position. How do we ...
0
votes
1answer
54 views

Counting Game Question, 2 players

Players A and B play the following game. Two integers, m and n, are written on the board. On each turn, a player selects one of the numbers on the board, erases it, and writes down a positive divisor ...
-2
votes
1answer
27 views

Sequences and ordinary generating functions

Find the ordinary generating function of the sequence <1, -1, 1/2!, -1/3!, 1/4!, ...>. I feel that it's a combination of sin and cosine functions but not sure. Please help.
0
votes
1answer
101 views

Number of ways to make n digit number?

Given M digits which are between 1 to 9, Find the number of ways to form N digit number, by repeating one or more given digits such that each of M digits are present in N digit number at least once. ...
2
votes
0answers
113 views

Game theoretical approach to other branches of mathematics

Are there some methods and ideas derived from game theory that are successfully applied to better (or more intuitively) understand theorems and proofs or tackling problems from other areas of ...
2
votes
3answers
117 views

Bijective Proofs

Give a bijetive proof: The number of subsets [n] equals the number of n-digit binary numbers. I do not understand how to do this problem, can someone help me figure it out? I have this so far, Let ...
2
votes
3answers
158 views

How many strings of $8$ Hs and $8$ Ts are there such that there are at most $2$ consecutive Hs?

How many strings of 8 Hs and 8 Ts are there such that there are at most 2 consecutive Hs? I don't really understand how to approach this question. What would be the quickest way to solve it? Thanks ...
1
vote
2answers
60 views

Back with a harder poker probability problem

Okay, so last time I got help figuring out a simple binomial coefficient misunderstanding. Now I'm trying to figure out what happens if the following scenario occurs: Player $1$ gets a $5$-hand of ...
2
votes
1answer
23 views

Question about poker hand probability

So this is really simple, but can someone shed light on this tiny issue I'm having? ------------ I want to find out how many combinations of cards there are in $5$-hand poker where you get two pair. ...
2
votes
2answers
80 views

Given a number $n \in \Bbb{N}$. In how many ways can $n$ be written as $\prod_{i=1}^{k}n_i$ such that $n1|n2|\ldots|n_k|n$?

I came to this problem in a question a few days ago. I have not found any duplicates so I assume there are none. In fact, the proposed problem is equivalent to "How many abelian groups are there with ...