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)

0
votes
0answers
20 views

Number of ways to get from top to left through a blocked Grid

There is a Grid and a guy , guy can move either down or right in a Grid as shown from starting point (1,1). Let the Grid Dimensions be N x M . (The length of Grid x The Breadth of Grid) (Guy can ...
3
votes
1answer
170 views

Lengths of the shortest “simple” equation, that use only the number '1', equal to a given natural numbers.

Is there a formula, for determining the length of the shortest formula, that uses only the number '1', parenthesis, and the hyperoperations $\{\{+, - \}, \{\times, / \}, \{\text{^}, \log_N,\text{nth ...
1
vote
2answers
44 views

Ways of coloring the $7\times1$ grid (with three colors)

Hints only please! A $7 \times 1$ board is completely covered by $m \times 1$ tiles without overlap; each tile may cover any number of consecutive squares, and each tile lies completely on the ...
0
votes
2answers
27 views

Can we obtain the pair $(1,50)$ with these following operations?

It's a problem from some russian competition: We're given a card with two positive integers $(a,b)$ and we have tree machines which generate another card from the one we insert on it(I assume we ...
2
votes
0answers
21 views

An easy (or not?) collection of proper sets .

Let $S$ be a finite set. We are given $k$ rows and in each row we have two subsets of $S$ which we call them $A_i$, $B_i$ (for the $i$th row, with $i\leq k$). $A_1$ and $B_1$ $A_2$ and $B_2$ . . ...
0
votes
1answer
35 views

Why is $^nC_r$ not equal to $ ^{n-k}C_{r-k}\times ^nC_k$?

Why is $^nC_r$ not equal to $ ^{n-k}C_{r-k}\times ^nC_k$ ? I know that by simplifying, we can obviously see that they are unequal. But consider this: Where am I going wrong?
4
votes
0answers
59 views

If $G$ is shellable, then $G \backslash \{x_i\}$ is shellable?

A simplicial complex $\Delta$ on the vertex set $\{x_1,\dots,x_n\}$ is shellable if the facets of $\Delta$ can be ordered, say $F_ 1 , . . . , F _s$, such that for all $1 \leq i < j ...
9
votes
1answer
169 views
+100

Help with binomial identity

In my work, I was led to the following identity. I would be grateful if someone could provide an easy proof. Suppose $n, d, k \in \mathbb{Z}$, and $d \geq 0$. $$ \sum_{j = 0}^d (-1)^{d-j} \cdot ...
-1
votes
1answer
18 views

How many structurally different latin squares of order 5 do exist?

I know the number of latin squares order 5 which start with 1 2 3 4 5 in the 1st row or column, that is 1344, but the greater part of that number consists of structural duplicates of each other. So, I ...
3
votes
1answer
36 views

Permutations of n objects taken r at a time ( r=1 to r=n ) where objects may be groups of same entities and it's sum

Given n objects where n1 objects are the same ,along with another group of n2 objects of same element etc.. such that Σni = n (i=1 to k). Assuming there are k groups of similar objects eg: in ...
0
votes
2answers
65 views

Counting combinations with a restriction of the form “either … or …, but not both”

The following is the problem that I am dealing with. There are 9 people in a class and 4 of them is randomly chosen to form a committee. Jack and Nick are 2 of the 9 people in the class. How ...
5
votes
2answers
112 views

When does this sum of combinatorial coefficients equal zero?

$p>2$ is a prime number, $n\in \mathbb{N}$. Is the following statement true or false? Thanks. $$\sum_{i=0}^{\lfloor n/p\rfloor}(-1)^i {n\choose ip}=0$$ iff $n=(2k-1)p$ for some $k\in \mathbb{N}$.
3
votes
2answers
91 views

Algebraic proof that $\sum\limits_{i=0}^n \binom{i}{k} = \binom{n + 1}{k + 1}$

I'm looking for an algebraic proof of this identity for $n, k \in \mathbb{N}$: $$\sum\limits_{i=0}^n \binom{i}{k} = \binom{n + 1}{k + 1}$$ So far, I've turned the left hand side of the equality into ...
3
votes
2answers
131 views

Properties of a sequence of sums of binomials

I have encountered the following sequence of alternating sums of binomials and I am wondering whether there is a nicer way to write every element and/or are there some nice properties about it. So, if ...
5
votes
0answers
21 views

Partition Of Graph's edges Into 3 Groups

Let $G = (V, E)$ be a bipartite graph. Prove that there is a partition of the set of edges $E$ into 3 disjoint parts: $E = E1 ∪ E2 ∪ E3$, $E1 ∩ E2 = E2 ∩ E3 = E3 ∩ E1 = ∅$, so that for ...
4
votes
3answers
104 views

Showing ${n + a - 1 \choose a - 1} = \sum_{k = 0}^{\left\lfloor n/2 \right\rfloor} {a \choose n-2k}{k+a-1 \choose a-1}$

Prove that for integers $n \geq 0$ and $a \geq 1$, $${n + a - 1 \choose a - 1} = \sum_{k = 0}^{\left\lfloor n/2 \right\rfloor} {a \choose n-2k}{k+a-1 \choose a-1}.$$ I figured I'd post this question, ...
4
votes
1answer
100 views

How many different sums of parts of a vector

The following mathematical puzzle was given to me by a friend a while ago and I can't work out how to solve it. Does anyone have any ideas? For a given vector $v \in \{-1,1\}^n$ we consider the ...
3
votes
2answers
41 views

Permutation count of AABBC

Given a string: $AABBC=A^2B^2C^1$ I am trying to find the Total Permutations (this may be incorrect): $\dfrac{5!}{2!\cdot2!}=30$ My question is how would I find the partial sums (perhaps the ...
2
votes
1answer
36 views

How many 3 letter words can you form from 'EEAAP' [duplicate]

How many 3 letter words can you form from 'EEAAP' I think the answer is ${3\choose 3} * 3! + {2\choose 1} * 3 + {2\choose 1} *3=18$. Is this right? ${3\choose 3} * 3!$ = You pick all ...
3
votes
1answer
27 views

Probability of the card following first ace being ace of spades or two of clubs

I am learning probability from Scheldon Ross' book. The question reads like this: A deck of 52 playing cards is shuffled, and the cards are turned up one at a time until the first ace appears. Is ...
2
votes
0answers
38 views

How many ways can you choose team of 5 people out of 7 men and 6 women in which there are at least 3 men?

I am confused by this question. I solved it by selecting 3 men first out of 7 men and then selecting 2 people out of 10 remaining person ( 4 men and 6 women ) . So my answer is C(7,3) * C(10,2) = ...
0
votes
2answers
35 views

Probability and Combinatorics

I am trying to solve example 4.15 here but think the total number of outcomes in the solution is incorrect. This is my reasoning. We have 3 that qualify as best three, say BBB, and 2 as bad say OO. ...
3
votes
2answers
50 views

Permutations minus Transpositions

I want a formula that allows me to find all the permutations in $S_n$ (which is the set of all the integers from 1 to $n$) which don't contain a transposition. Attempt: Lets call $g(n)$ the ...
0
votes
1answer
16 views

A succinct proof that the given graphs (red $K_n$ drawn cyclically, plus blue $2$-paths between closest vertices) have dihedral automorphism groups?

Take the complete graph $K_n$ ($n \geq 3$), on the red-colored vertex set $\mathbb{Z}_n$, say, and add a blue-colored $2$-path between each pair of vertices $v$, and $v+1$, we get a sequence of graphs ...
1
vote
0answers
15 views

Representing numbers by quasilexicographic ordered strings, formula for size of conversion between different alphabets

Let $X_r = \{ 0, 1, \ldots, r-1 \}$ and $X_b = \{ 0, 1, \ldots, b-1 \}$ be two finite alphabets with order's given by their numerical value. Consider the quasilexicographic (or shortlex) order on ...
2
votes
0answers
29 views

Probability of a run of *k* or more of a subset of categories in *m* multinoulli trials?

Given a multinoulli distribution of categories $(C_1,C_2,...,C_n)$ with associated probabilities $\left\{p_1,p_2,\ldots ,p_n\right\}$ with $\sum _{i=1}^n p_i=1$, is there a tractable way to get the ...
0
votes
0answers
58 views

Zero-Sum Partitions of Nonzero Elements of a Ring

In this question, rings are not necessarily finite nor do they need to be unital (i.e., the multiplicative identity may not exist). Although I shall exclusively discuss finite commutative unital ...
1
vote
0answers
30 views

Number of different keyboard layouts?

Pretty really stupid question probably, but if I would have a keyboard with the 30 main keys (A-Z,. shift) in how many different keyboard arrangements could I put them provided their possible ...
1
vote
1answer
27 views

Diagonalizing a matrix arising in a simple combinatorial situation

Maybe I'll return to this question a few hours from now and possibly even post an answer then. This concerns a matrix that I described in this answer. Start with a $\dbinom n2\times n$ matrix $B$ ...
3
votes
2answers
77 views

Combinatoric Birthday Paradox

There is likely a closed form solution for this problem but it's had me puzzled for days. This is about a variant on the classic birthday paradox. To recap, the birthday paradox is where given only 23 ...
1
vote
2answers
54 views

How many two letter words can be formed from 26 English letters?

There are 26 English letters. From layman approach, How can one calculate the possible two letter words from these 26 English letters?
0
votes
3answers
52 views

Evaluate: binomial theorem

Show: $$(x+1)^m=\sum_{k=1}^{m}\binom{m}{k}x^k$$ Can somebody help me in showing the above stated problem?
6
votes
1answer
162 views

Partition rectangle into finite number of squares

For what positive real numbers $x,y$ can an $x\times y$ rectangle be partitioned into a finite number of squares? When $\dfrac{x}{y}$ is a rational number, it is not hard to see that we can partition ...
2
votes
3answers
69 views

probability of $k$ boxes contain exactly $1$ ball

Occupancy problem with balls and boxes. Suppose there are $N$ balls and $M$ boxes. The balls are thrown to the boxes at random. What is the probability of $k$ boxes contain exactly $1$ ball? where ...
0
votes
0answers
25 views

Why $|N(P_{i, j})| \cong [0, 1]^n$ as stated in page 21 of HTT?

maybe this is an idiot question, however I could not solve this after thinking for a while. I added the tag about higher categories simply because of the nature of the question, however this is just a ...
2
votes
5answers
1k views

Hot dog combinatorics

A hot dog stand has 12 different toppings available. How many different kinds of hot dogs can be made, assuming the order of the toppings does not make a difference. I believe the correct answer is ...
3
votes
2answers
296 views

Arrangements in groups

In a book I had read The number of ways in which n different things can be arranged in r different groups is $n!\dbinom{n-1}{r-1}$ Question 1. So I had interpreted it like this First n things ...
0
votes
2answers
28 views

Why is this counting function finite? (It is used Probability)

Why is this counting function finite? I don't understand this interpretation of the author. Can you explain more about this? Please.
0
votes
1answer
47 views

The number of ways of going up 7 steps …

The number of ways of going up 7 steps if we take one or two steps at a time is ? So its essentially asking in how many ways can we make use of numbers of (1,2) to get a sum of 7.
0
votes
2answers
54 views

How many permutations of the word TOMORROW can be made if the O's can't be together?

I'm trying to answer this question. This is my attempt of solution: First we distiguish the O's and R's, then we have the word: $TO_1MO_2R_1R_2O_3W$. We have $8!-7!\cdot3!-6!\cdot 3!$ different ...
4
votes
1answer
143 views
+50

Cover the grid graph with simple cycles

I have a two dimensional n x m grid graph. And I want to find in how many ways this grid can be covered with simple cycles (it can be a one cycle or it can be many ...
1
vote
0answers
53 views

Is it possible to solve sudoku without backtracking?

I occasionally solve sudoku puzzles on smartphone in spare time. My approach is based on the belief that at each stage in solving a sudoku puzzle there is at least one cell where there in only one ...
2
votes
1answer
30 views

Reference for a combinatorial theorem

Is there a reference for this theorem https://en.wikipedia.org/wiki/Schur%27s_theorem#Combinatorics? I am unable to locate a reference. Google search does not spot this particular theorem well.
4
votes
2answers
166 views

How to calculate the number of integer solution of a linear equation with constraints?

If an equation is given like this , $$x_1+x_2+...x_i+...x_n = S$$ and for each $x_i$ a constraint $$0\le x_i \le L_i$$ How do we calculate the number of Integer solutions to this problem?
0
votes
2answers
58 views

Combinatorics - how many possibilities

How many possibilities do we have to solve this equation? all variables are natural numbers. $a$ is an odd number. $a + b + c + d + e = 10$
1
vote
0answers
51 views

Permutation of numbers from multiple sets [May contain duplicate numbers among other sets], resulting in Non-Duplicate Set

We have 3 Data Sets. From each set we will be selecting few numbers. 3 from Set 1, 2 from Set 2, 3 from Set 3. Totally, we will get 8 Numbers from 3 Sets. The resulting sets shouldn't contain any ...
1
vote
1answer
31 views

A question on arithmetic progressions

Is it true that for every $n \in \mathbb N$ , $\exists N \in \mathbb N$ such that for any subset $A \subseteq \{1,2,...,N\}$ , either $A$ or $\{1,2,..,N\} \setminus A$ contains an arithmetic ...
2
votes
1answer
98 views

Smallest string which contains all $27$ combinations of $1$, $2$, and $3$ as substrings

What is the smallest string of $1$s, $2$s and $3$s such that it contains each of $27$ substrings of $1$s $2$s and $3$s (repetitions included)?
3
votes
3answers
35 views

Combinatorics Question - Permutations and Supersets

I had a question that seems pretty straightforward, but I can't seem to wrap my mind around it. Let's say I have a bunch of elements in a set. {A, B, C, D, E}. How many permutations are there of ...
6
votes
5answers
137 views

Show that $(1+p/n)^n$ is a Cauchy sequence for arbitrary $p$

It is a generalization of this question. I am looking for a similar derivation as in here. Can we prove that $(1+p/n)^n$ is a Cauchy sequence for any $p \in [a, b]$ by showing that $$ \Bigg| \left( ...