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
1answer
14 views

Basic doubt on Stirling numbers of Second Type

When learning Stirling numbers of Second Type, one simple doubt came to my mind and posting it here. The formula for Stirling numbers of Second Type is given as ...
0
votes
1answer
59 views

Permutations of the elements of $\mathbb Z_p$

Note Added by Robert Lewis, 2 August 2015 3:04 PM PST in an attempt to provide background, motivation, and other context for this engaging problem: This problem essentially asks for a method of ...
0
votes
2answers
19 views

Probability of picking up one ball of each color

A box contains 6 red, 4 white and 5 black balls. A person draws 4 balls from the box at random. Let P be the probability that among the balls drawn there is at least one ball of each color. Find 455 * ...
0
votes
1answer
30 views

How many combinations in 10x10x10 Rubik's cube?

I was wondering how many possible combinations there is in the cubes greater than 3x3x3 (4x4x4, 5x5x5, ..., 10x10x10)? We know that in 3x3x3 there are about 4,3 * 10^19 combinations, what about bigger ...
-3
votes
0answers
24 views

How many number of substrings of all lengths inclusive can be formed from a string of length n?

Options are A). $\dfrac{n(n-1)}2$ B). $\dfrac{n(n+1)}2$
3
votes
2answers
34 views

Find the least $N$ so there is no square

Find the least positive integer $N$ such that the set of $1000$ consecutive integers beginning with $1000 \cdot N$ contains no square of an integer. Let $x^2$ appear before $1000N$ so: $(x+1)^2 ...
1
vote
2answers
21 views

How many sequences $(i_1,\ldots,i_d)$ of fixed length `d` of positive integers satisfy $\alpha\le i_1+\cdots+i_d\le\beta$?

Let $i\in\mathbb N^d$ and $|i|:=i_1+\cdots+i_n$. How can we calculate the cardinality of the set of all $i$ which satisfy $$\alpha\le|i|\le\beta$$ with given constants $\alpha,\beta\in\mathbb N$?
0
votes
0answers
20 views

Find the constant $k$

In a graph $G$ with $n$ vertices, let $T_1$ be the number of triangles one can make and $T_2$ be the numbers of tetrahedrons. Find the least constant $k$ such that $(T_2)^3\le k.(T_1)^4$.
0
votes
0answers
11 views

Inverse function for a sort of negative binomial distribution

I am trying to find the inverse function of $f(p) = \sum_{k=0}^{6}{\binom{6-H+k}{k} p^{7-H} (1-p)^k}$, where $0 \leq H \leq 6$ is a constant integer. Any ideas on how to do this? Or perhaps equally ...
0
votes
2answers
49 views

How many divisors of the combination of numbers?

Find the number of positive integers that are divisors of at least one of $A=10^{10}, B=15^7, C=18^{11}$ Instead of the PIE formula, I would like to use intuition. $10^{10}$ has $121$ divisors, ...
1
vote
1answer
35 views

How to use Principle of Inclusion-Exclusion here?

A while ago I posted a question: Coloring a Grid. Online, I seem to have stumbled upon a usage of PIE AOPS Wiki Solution AIME II #9. (1) Now, I have experience with PIE, but I do not see how to ...
1
vote
1answer
58 views

Expected Value of a Mosquito

A mosquito is walking at random on the nonnegative number line. She starts at $1$. When she is at $0$, she always takes a step $1$ unit to the right, but, from any positive position on the line, she ...
2
votes
1answer
22 views

Probability a card can win a trick with a trump suit

I'm working on the AI for a card game that uses a standard deck of 52 cards consisting of 13 cards in 4 (spades, clubs, diamonds, hearts) suits. Each player starts with 13 cards in their hand. ...
-1
votes
2answers
44 views

Circular table problem

I've looked other questions that might help solve my problem, but haven't found any people who've used my method to solve it. The problem goes like this: Suppose there are 7 men and 5 women, and they ...
3
votes
0answers
32 views

A combinatorial proof by tesselation of the plane.

Some days ago the following problem was posed in the site: given a set of $N$ points in the plane such that for each pair of points $p,q$ we have $\lVert p-q\rVert >1$, prove there is a subset of ...
1
vote
0answers
39 views

What is the number of set partitions of $\{1,1,2,2,3,3\}$?

It must be less than $B_6$ (where $B_6$ is the Bell number of $6$) since the elements are "duplicated". I would most appreciate a generating function that gives the number of set partitions of ...
2
votes
1answer
46 views

Counting number of bijections

The question is: Let $S = \{a,b,c,d\}$ and let $X : = \{f\colon S \to S \mid f \, \, \text{is bijective and } f(x) \ne x \, \, \text{for each}\, \, x \in S \}$. What is $|X|$? Is there a simple ...
2
votes
1answer
35 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
2answers
38 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 ...
1
vote
2answers
68 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 ...
-1
votes
1answer
20 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 ...
5
votes
0answers
36 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 ...
2
votes
1answer
38 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
49 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) = ...
3
votes
1answer
32 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 ...
0
votes
2answers
37 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. ...
0
votes
1answer
18 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 ...
0
votes
1answer
38 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?
2
votes
1answer
37 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 ...
3
votes
2answers
51 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 ...
3
votes
2answers
42 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 ...
1
vote
0answers
32 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
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 ...
1
vote
2answers
57 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?
1
vote
1answer
30 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$ ...
0
votes
0answers
69 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 almost exclusively discuss finite commutative ...
4
votes
2answers
91 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 ...
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
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?
1
vote
0answers
54 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 ...
0
votes
2answers
57 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 ...
5
votes
0answers
90 views
+50

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 ...
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.
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 ...
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 ...
3
votes
3answers
37 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 ...
1
vote
1answer
23 views

How many option are there to divide n people into any number of groups of any size?

I found only something like this: $$f(0) = 1$$ $$ f(n) = \sum_{i=0}^{n-1} \binom{n-1}{i} * f(i) $$ Now I wonder if there are other (faster) ways to calculate this.
2
votes
2answers
50 views

Count all possible combinations

I want to check how many combinations of $2$ numbers I can generate from $20$ different numbers when the same number can be picked twice. I calculated it like this and answer is $20 \cdot 20 =400$. Is ...
1
vote
0answers
61 views

Find the number of “p-safe numbers”

For a positive integer $p$, define the positive integer $n$ to be $p$-safe if $n$ differs in absolute value by more than $2$ from all multiples of $p$. For example, the set of $10$-safe numbers is ...
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 ...